Longest Subarray of 1's After Deleting One Element
Post
Cancel

# LeetCode #1493: Longest Subarray of 1's After Deleting One Element (C/C++).

medium

source: https://leetcode.com/problems/longest-subarray-of-1s-after-deleting-one-element/
C/C++ Solution to LeetCode problem 1493. Longest Subarray of 1's After Deleting One Element.

## Problem

Given a binary array nums, you should delete one element from it.

Return the size of the longest non-empty subarray containing only 1’s in the resulting array. Return 0 if there is no such subarray.

## Examples

### Example 1:

Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, [1,1,1] contains 3 numbers with value of 1’s.

### Example 2:

Input: nums = [0,1,1,1,0,1,1,0,1]
Output: 5
Explanation: After deleting the number in position 4, [0,1,1,1,1,1,0,1] longest subarray with value of 1’s is [1,1,1,1,1].

### Example 3:

Input: nums = [1,1,1]
Output: 2
Explanation: You must delete one element.

## Constraints

• 1 <= nums.length <= 105
• nums[i] is either 0 or 1.

## Solution

Two solutions:

1. A simple count of every group of ones.
2. Using an sliding window.

### Solution 1

• As long as we have 1s we count them.
• Every step, we add the current count with the last count before a 0 was found.
• If a 0 is found, our current count becomes the previous count, and we reset the current count.
• If two 0s are found, then the previous count will become 0
• We update the max value at every step (current count + previous count).
• After finishing, if the max count is equal to the size of the vector, then we just decrease the count by one.
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public: int longestSubarray(vector& nums) { int maxC = 0; int prev = 0; int c = 0; for (int i=0; i < nums.size(); i++) { if (nums[i] == 1) { c++; maxC = max(maxC, prev + c); } else { prev = c; c = 0; } } if (maxC == nums.size()) maxC--; return maxC; } };

### Solution 2

• As long as we don’t find a 0 we keep moving our right extreme of the window (growing).
• When we find a 0, we increase a count.
• Once the count is 2:
• We move the left extreme of the window until we find a 0 to decrease the count (shrinking window).
• At every step, we calculate the max with the size of the window (which contains only 1s and maximum one 0).
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public: int longestSubarray(vector& nums) { int left = 0; int count = 0; int maxC = 0; for (int right=0; right < nums.size(); right++) { count += nums[right] == 0; while (count > 1) count -= nums[left++] == 0; maxC = max(maxC, right - left); } return maxC; } };