DSA Longest Run of Ones with K Flips

The problem

The problem gives a list of zeros and ones and a budget k. A flip turns a zero into a one, on paper only. The list itself does not change.

The question asks for one length. Find the longest stretch of neighbouring values that could become all ones with at most k flips. That is the longest stretch holding at most k zeros.

The input is the list and the integer k. The output is one integer, a length. An empty list answers 0.

cases = [
    ([1, 1, 0, 1, 1, 0, 1], 1, 5),
    ([1, 1, 0, 1, 1, 0, 1], 0, 2),
    ([1, 1, 0, 1, 1, 0, 1], 2, 7),
    ([0, 0, 1, 1, 0], 2, 4),
    ([1, 0, 1], 1, 3),
]
for nums, k, expected in cases:
    print("values", nums, "k", k, "longest:", expected)

One list carries the first three rows. Only the budget changes. With no flips the best pure run of ones has length 2, with one flip the answer is 5, and with two flips the whole list qualifies.

The fourth row starts with two zeros. Both can be flipped under a budget of 2, so the stretch reaches length 4 before the last zero stops it.

Intuition: extending the best pure run undercounts

A first idea looks for the longest pure run of ones. It then adds k, one extra place for each flip. The sum feels like the answer.

The idea misses how flips are really spent. A flipped zero can sit at the edge of a stretch, or between two shorter runs. The best stretch need not contain the longest pure run at all.

def shortcut(nums, k):
    best_run = 0
    run = 0
    for value in nums:
        run = run + 1 if value == 1 else 0
        best_run = max(best_run, run)
    return min(len(nums), best_run + k)

nums = [0, 1, 1, 0, 1]
print("shortcut answer:", shortcut(nums, 1))
print("correct answer: 4, from the stretch 1, 1, 0, 1 with its one zero flipped")

The shortcut reports 3, and the correct answer is 4. The winning stretch uses a run of two ones, one flipped zero, and then one more one. No single pure run explains it.

The method that works thinks in windows, not runs. Any stretch with at most k zeros is a candidate, wherever it sits. The scan has to consider stretches that start and end anywhere.

Brute force: test every stretch

The straightforward method lists every stretch. For each start, it extends the end and counts the zeros inside. A stretch counts when its zero count stays at or below k.

Once the zero count passes k, that start is finished. Every longer stretch from the same start holds at least as many zeros, so none of them can qualify either.

def brute_ones(nums, k):
    best = 0
    checked = 0
    for start in range(len(nums)):
        zeros = 0
        for end in range(start, len(nums)):
            checked += 1
            if nums[end] == 0:
                zeros += 1
            if zeros > k:
                break
            best = max(best, end - start + 1)
    return best, checked

for nums, k in [([1, 1, 0, 1, 1, 0, 1], 1), ([0, 0, 1, 1, 0], 2)]:
    best, checked = brute_ones(nums, k)
    print("values", nums, "k", k, "longest:", best, "stretches checked:", checked)

The answers are right. The cost is the repetition. Each start recounts the zeros of stretches that overlap the previous start almost completely.

The overlap is the opening for a better method. Neighbouring stretches differ by one value at each edge. A window that slides can add and remove those edge values instead of recounting everything.

The optimal solution: a window with a zero budget

The window is the current stretch. Its right edge grows one value per step. A counter tracks how many zeros sit inside it.

The key idea is one sentence. The window stays valid while its zero count stays at or below k, and whenever the count passes k the left edge shrinks the window until the count fits again.

def longest_ones(nums, k):
    left = 0
    zeros = 0
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

cases = [
    ([1, 1, 0, 1, 1, 0, 1], 1),
    ([1, 1, 0, 1, 1, 0, 1], 0),
    ([1, 1, 0, 1, 1, 0, 1], 2),
    ([0, 0, 1, 1, 0], 2),
    ([1, 0, 1], 1),
]
for nums, k in cases:
    print("values", nums, "k", k, "longest:", longest_ones(nums, k))

All five cases from the start of the article pass. The best length updates only after the shrink loop ends. At that moment the window is valid again, so its length is a real candidate.

The budget is spent by the counter, not by editing the list. No value in the input changes, which is why the same list can be scanned again under a different k.

Walkthrough: one flip on [1, 1, 0, 1, 1, 0, 1]

Follow the main list with k = 1. The window grows freely until the second zero arrives at the last-but-one position. That zero pushes the count to 2, one over budget.

nums = [1, 1, 0, 1, 1, 0, 1]
k = 1
left = 0
zeros = 0
best = 0
for right in range(len(nums)):
    if nums[right] == 0:
        zeros += 1
    while zeros > k:
        if nums[left] == 0:
            zeros -= 1
        left += 1
    best = max(best, right - left + 1)
    print("right", right, "window:", nums[left:right + 1], "zeros:", zeros, "best:", best)
print("answer:", best)

The shrink at right index 5 moves the left edge three places. It passes two ones and then the first zero, which brings the count back to 1. The window that remains is [1, 1, 0], of length 3.

The final value extends that window to [1, 1, 0, 1], of length 4. The best stays at 5, set earlier by the window that ended at right index 4.

Complexity

Time is O(n). The right edge visits each value once, and the left edge moves forward at most n times across the whole scan, so the total edge moves stay within twice n.

Space is O(1). The method keeps two edges, one zero counter, and one best length, whatever the size of the list.

def edge_moves(nums, k):
    left = 0
    zeros = 0
    moves = 0
    for right in range(len(nums)):
        moves += 1
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
            moves += 1
    return moves

def brute_checked(n):
    checked = 0
    for start in range(n):
        for end in range(start, n):
            checked += 1
    return checked

for n in [10, 20, 40]:
    print("n", n, "window edge moves:", edge_moves([1, 0] * (n // 2), 1), "brute stretches:", brute_checked(n))

The printed counts show the gap. The window moves stay close to twice n on this alternating pattern. The brute stretches follow n times n plus one, over two, and pull away fast.

Edge cases and pitfalls

A budget of zero is a real case, not an error. It forbids zeros in the window completely, so the answer is the longest pure run of ones. A budget that covers every zero in the list makes the whole list the answer.

An all-zero list answers k, capped by its own length. Each place in the stretch is bought with a flip, and the budget runs out before the values do when k is the smaller number.

def longest_ones(nums, k):
    left = 0
    zeros = 0
    best = 0
    for right in range(len(nums)):
        if nums[right] == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

print("empty list:", longest_ones([], 2))
print("k = 0:", longest_ones([1, 1, 0, 1], 0))
print("k covers all zeros:", longest_ones([0, 1, 0], 5))
print("all zeros, k = 2:", longest_ones([0, 0, 0, 0], 2))
print("all ones:", longest_ones([1, 1, 1], 0))

One pitfall is measuring the window before the shrink finishes. A window that is still over budget is not a candidate, and its length would inflate the answer. The code shrinks first and measures second, on every step.

A second pitfall is forgetting to lower the zero counter when the left edge passes a zero. The counter would stay over budget, the left edge would keep moving, and valid stretches would be cut short.