DSA sheet · Arrays · Sliding Window pattern

Subarray Product Less Than K

This is the first "count the windows" problem of the sliding window pattern. The teacher first writes a brute force with two loops (the inner loop walks backwards from each index), finds an important base case from the constraints (k ≤ 1 → answer 0), then goes through her four array patterns to pick sliding window. The heart of the video is one line: count += right − left + 1. She spends a lot of time showing why that formula counts every valid subarray exactly once, and so do these notes.

Why it matters: "count subarrays whose (sum / product / distinct count …) stays within a limit" always uses this same right − left + 1 trick. Later problems (like Subarrays with K Different Integers) build directly on it.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting (sliding window from scratch)
• Part A · Brute force: every subarray, walking left from each index
• Part B · Optimal: sliding window + count += right − left + 1
• Part C · Revision page

Part 0 · Before starting

What is a subarray?

A subarray is a piece of the array whose elements sit next to each other (we say contiguous). You pick a start index and an end index and take everything between them. You are not allowed to skip an element in the middle. (For strings, the same idea is called a substring.)

An array of length n has n·(n+1)/2 non-empty subarrays. For n = 4 that's 10.

The brute force over all windows, and why it repeats work

The simplest way to solve any "subarray" question is: fix one end, move the other end one step at a time, and check every piece. That is two nested loops, so about n²/2 checks → O(n²).

The waste: the piece [5, 2, 6] and the piece [5, 2] share almost everything. The brute force forgets what it learned about [5, 2] and starts again from scratch for the next start index. Sliding window keeps what it already knows and only adjusts the edges.

The window [left..right]

A window is just the current subarray, described by two pointers: left (its first index) and right (its last index). Its length is right − left + 1. We keep a small summary of what's inside (a sum, a product, a count map…) so we never re-add the whole window.

• Expand = move right one step forward and add the new element to the summary.
• Shrink = remove nums[left] from the summary and move left one step forward.

Both pointers only ever move forward. Neither ever goes back. That is why the whole thing is O(n).

Fixed-size vs variable-size windows

Three kinds of variable-window questions

A related trick you'll meet later: "count subarrays with exactly K of something" = atMost(K) − atMost(K − 1). We don't need it here, because "product < k" is already an "at most" style rule.

Why sliding window needs a "monotonic" rule

Shrinking is only safe if removing an element always moves the window towards valid, and growing only ever moves it towards invalid. Here every number is ≥ 1, so:

• multiplying in a new number makes the product bigger or equal (never smaller);
• dividing out the left number makes it smaller or equal (never bigger).

If numbers could be 0 or negative, or fractions below 1, this promise breaks, and the window can skip answers. (With sums, the same thing happens when negative numbers are allowed.)

Other tools you'll see in this pattern (not needed here)

• Frequency map (dict or collections.Counter): "value → how many times it's in the window". Used when the rule is about distinct values (Fruits Into Baskets, anagrams).
• Monotonic deque: a deque that keeps indexes in decreasing order of value, used only for Sliding Window Maximum.

The teacher's 4 array patterns

Whenever she wants to optimise an array problem, she checks four patterns from the first video of the playlist:

Part A · Brute force: every subarray, walking left from each index

LeetCode 713

1The question in simple words

You get an array of positive integers nums and an integer k. Return how many subarrays have a product (all elements multiplied together) that is strictly less than k. "Strictly" matters: if k = 100, a product of 99 counts, but 100 does not.

The teacher lists every subarray and its product, grouped by where it starts:

Valid products: 10, 50, 5, 10, 60, 2, 12, 6 → 8 subarrays, which matches the expected output.

2What the constraints tell us

• 1 ≤ n ≤ 3·10⁴. O(n²) is up to 9·10⁸ steps. The teacher's rule: beyond about 10⁸ operations you risk TLE. So we'll need something better, but she writes the brute force first.
• 1 ≤ nums[i] ≤ 1000. Every number is at least 1. No zeros, no negatives. Remember this: it gives us the base case below, and it's what makes the sliding window safe.
• 0 ≤ k ≤ 10⁶. k can be 0 or 1. The teacher says the constraints are what help us find the base case. (She reads the upper limit of k aloud as 10⁵ once and 1000 later; LeetCode's actual limit is 10⁶. It doesn't change anything.)

The base case: k ≤ 1 → answer 0

The smallest possible product of any subarray is 1 (every number is ≥ 1, and multiplying more numbers ≥ 1 never goes below that). We need a product strictly less than k.

• k = 0: is any product < 0? No, products are at least 1.
• k = 1: is any product < 1? No. Even [1, 1, 1] has product 1, which is not less than 1.

