Interview 150
Max Consecutive Ones III
- Problem
- LC 1004
- File
- interview150_LC1004MaxConsecutiveOnesIII.java
- Path
- pkg5leetcode/interview150/interview150_LC1004MaxConsecutiveOnesIII.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC1004MaxConsecutiveOnesIII.java
- Approach
- Sliding window max length with at most k zeros flipped.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Max Consecutive Ones III | LC 10045 * APPROACH: Sliding window max length with at most k zeros flipped.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class interview150_LC1004MaxConsecutiveOnesIII {9 static int longestOnes(int[] nums, int k) {10 int lo = 0, zeros = 0, best = 0;11 for (int hi = 0; hi < nums.length; hi++) {12 if (nums[hi] == 0) zeros++;13 while (zeros > k) if (nums[lo++] == 0) zeros--;14 best = Math.max(best, hi - lo + 1);15 }16 return best;17 }18 19 public static void main(String[] args) {20 check(longestOnes(new int[]{1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, 2) == 6, "case1");21 check(longestOnes(new int[]{0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 3) == 10, "case2");22 System.out.println("all tests passed");23 }24 25 static void check(boolean cond, String name) {26 if (!cond) throw new AssertionError("FAILED: " + name);27 System.out.println(" PASS " + name);28 }29}