LeetCode 1004. Max Consecutive Ones III

February 13, 2025

I completed the LeetCode 150! Since then, I haven't stopped practicing. I want to master common algorithms and feel confident for future interviews.

For this problem, I started with this greedy solution. We always flip a zero if we haven't done so k times. Each step, we check if our count is a new maximum. If we reach a zero and used all our flips, we reset our count and flips. We start counting again from this position.

Copy
1class Solution:
2    def longestOnes(self, nums: List[int], k: int) -> int:
3        largest = float('-inf')
4        count = 0
5        flipped = 0
6        for num in nums:
7            if num == 1:
8                count += 1
9            if num == 0 and flipped < k:
10                count += 1
11                flipped += 1
12            elif num == 0 and flipped == k:
13                largest = max(largest, count)
14                count, flipped = 1, 1
15        
16        return largest

This works for the first example:

Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2

Output: 6 (correct!)

However, for the second example, it fails to connect the first two strings of ones.

Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3

Output: 9 (incorrect, expected 10.)

To fix this, we will have to alter our algorithm to conditionally flip a zero. My idea is to apply our previous algorithm at each step.

Copy
1class Solution:
2    def longestOnes(self, nums: List[int], k: int) -> int:
3        largest = float('-inf')
4
5        def countOnes(start):
6            count = 0
7            flipped = 0
8            for i in range(start, len(nums)):
9                num = nums[i]
10                if num == 1:
11                    count += 1
12                if num == 0 and flipped < k:
13                    choice = i 
14                    count += 1
15                    flipped += 1
16                elif num == 0 and flipped == k:
17                    return count
18            return count
19        
20        for i in range(len(nums)):
21            largest = max(largest, countOnes(i))
22        
23        return largest

Unfortunately, this is inefficient, but it works. It has a quadratic time complexity of O(n) = (N^2 + n) / 2, also known as the nth triangle number.

Rather we should make this algorithm into a sliding-window algorithm. When we reach the end of a series of ones, we want to slide our window by moving our start to the second flip we made by removing our first flip along with any tail attached to it. To do this, we create a queue and add our tail each time we flip and set the new tail to 0.

Copy
1from collections import deque
2class Solution:
3    def longestOnes(self, nums: List[int], k: int) -> int:
4        largest = float('-inf')
5        count, tail = 0, 0
6        tails = deque([])
7        for i, num in enumerate(nums):
8            count += 1
9            tail += 1
10            if num == 0:
11                if tails and len(tails) == k:
12                    count -= tails.popleft()
13                elif not k:
14                    count = 0
15                tails.append(tail)
16                tail = 0
17            largest = max(largest, count)
18        return largest

This has a time complexity of O(n) = n at the tradeoff of space complexity being O(n) = n compared to O(n) = 1 for previous solutions.

LeetCode 120. Triangle

LeetCode 32. Longest Valid Parantheses