Longest Run of Ones After One Flip
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Longest Run of Ones After One Flip
You are given a binary array `nums`, where every element is either `0` or `1`.
You may flip **at most one** `0` to a `1` (you are not required to flip any). Return the length of the longest contiguous run of `1`s you can obtain after performing at most one such flip.
Implement a function `findMaxConsecutiveOnes(nums)` that returns this maximum length as an integer.
### Examples
**Example 1**
```
nums = [1, 0, 1, 1, 0]
Output: 4
```
Flip the `0` at index 1 to get `[1, 1, 1, 1, 0]`, which has a run of four consecutive `1`s.
**Example 2**
```
nums = [1, 0, 1, 1, 0, 1]
Output: 4
```
Flipping the `0` at index 1 yields `[1, 1, 1, 1, 0, 1]`, giving a run of four `1`s. No single flip produces a longer run.
**Example 3**
```
nums = [1, 1, 1]
Output: 3
```
There is no `0` to flip; the whole array is already a run of three `1`s.
### Constraints
- $1 \le \text{len(nums)} \le 10^5$
- Each `nums[i]` is `0` or `1`.
### Follow-up (streaming)
Suppose `nums` is not given all at once but arrives as a **stream**: you read one element at a time, in order, you may not revisit earlier elements, and you cannot store the entire array in memory. Can you still produce the answer using only $O(1)$ additional space, updating your running result online as each new element arrives? Design your solution so that the same idea works in both the in-memory and streaming settings.
Quick Answer: This question tests a candidate's ability to solve a sliding window problem involving binary arrays, extending the basic "maximum consecutive ones" pattern to allow a single flip. It evaluates practical coding skill in tracking window boundaries and zero counts, plus the ability to adapt an in-memory approach to a constant-space streaming solution. This type of coding and algorithms question is common in interviews to assess array manipulation and space-optimization reasoning.
You are given a binary array `nums`, where every element is either `0` or `1`.
You may flip **at most one** `0` to a `1` (you are not required to flip any). Return the length of the longest contiguous run of `1`s you can obtain after performing at most one such flip.
Implement `findMaxConsecutiveOnes(nums)` returning this maximum length as an integer.
**Example 1:** `nums = [1, 0, 1, 1, 0]` -> `4` (flip index 1: `[1,1,1,1,0]`).
**Example 2:** `nums = [1, 0, 1, 1, 0, 1]` -> `4`.
**Example 3:** `nums = [1, 1, 1]` -> `3` (nothing to flip).
**Constraints:** `1 <= len(nums) <= 1e5`; each `nums[i]` is `0` or `1`.
**Follow-up (streaming):** `nums` arrives one element at a time; you cannot revisit earlier elements or store the whole array. Produce the answer online using only O(1) extra space. The sliding-window idea below adapts directly: track the count of ones in the current run, the count of ones in the previous run (before the last seen 0), and combine them.
Constraints
- 1 <= len(nums) <= 10^5
- Each nums[i] is 0 or 1
- At most one 0 may be flipped to 1 (flipping is optional)
Examples
Input: [1, 0, 1, 1, 0]
Expected Output: 4
Explanation: Flip index 1 to make [1,1,1,1,0]; longest run of 1s is 4.
Input: [1, 0, 1, 1, 0, 1]
Expected Output: 4
Explanation: Flipping index 1 gives [1,1,1,1,0,1]; no single flip beats 4.
Input: [1, 1, 1]
Expected Output: 3
Explanation: No 0 to flip; the array is already a run of 3.
Input: [0]
Expected Output: 1
Explanation: Flip the single 0 to get one 1.
Input: [1]
Expected Output: 1
Explanation: Single 1, nothing to flip.
Input: [0, 0]
Expected Output: 1
Explanation: Only one 0 may be flipped, so the best run is length 1.
Input: [0, 0, 0, 1]
Expected Output: 2
Explanation: Flip the 0 at index 2 to join the trailing 1: [.,.,1,1] gives a run of 2.
Input: [1, 1, 0, 1]
Expected Output: 4
Explanation: Flipping the single 0 joins the two runs into one run of 4.
Hints
- Reframe the flip: the answer is the length of the longest contiguous window containing at most one 0.
- Use a sliding window [left, right]. Expand right; when the window holds more than one 0, advance left until it holds at most one again.
- For the streaming O(1) follow-up, keep only the count of 1s in the current run and the count of 1s in the previous run (the run just before the most recently seen 0). On a 1, extend the current run; on a 0, the previous run becomes the current run and the current run resets to 0. The answer is max over time of (previous_run + 1 + current_run).