Problem 795

Abstract / Summary

Count subarrays where the largest number is between two given values.

Note

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

Python 0795.py

class Solution:
    def numSubarrayBoundedMax(self, nums: List[int], left: int, right: int) -> int:
        result = 0

        def below(value):
            have = 0 # number of valid subarrays
            span = 0 # length of current subarray
            for n in nums:
                if n > value:
                    span  = 0
                else:
                    span += 1
                    have += span

            return have

        good  = below(right)    # all subarrays where max() <= right
        small = below(left - 1) # all subarrays where max() <  left
        return good - small
19 lines | 627 bytes | submitted July 5, 2024 | GitHub   25% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 55% (100k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Two Pointers
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 “Number of Subarrays with Bounded Maximum” problem. It counts subarrays whose maximum element lies within the inclusive interval [left, right]. The solution works by computing two cumulative counts: the number of subarrays whose maximum does not exceed right, and the number of subarrays whose maximum is strictly less than left. The difference between these two counts yields the desired result.

Core Logic

The algorithm defines an inner helper function below(value) that returns the total number of subarrays whose maximum element is not greater than value. The outer method invokes this helper twice-once with right and once with left-1-and subtracts the second result from the first.

def below(value):
    have = 0          # accumulator for valid subarrays
    span = 0          # length of the current stretch of elements ≤ value
    for n in nums:
        if n > value:
            span = 0
        else:
            span += 1
            have += span
    return have

The outer method then uses the helper:

good  = below(right)        # subarrays with max ≤ right
small = below(left - 1)     # subarrays with max < left
return good - small

How below Works

below iterates once over the input list nums. It maintains span, the length of the most recent contiguous segment where every element is ≤ value. When an element exceeds value, the segment ends and span resets to zero. For each element that stays within the bound, span grows by one, and the number of subarrays ending at the current position that satisfy the bound (span) is added to have. This cumulative addition captures all subarrays whose maximum does not exceed value.

Edge Cases Handled

When the input list contains elements larger than value, the reset of span to zero correctly discards any subarray that would include the offending element, ensuring those subarrays are not counted.

If left equals right, the subtraction below(right) - below(left-1) still works because below(left-1) counts subarrays whose maximum is strictly less than left, leaving only those whose maximum equals left (and therefore also equals right).

When left is 1, the call below(left - 1) becomes below(0). The helper treats any positive integer as exceeding 0, so only subarrays consisting entirely of zeros (if present) contribute to the count, which matches the intended definition of “max < left”.

An empty input list results in both helper calls returning 0, and the final result is 0, which aligns with the expectation that no subarrays exist.

If all elements are within [left, right], span never resets, and have accumulates the triangular number n*(n+1)/2, representing every possible subarray. The subtraction then yields the same total, confirming that all subarrays are valid.

When every element exceeds right, each iteration resets span to 0, leaving have at 0. Consequently, good is 0, and the final answer is 0, reflecting that no subarray satisfies the bound.

Performance Optimizations

The solution achieves linear time performance by scanning the input list only once per helper invocation. The inner loop performs constant-time operations: a comparison, a possible reset, an increment, and an addition to the accumulator. No auxiliary data structures are allocated beyond a few integer variables, keeping memory usage minimal.

By reusing the same helper logic for both right and left-1, the code avoids duplication and benefits from the same tight loop structure for both counts. The subtraction of the two cumulative results eliminates the need for a separate pass to filter subarrays that fall below left, thereby preserving the single-pass efficiency.

Overall, the algorithm balances clarity with optimal traversal, delivering the required count with the smallest possible overhead.

written by openai gpt

ELI5 - Simplified Explanation

Imagine a long row of building blocks standing in a line. Each block has a different number written on it. This code looks at every possible group of blocks sitting next to each other to see which groups fit a special rule.

The rule says that the biggest number in the group must be at least as big as the left number, but no bigger than the right number. Think of it like trying to find groups of playmates where the leader is not too short and not too tall.

To solve this, the code uses a clever trick. It first counts how many groups have a leader that is smaller than or equal to the high limit. Then it counts how many groups have a leader that is smaller than the low limit.

By taking the first count and subtracting the second count, the code is left with exactly the groups that have the perfect sized leader. It goes through the blocks one by one, keeping track of how long the current line of allowed blocks is, and adds that count to a total as it moves along.

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.85 | σ = 0.77

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
LeetcodeHelp C++ Python Java
Progiez C++ Python Java
github black-shadows C++
charles-wangkai Java
everthis JS
fpdjsns C++
halfrost Go
JoshCrozier JS
lkwq007 Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
wisdompeak C++
zfang399 C++
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C++, Go, Java, Python
LeetcodeHelp C++, Java, Python
Progiez C++, Java, Python
black-shadows C++, C++
charles-wangkai Java
everthis JavaScript
fpdjsns C++
halfrost Go
JoshCrozier JavaScript
lkwq007 Python
ruoru Rust
suxrobGM C#
trung-hn Python
varunu28 Java
wisdompeak C++
zfang399 C++
30 links | 18 authors | 8 languages

Videos

5 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

1 medium 1 hard
3 solutions   July 5, 2024

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