👨‍💻
Coding Interview Patterns
  • Coding Interview Patterns
  • 1. Pattern: Sliding Window
    • 1.0 Introduction
    • 1.1 Maximum Sum Subarray of Size K (easy)
    • 1.2 Smallest Subarray with a given sum (easy)
    • 1.3 Longest Substring with K Distinct Characters (medium)
    • 1.4 Fruits into Baskets (medium)
    • 1.5 No-repeat Substring (hard)
    • 1.6 Longest Substring with Same Letters after Replacement (hard)
    • 1.7 Longest Subarray with Ones after Replacement (hard)
    • 1.8 - Permutation in a String (hard)
    • 1.9 String Anagrams (hard)
    • 1.10 Smallest Window containing Substring (hard)
    • 1.11 Words Concatenation (hard)
  • 2. Pattern: Two Pointers
    • 2.0 Introduction
    • 2.1 Pair with Target Sum (easy)
    • 2.2 Remove Duplicates (easy)
    • 2.3 Squaring a Sorted Array (easy)
    • 2.4 Triplet Sum to Zero (medium)
    • 2.5 Triplet Sum Close to Target (medium)
    • 2.6 Triplets with Smaller Sum (medium)
    • 2.7 Subarrays with Product Less than a Target (medium)
    • 2.8 Dutch National Flag Problem (medium)
    • 2.9 Comparing Strings containing Backspaces (medium)
    • 2.10 Minimum Window Sort (medium)
  • 7. Pattern: Tree Breadth First Search
    • 7.0 Introduction
    • 7.1 Binary Tree Level Order Traversal (easy)
    • 7.2 Reverse Level Order Traversal (easy)
    • 7.3 Zigzag Traversal (medium)
    • 7.4 Level Averages in a Binary Tree (easy)
    • 7.5 Minimum Depth of a Binary Tree (easy)
    • 7.6 Maximum Depth of Binary Tree (easy)
    • 7.7 Level Order Successor (easy)
    • 7.8 Connect Level Order Siblings (medium)
    • 7.9 Problem Challenge 1 - Connect All Level Order Siblings (medium)
    • 7.10 Problem Challenge 2 - Right View of a Binary Tree (easy)
  • 11. Pattern: Modified Binary Search
    • 11.1 Introduction
    • 11.2 Order-agnostic Binary Search (easy)
    • 11.3
  • 16. Pattern: Topological Sort (Graph)
    • 16.1 Introduction
    • 16.2 Topological Sort (medium)
    • 16.3 Tasks Scheduling (medium)
    • 16.4 Tasks Scheduling Order (medium)
  • Contributor Covenant Code of Conduct
  • Page 1
Powered by GitBook
On this page

Was this helpful?

  1. 1. Pattern: Sliding Window

1.7 Longest Subarray with Ones after Replacement (hard)

Previous1.6 Longest Substring with Same Letters after Replacement (hard)Next1.8 - Permutation in a String (hard)

Last updated 3 years ago

Was this helpful?

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.

Example 1:

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.

Example 2:

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Solution:

public int longestOnes(int[] A, int K) {
    int max = 0;
    int zeroCount = 0; // zero count in current window
    int i = 0; // slow pointer
    for(int j = 0; j < A.length; ++j) {
        if(A[j] == 0) { // move forward j, if current is 0, increase the zeroCount
            zeroCount++;
        }
        
        // when current window has more than K, the window is not valid any more
        // we need to loop the slow pointer until the current window is valid
        while(zeroCount > K) {  
            if(A[i] == 0) {
                zeroCount--;
            }
            i++;
        }
        max = Math.max(max, j-i+1); // everytime we get here, the current window is valid 
    }
    return max;
}
Max Consecutive Ones III