Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Longest Subarray with Ones after Replacement
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given an array containing 0s and 1s, if you are allowed to replace no more than ‘k’ 0s with 1s, find the length of the longest contiguous subarray having all 1s.

Example 1:

Input: Array=[0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k=2  
Output: 6  
Explanation: Replace the '0' at index 5 and 8 to have the longest contiguous subarray of 1s having length 6.

Example 2:

Input: Array=[0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3  
Output: 9  
Explanation: Replace the '0' at index 6, 9, and 10 to have the longest contiguous subarray of 1s having length 9.

Example 3:

Input: Array=[1, 0, 0, 1, 1, 0, 1, 1], k=2
Output: 6
Explanation: By flipping 0 at the second and fifth index in the list, we get [1, 0, 1, 1, 1, 1, 1, 1], which has 6 consecutive 1s.

Constraints:

  • 1 <= arr.length <= 10^5
  • arr[i] is either 0 or 1.
  • 0 <= k <= nums.length

Solution

This problem follows the Sliding Window pattern and is quite similar to Longest Substring with same Letters after Replacement. The only difference is that, in the problem, we only have two characters (1s and 0s) in the input arrays.

Following a similar approach, we’ll iterate through the array to add one number at a time in the window. We’ll also keep track of the maximum number of repeating 1s in the current window (let’s call it maxOnesCount). So at any time, we know that we can have a window with 1s repeating maxOnesCount time, so we should try to replace the remaining 0s. If we have more than ‘k’ remaining 0s, we should shrink the window as we are not allowed to replace more than ‘k’ 0s.

Step-by-Step Algorithm

  • Initialize windowStart to 0, maxLength to 0, and maxOnesCount to 0.
  • Iterate over the array using windowEnd from 0 to the end of the array.
    • If the current element is 1, increment maxOnesCount.
    • Calculate the current window size as windowEnd - windowStart + 1.
    • If the number of 0s in the current window (windowEnd - windowStart + 1 - maxOnesCount) is greater than k, shrink the window from the start.
      • If the element at windowStart is 1, decrement maxOnesCount.
      • Increment windowStart.
    • Update maxLength to be the maximum of maxLength and the current window size.
  • Return maxLength as the length of the longest subarray.

Algorithm Walkthrough

Consider the input arr = [0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1], k = 2.

Let's walk through the algorithm step-by-step, keeping track of all the important variables:

  1. Initialization:

    • windowStart = 0
    • maxLength = 0
    • maxOnesCount = 0

  2. Iterating over the array:

    • Iteration 1:

      • windowEnd = 0, arr[0] = 0
      • maxOnesCount = 0
      • Window size: windowEnd - windowStart + 1 = 1
      • Condition: 1 - 0 > 2 is False
      • Update maxLength = 1

    • Iteration 2:

      • windowEnd = 1, arr[1] = 1
      • maxOnesCount = 1
      • Window size: windowEnd - windowStart + 1 = 2
      • Condition: 2 - 1 > 2 is False
      • Update maxLength = 2

    • Iteration 3:

      • windowEnd = 2, arr[2] = 1
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 3
      • Condition: 3 - 2 > 2 is False
      • Update maxLength = 3

    • Iteration 4:

      • windowEnd = 3, arr[3] = 0
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 4
      • Condition: 4 - 2 > 2 is False
      • Update maxLength = 4

    • Iteration 5:

      • windowEnd = 4, arr[4] = 0
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 2 > 2 is True
      • Shrink window: windowStart = 1
      • Since arr[0] = 0, maxOnesCount remains 2

    • Iteration 6:

      • windowEnd = 5, arr[5] = 0
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 2 > 2 is True
      • Shrink window: windowStart = 2
      • Since arr[1] = 1, maxOnesCount = 1

    • Iteration 7:

      • windowEnd = 6, arr[6] = 1
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 2 > 2 is True
      • Shrink window: windowStart = 3
      • Since arr[2] = 1, maxOnesCount = 1

    • Iteration 8:

      • windowEnd = 7, arr[7] = 1
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 2 > 2 is True
      • Shrink window: windowStart = 4
      • Since arr[3] = 0, maxOnesCount remains 2

    • Iteration 9:

      • windowEnd = 8, arr[8] = 0
      • maxOnesCount = 2
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 2 > 2 is True
      • Shrink window: windowStart = 5
      • Since arr[4] = 0, maxOnesCount remains 2

    • Iteration 10:

      • windowEnd = 9, arr[9] = 1
      • maxOnesCount = 3
      • Window size: windowEnd - windowStart + 1 = 5
      • Condition: 5 - 3 > 2 is False
      • Update maxLength = 5

    • Iteration 11:

      • windowEnd = 10, arr[10] = 1
      • maxOnesCount = 4
      • Window size: windowEnd - windowStart + 1 = 6
      • Condition: 6 - 4 > 2 is False
      • Update maxLength = 6
  • The maximum length of the subarray with at most k replacements is 6.
  • The final values of the variables are:
    • windowStart = 5
    • windowEnd = 10
    • maxOnesCount = 4
    • maxLength = 6
Image

Code  

Here is what our algorithm will look like:

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Single pass: The algorithm uses a sliding window approach and makes a single pass through the input array. The outer loop runs once for each element in the array, which means the algorithm iterates through the array exactly once. Therefore, the outer loop runs O(N) times, where N is the length of the array.

  • Sliding window adjustment: For each element in the array, the sliding window is adjusted when the number of 0s in the window exceeds k. Since adding or removing elements from the window involves constant-time operations, the inner logic inside the loop runs in constant time, O(1).

Overall time complexity: O(N) because both the outer loop and the inner operations are processed linearly.

Space Complexity

  • Additional variables: The algorithm uses a few additional variables (windowStart, windowEnd, maxLength, maxOnesCount), which require constant space, O(1). No additional data structures are used that depend on the input size.

Overall space complexity: O(1).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible