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.
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 either0
or1
.
SOLUTION:
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
chunks = []
i = 0
zeroFound = False
mlen = 0
msingle = 0
while i < n:
ctr = 1
while i < n - 1 and nums[i] == nums[i + 1]:
ctr += 1
i += 1
i += 1
chunks.append((nums[i - 1], ctr))
if nums[i - 1] == 1:
msingle = max(msingle, ctr)
else:
zeroFound = True
k = len(chunks)
for i in range(1, k - 1):
if chunks[i] == (0, 1):
mlen = max(mlen, chunks[i - 1][1] + chunks[i + 1][1])
if zeroFound:
mlen = max(mlen, msingle)
else:
mlen = max(mlen, msingle - 1)
return mlen
Top comments (0)