3Intuition: list every subarray, multiply, and count

If we could visit every subarray, multiply its numbers and check "< k?", we'd just do count += 1 each time it's true. Two loops can list all subarrays: one finger i fixes one end, a second finger j walks away from it.

The teacher points out that j may walk in either direction from i, as long as you pick one. She chooses to walk leftwards: j goes from i down to 0. So for each i, we list all subarrays that end at i.

4Building the logic from the example

A product variable, starting at 1 (not 0)

For sums we start at 0. For a product we must start at 1. If we started at 0, multiplying anything into it would keep it 0 forever. And just like a sum, the product must be reset for each new i, because a new i means a new family of subarrays.

Walk it on [10, 5, 2, 6], k = 100

• i = 0: j = 0 → product 10 → < 100 ✓ count 1.
• i = 1: j = 1 → 5 ✓; j = 0 → 5 × 10 = 50 ✓. count 3.
• i = 2: j = 2 → 2 ✓; j = 1 → 10 ✓; j = 0 → 100 ✗ → stop. count 5.
• i = 3: 6 ✓, 12 ✓, 60 ✓, then 600 ✗ → stop. count 8.

Why we can break the moment it fails

Once [10, 5, 2, 6] has product ≥ k, could stretching it further (say there were one more 5 on the left) bring it back under k? No. Multiplying by a number ≥ 1 can never make the product smaller. So every longer subarray in this direction also fails. There's no point continuing → break.

5Approach steps

1. If k ≤ 1, return 0.
2. count = 0.
3. For each end index i from 0 to n − 1: set product = 1.
4. For j from i down to 0: multiply in nums[j].
5. If product < k, count it. Otherwise break.
6. Return count.

6Code (Python)

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:                          # no product can be < 1
            return 0
        n = len(nums)
        count = 0
        for i in range(n):                  # subarrays that END at i
            product = 1                     # fresh product, starts at 1
            for j in range(i, -1, -1):      # j walks left: i, i-1, ..., 0
                product *= nums[j]          # product of nums[j..i]
                if product < k:
                    count += 1
                else:
                    break                   # longer ones are even bigger
        return count

7Code line by line

8Dry run (hand table)

nums = [10, 5, 2, 6], k = 100. Each row is one end index i; the products are listed as j walks left.

Final answer: 8 ✓. Notice the "valid ones" column: for each end, the valid subarrays are a block of consecutive starts right next to the end. Keep that in mind for Part B.

9Complexity & remember

• Time O(n²): for i the inner loop runs up to i + 1 times, so in total up to 1 + 2 + … + n = n(n+1)/2.
• Space O(1): just a few variables.

The teacher notes that this code actually gets accepted, but slowly. The reason it doesn't always hit n²: the break often stops j early (for example, if the first two numbers already multiply past k, j never goes further). It's still O(n²) in the worst case (think k = 10⁶ with all ones), and an interviewer will definitely ask for better.

Part B · Optimal: sliding window + count += right − left + 1

LeetCode 713

1The question again, with the new goal

Same question: count subarrays with product < k. The new goal is one pass, O(n), where both pointers only move forward.

2Choosing the pattern (what the constraints tell us now)

The teacher goes through her four patterns:

• Two pointers ✗: needs a sorted array and only cares about two particular points. Ours isn't sorted, and we need everything in between.
• Sliding window ✓: used when we care about everything between two points. A subarray's product depends on every element inside it, so this fits.
• Prefix sum ✗: it's built for continuous sums. We want a product, so she sets it aside.
• Kadane's ✗: for the maximum sum when negatives exist. There are no negatives here, and we're counting, not maximising.

Also from the constraints: n up to 3·10⁴ → we want O(n). And numbers ≥ 1 → the product is monotonic (grows when we add, shrinks when we remove), which is exactly what sliding window needs.

3Intuition: expand while it's fine, shrink when it breaks

Both left and right start at index 0. We keep a running product of the window, starting at 1.

• Expansion phase: move right forward and multiply in nums[right]. As long as the product stays < k, keep expanding.
• Shrinking phase: the moment the product becomes ≥ k, the window is invalid. Remove elements from the left side (divide them out, move left forward) until the product is < k again.
• Then, with the window valid again, count how many valid subarrays end at right, and expand again.

4Building the logic from examples

The big question: why count += right − left + 1?

The teacher builds this slowly on a separate little array, [2, 3, 5, 6], pretending every subarray is valid (imagine a huge k) so we only focus on counting. The idea: each time right moves, count only the new subarrays, the ones that end at right. The older ones (ending earlier) were already counted on earlier steps.

