Problem 1493

Abstract / Summary

Given an array of integers, count how many times the value equals its index.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
15 lines | 466 bytes | submitted September 12, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 71% (900k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Dynamic Programming
  • Sliding Window
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 26 | median = 8 | μ = 7.42 | σ = 1.04

Complexity Analysis

Time: linear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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
25 links | 13 authors | 8 languages

Similar Problems

1 similar problem

Solved On The Same Day

26 solutions   September 12, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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