Count Subarrays With Sum Less Than K
Given an array of positive integers nums and a positive integer k, return the number of contiguous subarrays whose sum is strictly less than $k$.
Constraints:
- $1 \le n \le 10^5$ where $n$ is the length of
nums - $1 \le \text{nums}[i] \le 10^4$
- $1 \le k \le 10^9$
Example 1:
- Input:
nums = [2, 1, 4, 3],k = 5 - Output:
5 - Explanation: The valid subarrays are
[2](sum 2),[1](sum 1),[4](sum 4),[3](sum 3), and[2,1](sum 3). Subarrays like[1,4](sum 5) and[4,3](sum 7) are excluded because their sums are not strictly less than 5.
Example 2:
- Input:
nums = [1, 1, 1],k = 3 - Output:
5 - Explanation:
[1]appears 3 times (sums to 1 each),[1,1]appears 2 times (sums to 2 each). All five have sum < 3. The full array[1,1,1]sums to 3, which is not strictly less, so it is excluded.
Hints
- Since all elements are positive, the sum of any subarray only grows as you extend it. How can you use this monotonicity to avoid checking all $O(n^2)$ subarrays?
- Think about a two-pointer / sliding window approach. For a fixed right endpoint, there is a smallest valid left endpoint -- and every starting index from that left to right gives a valid subarray.
- For each
right, maintain a running sum and advanceleftwhile the sum is $\ge k$. The number of valid subarrays ending atrightis $\text{right} - \text{left} + 1$.
Worked Solution
How to Think About It: Naively you enumerate all $O(n^2)$ subarrays and sum each -- $O(n^2)$ or worse. The structural fact that kills the redundancy is that every element is positive, so a subarray's sum is *monotone*: extend the right end, the sum only grows; shrink the left end, it only shrinks. That monotonicity is exactly the license for a sliding window with no backtracking -- the left pointer only ever moves forward. The heuristic being taught is the two-pointer / monotone-window pattern, plus the counting trick: once you know the smallest valid left for a given right, *all* $(\text{right}-\text{left}+1)$ subarrays ending at right are automatically valid, so you add them in one shot instead of looping.
Quick Estimate (order-of-magnitude sanity): Give yourself a feel for the count before coding. If the values average $a$, a window stays under $k$ until it holds about $L\approx k/a$ elements, and there are $n$ possible right-endpoints, so the count is roughly $n\cdot\min(L, n/2)$ -- capped because a window can't be longer than the array. Test on Example 1: $\text{nums}=[2,1,4,3]$, average $a=2.5$, $k=5$, so $L\approx 5/2.5 = 2$ elements per window, $n=4$ endpoints $\Rightarrow \approx 4\times 2 = 8$ raw, but edge effects (windows near the start are short, and $[4]$ nearly saturates alone) trim it to the true $5$. Right order of magnitude, and the true answer $5$ is exactly the singleton count $4$ plus the one length-2 window $[2,1]$ -- consistent. Example 2: $[1,1,1]$, $k=3$: windows of length $\le 2$ qualify, giving $3$ singles $+ 2$ pairs $= 5$, matching.
Approach: Monotone sliding window; add $(\text{right}-\text{left}+1)$ per right endpoint.
Formal Solution:
Maintain a window $[\text{left},\text{right}]$ with a running window_sum. For each new right: 1. Add nums[right] to window_sum. 2. While window_sum $\ge k$ (and left $\le$ right), subtract nums[left] and increment left. 3. Now every start in $\{\text{left},\ldots,\text{right}\}$ gives a subarray ending at right with sum $< k$ -- exactly $\text{right}-\text{left}+1$ of them. Add that to the total.
Why step 3 is airtight: removing left elements can only *decrease* the sum, so if $[\text{left},\text{right}]$ is valid, so is every shorter suffix ending at right.
```python def count_subarrays(nums, k): count = 0 window_sum = 0 left = 0 for right in range(len(nums)): window_sum += nums[right] while window_sum >= k and left <= right: window_sum -= nums[left] left += 1 count += (right - left + 1) return count ```
*Edge case:* if a single nums[right] $\ge k$, the while loop pushes left past right, so $\text{right}-\text{left}+1 = 0$ -- correctly counting no valid subarray ending there.
Complexity: $\boxed{O(n)}$ time -- each element enters and leaves the window at most once, left never rewinds -- and $O(1)$ extra space.
Answer: Sliding window with two pointers. For each right endpoint, shrink from the left until the sum drops below $k$, then add $\text{right}-\text{left}+1$. $O(n)$ time, $O(1)$ space. (Verified: Example 1 $\to 5$, Example 2 $\to 5$.)
Intuition
This problem is a textbook application of the sliding window technique, and the reason it works boils down to one thing: monotonicity. Because every element is positive, extending a subarray always increases its sum and shrinking it always decreases it. That means for each right endpoint there is a clean cutoff -- a single leftmost starting index where the subarray sum first drops below $k$ -- and every starting index to the right of that cutoff also works. Without the positivity constraint (if elements could be negative), this monotonicity breaks and the two-pointer approach fails; you would need a more sophisticated method like a balanced BST on prefix sums.
The counting trick -- adding $\text{right} - \text{left} + 1$ per step instead of iterating through valid starting points -- is a pattern that shows up constantly in subarray counting problems. Any time you can express "number of valid subarrays ending at index $i$" as a simple formula of your window boundaries, you collapse an $O(n^2)$ enumeration into $O(n)$ total work. Recognizing this pattern immediately signals to an interviewer that you understand amortized analysis and can work with invariants rather than brute force.