Total 1 + 2 + 3 + 4 = 10, and indeed an array of 4 elements has exactly 10 subarrays. In every row, "how many new subarrays" equals the window length right − left + 1.

Why the length? Every new subarray must end at right, and it can start at any index from left to right. There are exactly right − left + 1 such start positions, one subarray per start.

Now the real example, with the shrinking

Back to [10, 5, 2, 6], k = 100.

• right = 0: product 10 < 100 → count += 0 − 0 + 1 = 1 → ([10]).
• right = 1: product 50 < 100 → count += 1 − 0 + 1 = 2 → ([5], [10,5]). Total 3.
• right = 2: product 100. Not < 100. The teacher stops here and says: before counting the length, we should have checked the window is valid. It isn't, so we must shrink first.

Shrinking: divide, don't subtract

With sums, removing the left element means subtracting it. Here we multiplied it in, so to take it out we divide: product /= nums[left], then left += 1. Removing 10: 100 / 10 = 10, left now points at 5. Window [5, 2], product 10 < 100 → valid again → count += 2 − 1 + 1 = 2 → ([2], [5,2]). Total 5.

Finishing the example

right = 3: product 10 × 6 = 60 < 100 → no shrink → count += 3 − 1 + 1 = 3 → ([6], [2,6], [5,2,6]). Total 8 ✓.

The teacher's summary of the final count: ending at 10 → 1; ending at 5 → 2 more (3); ending at 2 → 2 more (5); ending at 6 → 3 more (8).

5Approach steps

1. If k ≤ 1, return 0.
2. left = 0, product = 1, count = 0.
3. For right from 0 to n − 1: multiply in nums[right] (expand).
4. While product ≥ k: divide out nums[left] and move left forward (shrink).
5. Now the window is valid: count += right − left + 1 (all valid subarrays ending at right).
6. Return count.

6Code (Python)

class Solution:
    def numSubarrayProductLessThanK(self, nums, k):
        if k <= 1:                          # base case: nothing can be < k
            return 0
        left = 0
        product = 1
        count = 0
        for right in range(len(nums)):
            product *= nums[right]          # expand: take nums[right] in
            while product >= k:             # invalid: shrink from the left
                product //= nums[left]      # take nums[left] out
                left += 1
            count += right - left + 1       # valid subarrays ending at right
        return count

7Code line by line

8Dry run

nums = [10, 5, 2, 6], k = 100.

The windows counted at each step (each list = all subarrays ending at right):

• step 1: [10]
• step 2: [5], [10, 5]
• step 3: [2], [5, 2] ([10, 5, 2] is not counted: 10 is outside the window)
• step 4: [6], [2, 6], [5, 2, 6] ([10, 5, 2, 6] is not counted)

The array at the key moments (yellow = window, grey = already left behind):

Final answer: 8 ✓, the same as the brute force. Compare the "+" column with the brute force's "valid ones" column: they're identical (1, 2, 2, 3). The window's left is exactly where the brute force's backwards walk would have stopped, but we find it without walking back.

9Complexity & remember

• Time O(n): right touches every index once. The inner while looks like a nested loop, but left also touches each index at most once in the whole run, and it never goes back to restart. So the total work is about n + n = 2n, which is O(n). The teacher's advice if you don't believe it: dry run it and count the moves.
• Space O(1): only left, product and count.

She submitted it and it beat about 99.8% of solutions, far faster than the O(n²) version.

Part C · Revision page

def count_with_zeros(nums, k):
    if k <= 0:
        return 0
    count, left, product, last_zero = 0, 0, 1, -1
    for right, x in enumerate(nums):
        if x == 0:                          # every subarray ending here contains the 0
            last_zero, left, product = right, right + 1, 1
            count += right + 1
            continue
        product *= x
        while product >= k and left <= right:
            product //= nums[left]
            left += 1
        # windows after the zero + subarrays that reach back over the last zero
        count += (right - left + 1) + (last_zero + 1)
    return count

s = Solution()
print(s.numSubarrayProductLessThanK([10, 5, 2, 6], 100))   # 8
print(s.numSubarrayProductLessThanK([1, 2, 3], 0))         # 0  (base case)
print(s.numSubarrayProductLessThanK([1, 1, 1], 1))         # 0  (1 is not < 1)
print(s.numSubarrayProductLessThanK([1, 1, 1], 2))         # 6  (all subarrays)
print(s.numSubarrayProductLessThanK([2, 2, 2, 50], 60))    # 7  (needs while, not if)
print(s.numSubarrayProductLessThanK([100, 200], 50))       # 0  (no valid window)
print(count_with_zeros([0, 10, 10], 50))                   # 5

Based on this video: Subarray Product Less Than K | Sliding Window