Longest Subarray with Ones after Replacement

Problem

Given an array A of 0's and 1's, and a value K which indicates that you may change up to K values from 0 to 1. Return the length of the longest (contiguous) subarray that contains only 1’s.

Examples

Example 1:

Input: nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], k = 2
Output: 6
Explanation:
To obtain the longest contiguous subarray of 1s, you can flip the 0s at index 5 and 10 to 1s:
[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]

Example 2:

Input: nums = [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], k=3
Output: 9
Explanation: Replace the 0s at index 6, 9, and 10 with 1s to get the longest contiguous subarray of 1s.

Solution

Method 1 - Sliding Window

This problem is a variation of the problem [Longest Substring with Same Letters after Replacement](longest-substring-with-same-letters-after-replacement). We can solve it using a similar sliding window strategy discussed in the previous problem.

Intuition

We use a sliding window to keep track of the longest subarray containing only 1s, allowing up to K replacements of 0s to 1s. By expanding the window to the right and shrinking it from the left when the number of zeros exceeds K, we efficiently find the answer.

Approach

1. Initialize two pointers: left and right to define the window bounds.
2. Use a variable numReplacements to count the number of zeros replaced in the current window.
3. Iterate right over the array:
   • If nums[right] == 0, increment numReplacements.
   • If numReplacements exceeds K, move left forward until the window has at most K zeros (decrement numReplacements if nums[left] == 0).
   • Update the maximum window size at each step.
4. Return the maximum window size found.

Code

C++

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, maxLen = 0, numReplacements = 0;
        for (int right = 0; right < nums.size(); ++right) {
            if (nums[right] == 0) numReplacements++;
            while (numReplacements > k) {
                if (nums[left] == 0) numReplacements--;
                left++;
            }
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

Go

func longestOnes(nums []int, k int) int {
    left, maxLen, numReplacements := 0, 0, 0
    for right := 0; right < len(nums); right++ {
        if nums[right] == 0 {
            numReplacements++
        }
        for numReplacements > k {
            if nums[left] == 0 {
                numReplacements--
            }
            left++
        }
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen
}

Java

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, maxLen = 0, numReplacements = 0;
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] == 0) numReplacements++;
            while (numReplacements > k) {
                if (nums[left] == 0) numReplacements--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Kotlin

class Solution {
    fun longestOnes(nums: IntArray, k: Int): Int {
        var left = 0
        var maxLen = 0
        var numReplacements = 0
        for (right in nums.indices) {
            if (nums[right] == 0) numReplacements++
            while (numReplacements > k) {
                if (nums[left] == 0) numReplacements--
                left++
            }
            maxLen = maxOf(maxLen, right - left + 1)
        }
        return maxLen
    }
}

Python

class Solution:
    def longestOnes(self, nums: list[int], k: int) -> int:
        left = 0
        maxLen = 0
        numReplacements = 0
        for right in range(len(nums)):
            if nums[right] == 0:
                numReplacements += 1
            while numReplacements > k:
                if nums[left] == 0:
                    numReplacements -= 1
                left += 1
            maxLen = max(maxLen, right - left + 1)
        return maxLen

Rust

impl Solution {
    pub fn longest_ones(nums: Vec<i32>, k: i32) -> i32 {
        let (mut left, mut max_len, mut num_replacements) = (0, 0, 0);
        for right in 0..nums.len() {
            if nums[right] == 0 { num_replacements += 1; }
            while num_replacements > k {
                if nums[left] == 0 { num_replacements -= 1; }
                left += 1;
            }
            max_len = max_len.max(right - left + 1);
        }
        max_len as i32
    }
}

TypeScript

class Solution {
    longestOnes(nums: number[], k: number): number {
        let left = 0, maxLen = 0, numReplacements = 0;
        for (let right = 0; right < nums.length; right++) {
            if (nums[right] === 0) numReplacements++;
            while (numReplacements > k) {
                if (nums[left] === 0) numReplacements--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

Complexity

• ⏰ Time complexity: O(n) — Each element is visited at most twice (once by right, once by left).
• 🧺 Space complexity: O(1) — Only a few variables are used for tracking window and replacements.