Longest Subarray of 1's After Deleting One Element — LeetCode 1493 Python Solution
MediumArrayDynamic ProgrammingSliding Window
- Problem
- #1493
- Pattern
- Sliding Window
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
Python
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
left = [0] * (n + 1)
right = [0] * (n + 1)
for i, x in enumerate(nums, 1):
if x:
left[i] = left[i - 1] + 1
for i in range(n - 1, -1, -1):
if nums[i]:
right[i] = right[i + 1] + 1
return max(left[i] + right[i + 1] for i in range(n))Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1493. Longest Subarray of 1's After Deleting One Element is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
On a study list
This problem is on LeetCode 75.
Frequently asked questions
- How hard is LeetCode 1493. Longest Subarray of 1's After Deleting One Element?
- LeetCode 1493. Longest Subarray of 1's After Deleting One Element is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1493. Longest Subarray of 1's After Deleting One Element?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1493. Longest Subarray of 1's After Deleting One Element?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1493. Longest Subarray of 1's After Deleting One Element cover?
- LeetCode 1493. Longest Subarray of 1's After Deleting One Element is tagged Array, Dynamic Programming and Sliding Window on LeetCode.