A window that changes size to fit a rule

Tier 1Free

Elman HuseynovUpdated 2026-10-21

Level

Where it runs

1. The problem

A customer of your platform has a spending limit. You know what their requests cost in each minute. You want the longest run of minutes in a row where the total cost stayed within the limit. That is the longest time the customer kept to the budget.

In the last lesson the window width k was given in advance. Here nobody gives it to you. The length of the run is the thing you are looking for. A window of a given width won't work, because the width is unknown.

The brute-force way tries every start. From each starting minute it walks forward until the sum goes over the limit, then writes down the length. That is O(n²), a loop inside a loop, and the stream of data can be huge.

2. In plain words

This time nobody tells you how wide the run should be. The width is what you are looking for: the longest run that still keeps a rule, such as staying within a budget.

Take the numbers 2, 3, 1, 2, 4 and the limit 7. Add numbers on the right one at a time: 2, then 3, then 1. The sum is 6, within the limit, with 3 numbers in the window. Add 2: the sum is 8, more than 7. So remove numbers on the left until the sum fits again: remove the 2, and the sum is 6. At every step, write down how many numbers are in the window, and remember the largest count. Each number is added once and removed at most once.

3. The idea

Keep two markers and the sum of the window. The right marker grows the window: it takes the next element and adds it to the sum. As soon as the sum breaks the rule, the left marker shrinks the window from the start. Subtract nums[left], move left forward, and repeat until the rule holds again. After each step the window from left to right keeps the rule, so write down its length.

All of this costs O(n), because left only moves forward and never comes back. It never needs to come back because all the numbers here are non-negative (zero or more). A number you add can only raise the sum, and a number you remove on the left can only lower it. Once the break is fixed, putting back the numbers removed on the left makes no sense: the sum would only grow.

Trace "the longest run with sum ≤ 7" on [2, 3, 1, 2, 4].

right points at 2: sum 2, length 1.
right points at 3: sum 5, length 2.
right points at 1: sum 6, length 3.
right points at 2: sum 8, more than 7. Remove the 2 on the left: sum 6, and left moves forward. The window is [3, 1, 2], length 3.
right points at 4: sum 10, more than 7. Remove the 3: sum 7, and left moves forward. The window is [1, 2, 4], length 3.

The best length is 3.

4. What it costs

Time is O(n). right passes over the list once. Over the whole pass, left moves at most n times in total. That is at most 2n moves. There is a while inside the for, but the while does not start over at each step of right. Memory is O(1): two markers and a sum.

5. Where this shows up

The longest period when spending of money or resources stayed within a limit. The longest stretch of stable service while the share of errors stayed below a threshold. The longest piece of text or of a list that meets a rule, when processing text and logs. Buffering choices such as "how much data to hold in memory before the size limit forces a flush". Any task "find the longest run of a stream that meets a condition" is solved with this window.

Longest stretch with sum at most 6

longestUnder([2, 1, 5, 1, 1, 2, 1], 6)

left

sum = 0limit = 6best = 0

Find the longest stretch whose sum stays at most 6. The window starts empty.

1 / 16

Speed race

Longest run with sum at most 50 in the same 40 positive numbers

Bars: the 40 values. About a quarter of them fit under the limit at once, and the size table keeps that ratio.

One operation is one value read. Every frame, each lane does the same number of operations, so the slow one falls behind.

Every start, then extend O(n²)

0 operations

Growing and shrinking window O(n)

0 operations

And with more numbers

Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.

n = 1,000

Every start, then extend251K · 2.5 ms

Growing and shrinking window2K · under 1 ms

n = 100,000

Every start, then extend2.5B · 25 s

Growing and shrinking window200K · 2 ms

n = 10,000,000

Every start, then extend25T · 2.9 days

Growing and shrinking window20M · 200 ms

Recognise it

Sliding window (variable)

Say these words and it is this pattern

longest/shortest contiguous subarray or substring
satisfying a condition (sum <= K, at most, without breaking a limit)
at most K distinct, no repeated element, contains all of X
contiguous span, not a subsequence

Looks similar, isn't

Sliding window (fixed size)
A fixed window is k wide from the first step to the last. This one picks its own width.
Two pointers (opposite ends)
Those start apart on sorted data and converge to one pair. Here both ends move the same way.
Prefix sums
Prefix sums handle negative values and arbitrary ranges. Shrinking assumes removing a value helps.
Hash set / map
A map on its own describes the whole collection. The window needs counts for the live span.

n up to 1e6 and one best span gives O(n). Each end advances at most n times.

On LeetCode

Problems that ask for the longest or shortest run in a row that keeps a limit, when the length is not given. Grow the window on the right and shrink it on the left while the limit is broken.

209.Minimum Size Subarray Sum (opens in a new tab)Medium
Grow until the sum reaches target, then shrink while it still does, keeping the shortest length.
1004.Max Consecutive Ones III (opens in a new tab)Medium
The window may hold at most k zeros, so shrink it as soon as it holds more.
1493.Longest Subarray of 1's After Deleting One Element (opens in a new tab)Medium
The same window with room for one zero, and the answer is its length minus one.
713.Subarray Product Less Than K (opens in a new tab)Medium
Keep a product instead of a sum, and each window that fits adds right minus left plus 1 new subarrays.

Your task (Tier 1)

Write the function longestSubarrayAtMost(nums, K).

Find the longest run of numbers in a row whose sum is at most K. Grow the window on the right, and shrink it on the left every time the sum goes over K.

Input: nums, a list of non-negative numbers, and K, the largest sum allowed. Example: [2, 3, 1, 2, 4], 7.
Return: the length of the longest run whose sum is at most K.

Steps:

Make a marker left = 0, a sum sum = 0 and a best length best = 0.
Move right from the start of the list to the end. At each step, add nums[right] to sum.
While sum is bigger than K, subtract nums[left] from sum and move left one step right.
Now the window from left to right fits the limit. If its length right - left + 1 is bigger than best, update best. At the end, return best.

Done when all tests pass:

[2, 3, 1, 2, 4], 7 -> 3
[1, 1, 1, 1], 2 -> 2
[1, 2], 100 -> 2 (the whole list fits)
[10, 1, 1], 5 -> 2 (the 10 never fits)
[5], 5 -> 1 (one number, exactly at the limit)
[], 10 -> 0 (empty list)
[9], 5 -> 0 (one number, already over the limit)

Practice

longestSubarrayAtMost

longestSubarrayAtMost(nums, K) -> number (length of longest contiguous subarray with sum <= K; nums are non-negative)

export function longestSubarrayAtMost(nums, K) {
  // Your code here. The task is described in the box above the editor.
}

Running as a guest

The tests run right here, no account needed. Your code is kept in this browser only. A free account keeps it on every device, marks the step done and shows where you are in the course.

Create a free account Log in

Hint ladder

Stuck? Reveal one rung at a time, but try it yourself first.

PreviousReusing the last window's work NextA window that remembers what's inside it