Katkat
Back

Longest Run of Ones After One Flip

LinkedInSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage a sliding window with a flexible constraint, specifically counting zeros to determine the maximum length of a sequence after a single modification.

Problem Statement

Given a binary array nums, you are allowed to flip at most one 0 to a 1. Find the length of the longest contiguous sequence of 1s that can be formed in the modified array.

Function Signature

def longest_ones_after_flip(nums: list[int]) -> int:

Constraints

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

Examples

Example 1:

  • Input: nums = [1, 0, 1, 1, 0]
  • Output: 4
  • Explanation: Flip the 0 at index 1 or 4. If we flip index 1, the array becomes [1, 1, 1, 1, 0], yielding a sequence of 4 ones.

Example 2:

  • Input: nums = [0, 0, 0]
  • Output: 1
  • Explanation: Flip any one 0 to a 1, yielding a sequence of 1 one.

Edge Cases

  • Array with no zeros: The answer is the entire length of the array.
  • Array with only zeros: The answer is 1.
  • Empty array: The answer is 0.

Hints

Hint 1

Consider using a sliding window approach with two pointers, `left` and `right`, to represent the current contiguous sequence.

Hint 2

Maintain a count of zeros within your current window; as long as the count of zeros is 1 or less, the window is valid.

Hint 3

If the number of zeros exceeds 1, increment the `left` pointer to shrink the window until the zero count returns to 1.

Follow-up questions

  • How would you modify your solution if you were allowed to flip up to 'k' zeros instead of just one?
  • If the input was a stream of bits arriving one by one (where you cannot store the entire array in memory), how would you track the longest run?
  • What is the time and space complexity of your current solution, and can you prove it is optimal?