LeetCode 1004 - Max Consecutive Ones III

Link : https://leetcode.com/problems/max-consecutive-ones-iii/description/

import java.util.*;

/**
 * LeetCode 1004: Max Consecutive Ones III
 * 
 * Problem: Given a binary array nums and an integer k, return the maximum number
 * of consecutive 1's in the array if you can flip at most k 0's.
 * 
 * Key Implementation Details:
 * 1. Sliding window technique with count tracking
 * 2. Space-efficient solution
 * 3. Input validation
 * 4. Edge case handling
 * 
 * Example:
 * Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
 * Output: 6
 * Explanation: [1,1,1,0,0,1,1,1,1,1,1]
 * Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
 */
public class MaxConsecutiveOnes {

    /**
     * Finds maximum consecutive ones using sliding window.
     * 
     * Time Complexity: O(n) - single pass through array
     * Space Complexity: O(1) - only uses a few variables
     * 
     * @param nums Binary array
     * @param k Maximum number of flips allowed
     * @return Maximum length of consecutive ones possible
     */
    public Result longestOnes(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new Result(0, 0, 0, new int[0]);
        }

        int start = 0;
        int maxLength = 0;
        int zeroCount = 0;
        int bestStart = 0;
        int bestEnd = 0;

        // Slide window through array
        for (int end = 0; end < nums.length; end++) {
            if (nums[end] == 0) {
                zeroCount++;
            }

            // Shrink window while we have too many zeros
            while (zeroCount > k) {
                if (nums[start] == 0) {
                    zeroCount--;
                }
                start++;
            }

            // Update maximum if current window is longer
            if (end - start + 1 > maxLength) {
                maxLength = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }
        }

        // Create array showing the flips
        int[] result = Arrays.copyOfRange(nums, bestStart, bestEnd + 1);
        int flipsUsed = 0;
        for (int i = 0; i < result.length && flipsUsed < k; i++) {
            if (result[i] == 0) {
                result[i] = 1;
                flipsUsed++;
            }
        }

        return new Result(maxLength, bestStart, bestEnd, result);
    }

    /**
     * Class to hold result information
     */
    public static class Result {
        public final int length;
        public final int startIndex;
        public final int endIndex;
        public final int[] sequence;

        public Result(int length, int startIndex, int endIndex, int[] sequence) {
            this.length = length;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
            this.sequence = sequence;
        }
    }

    public static void main(String[] args) {
        MaxConsecutiveOnes solution = new MaxConsecutiveOnes();

        // Test cases
        TestCase[] testCases = {
            new TestCase(
                new int[]{1,1,1,0,0,0,1,1,1,1,0},
                2,
                "Standard case from problem description"
            ),
            new TestCase(
                new int[]{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1},
                3,
                "Complex case with multiple options"
            ),
            new TestCase(
                new int[]{1},
                1,
                "Single element 1"
            ),
            new TestCase(
                new int[]{0},
                1,
                "Single element 0"
            ),
            new TestCase(
                new int[]{1,1,1,1,1},
                2,
                "All ones"
            ),
            new TestCase(
                new int[]{0,0,0,0},
                2,
                "All zeros with k < length"
            ),
            new TestCase(
                new int[]{0,0,0,0},
                4,
                "All zeros with k = length"
            ),
            new TestCase(
                new int[]{1,0,1,0,1},
                1,
                "Alternating with k=1"
            ),
            new TestCase(
                new int[]{1,0,1,0,1},
                2,
                "Alternating with k=2"
            ),
            new TestCase(
                new int[]{1,1,1,0,0,1,1},
                1,
                "Single flip required"
            )
        };

        for (TestCase test : testCases) {
            runTest(solution, test);
        }
    }

    private static class TestCase {
        int[] nums;
        int k;
        String description;

        TestCase(int[] nums, int k, String description) {
            this.nums = nums;
            this.k = k;
            this.description = description;
        }
    }

    private static void runTest(MaxConsecutiveOnes solution, TestCase test) {
        System.out.println("\nTest: " + test.description);
        System.out.println("Input array: " + Arrays.toString(test.nums));
        System.out.println("Max flips (k): " + test.k);

        Result result = solution.longestOnes(test.nums, test.k);

        System.out.println("Maximum consecutive ones: " + result.length);
        System.out.println("Window position: [" + result.startIndex + ", " + result.endIndex + "]");
        System.out.println("Resulting sequence: " + Arrays.toString(result.sequence));

        // Verify result
        int flips = 0;
        for (int i = result.startIndex; i <= result.endIndex; i++) {
            if (test.nums[i] == 0) {
                flips++;
            }
        }

        boolean valid = flips <= test.k;
        System.out.println("Result verified: " + valid + 
                          " (uses " + flips + " flips, maximum allowed: " + test.k + ")");

        // Verify optimality
        boolean optimal = verifyOptimal(test.nums, test.k, result.length);
        System.out.println("Solution is optimal: " + optimal);
    }

    /**
     * Helper method to verify the solution is optimal by checking all possible windows
     */
    private static boolean verifyOptimal(int[] nums, int k, int resultLength) {
        for (int start = 0; start < nums.length; start++) {
            int flips = 0;
            int length = 0;

            for (int end = start; end < nums.length && flips <= k; end++) {
                if (nums[end] == 0) {
                    flips++;
                }
                if (flips <= k) {
                    length = end - start + 1;
                    if (length > resultLength) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}