Python 1493.py
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
right = left = best = zeros = 0
while right < len(nums):
if nums[right] == 0:
zeros += 1
while left < right and zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
right += 1
best = max(best, right - left - 1)
return best
Difficulty
and has an acceptance rate of about 71% (900k+ submissions).
Typical patterns to solve this problem:
- Array
- Dynamic Programming
- Sliding Window
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The provided implementation solves the problem of finding the length of the longest sub-array that contains only 1s after deleting exactly one element from the original array. It employs a two-pointer (sliding-window) technique that dynamically adjusts the window boundaries while tracking the number of zeros inside the current window. The algorithm iterates through the input list once, maintaining the best length observed so far.
Core Logic
The algorithm initializes four integer variables: right, left, best, and zeros. All start at zero, representing the right pointer, left pointer, the best length found, and the count of zeros inside the current window, respectively.
right = left = best = zeros = 0
A while loop drives the right pointer from the start of the list to its end. Inside the loop, the element at the current right index is examined. When a zero is encountered, the zeros counter is incremented. If the window now contains more than one zero, the left pointer is advanced until the window is reduced to at most one zero. This inner adjustment also decrements the zero count when a zero leaves the window.
if nums[right] == 0:
zeros += 1
while left < right and zeros > 1:
if nums[left] == 0:
zeros -= 1
left += 1
After handling the zero-count constraint, the right pointer is moved forward, and the candidate length for the current window is computed as right - left - 1. The subtraction of one accounts for the mandatory deletion of a single element (the zero that will be removed). The best variable is updated with the maximum of its current value and the newly computed length.
right += 1
best = max(best, right - left - 1)
When the loop finishes, best holds the length of the longest sub-array consisting solely of 1s after removing one element, and it is returned.
return best
Edge Cases Handled
The code gracefully handles several edge conditions without additional branching.
When the input consists entirely of 1s, the window never encounters a zero, so zeros remains zero throughout. The subtraction of one in the length calculation still correctly reflects the required deletion, yielding a result of len(nums) - 1.
If the array contains a single zero surrounded by 1s, the window expands to include the entire array, the zero count never exceeds one, and the final length equals the total number of 1s, which is the optimal answer.
When the array is composed solely of zeros, the inner while loop quickly collapses the window to a single element, and the length calculation yields zero, which matches the expectation that no sub-array of 1s can be formed after a deletion.
The condition while left < right and zeros > 1 ensures that the left pointer never overtakes the right pointer, preserving a valid window even when consecutive zeros appear at the start of the array.
Performance Optimizations
The implementation achieves optimal traversal by moving each pointer at most once across the array. The right pointer advances monotonically in the outer loop, while the left pointer only moves forward when the zero count exceeds the allowed threshold. This guarantees that the total number of pointer movements is bounded by twice the length of the input, eliminating redundant scans.
By maintaining the zero count incrementally rather than recomputing it for each window, the algorithm avoids costly inner loops that would otherwise examine the entire window contents. The use of a single max call per iteration to update the best length keeps the per-iteration work minimal.
All arithmetic operations are simple integer updates, and the algorithm relies on direct index access, which is O(1) in Python lists. Consequently, the runtime remains linear with respect to the size of the input, and the memory footprint stays constant because only a handful of scalar variables are used.
ELI5 - Simplified Explanation
Imagine a long train made of blocks that are either ones or zeros. The goal is to find the longest part of the train that has only ones, but there is a special rule where one zero is allowed to hide inside that long stretch.
The code starts at the beginning of the train with two pointers that act like two fingers marking the start and the end of a section. The right finger moves forward to explore the train one block at a time. Every time a zero is spotted, it gets counted. If the count of zeros ever goes above one, the left finger moves forward to shrink the section until the number of zeros is back down to one again.
As the right finger moves through the train, the code keeps track of how big the section is between the two fingers. By subtracting one to account for the extra hidden zero, it calculates the length of the string of ones. Throughout the journey across the train, the code remembers the largest size it has ever found. Once the right finger reaches the very end of the train, the biggest size discovered during the walk is kept as the answer.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Python | Java | TS | ||||
| WalkCCC | C++ | Python | Java | ||||||
| leetcode.ca | C++ | Python | Java | Go | Rust | TS | |||
| Progiez | C++ | Python | Java | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JS | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, Rust, TypeScript | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| fsq | C++ | ||||||||
| JoshCrozier | JavaScript | ||||||||
| keineahnung2345 | C++ | ||||||||
| lkwq007 | Python | ||||||||
| suxrobGM | C# | ||||||||
| trung-hn | Python |
Similar Problems
- problem 1004: Max Consecutive Ones III
Solved On The Same Day
- problem 724: Find Pivot Index
- problem 872: Leaf-Similar Trees
- problem 933: Number of Recent Calls
- problem 1207: Unique Number of Occurrences
- problem 1732: Find the Highest Altitude
- problem 2215: Find the Difference of Two Arrays
- problem 328: Odd Even Linked List
- problem 443: String Compression
- problem 649: Dota2 Senate
- problem 735: Asteroid Collision
- problem 875: Koko Eating Bananas
- problem 901: Online Stock Span
- problem 1161: Maximum Level Sum of a Binary Tree
- problem 1268: Search Suggestions System
- problem 1282: Group the People Given the Group Size They Belong To
- problem 1372: Longest ZigZag Path in a Binary Tree
- problem 1448: Count Good Nodes in Binary Tree
- problem 1456: Maximum Number of Vowels in a Substring of Given Length
- problem 1647: Minimum Deletions to Make Character Frequencies Unique
- problem 1657: Determine if Two Strings Are Close
- problem 1926: Nearest Exit from Entrance in Maze
- problem 2095: Delete the Middle Node of a Linked List
- problem 2130: Maximum Twin Sum of a Linked List
- problem 2352: Equal Row and Column Pairs
- problem 2390: Removing Stars From a String
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality