Subarray Product Less Than K

▶

Steps

setup

Initialize variables

Initialize product to 1.0, left pointer to 0, and count to 0 before starting iteration.

💡 Setting up these variables is essential to track the product of the current window and count valid subarrays.

Line:

product = 1.0
count = 0
left = 0

💡 We start with an empty window and no subarrays counted.

expand

Expand window to include nums[0] = 10

Move right pointer to 0 and multiply product by nums[0] (10). Product becomes 10.

💡 Expanding the window includes the first element, starting to form subarrays.

Line:

product *= nums[right]  # product = 1.0 * 10

💡 The window now covers [10] with product 10 < 100, so it's valid.

record_answer

Count subarrays ending at right=0

Add (right - left + 1) = 1 to count. Count becomes 1.

💡 Each valid window corresponds to multiple subarrays ending at right pointer.

Line:

count += right - left + 1  # count = 0 + 1

💡 The single element subarray [10] is counted.

expand

Expand window to include nums[1] = 5

Move right pointer to 1 and multiply product by nums[1] (5). Product becomes 50.

💡 Expanding window to include next element to find more valid subarrays.

Line:

product *= nums[right]  # product = 10 * 5

💡 Window now covers [10, 5] with product 50 < 100, still valid.

record_answer

Count subarrays ending at right=1

Add (right - left + 1) = 2 to count. Count becomes 3.

💡 Counting subarrays [5] and [10,5] ending at index 1.

Line:

count += right - left + 1  # count = 1 + 2

💡 Two new valid subarrays are added to the total count.

expand

Expand window to include nums[2] = 2

Move right pointer to 2 and multiply product by nums[2] (2). Product becomes 100.

💡 Including next element increases product to boundary value.

Line:

product *= nums[right]  # product = 50 * 2

💡 Product equals k, so window is invalid and needs shrinking.

shrink

Shrink window from left to reduce product

Product (100) ≥ k, divide product by nums[left] (10), product becomes 10.0. Increment left to 1.

💡 Shrinking window removes leftmost element to restore product < k.

Line:

product /= nums[left]  # product = 100 / 10
left += 1

💡 Removing 10 from window reduces product to valid range.

record_answer

Count subarrays ending at right=2

Add (right - left + 1) = 2 to count. Count becomes 5.

💡 Counting subarrays [2] and [5,2] ending at index 2.

Line:

count += right - left + 1  # count = 3 + 2

💡 Two more valid subarrays are added.

expand

Expand window to include nums[3] = 6

Move right pointer to 3 and multiply product by nums[3] (6). Product becomes 60.

💡 Expanding window to include last element.

Line:

product *= nums[right]  # product = 10 * 6

💡 Window covers [5, 2, 6] with product 60 < 100, valid.

record_answer

Count subarrays ending at right=3

Add (right - left + 1) = 3 to count. Count becomes 8.

💡 Counting subarrays [6], [2,6], and [5,2,6] ending at index 3.

Line:

count += right - left + 1  # count = 5 + 3

💡 Three new valid subarrays added, total count is 8.

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0  # STEP 1
    count = 0      # STEP 1
    left = 0       # STEP 1
    for right in range(len(nums)):
        product *= nums[right]  # STEP 2,4,6,9
        while product >= k and left <= right:  # STEP 7
            product /= nums[left]  # STEP 7
            left += 1              # STEP 7
        count += right - left + 1  # STEP 3,5,8,10
    return count

if __name__ == '__main__':
    print(numSubarrayProductLessThanK([10,5,2,6], 100))  # Expected output: 8

📊

Subarray Product Less Than K - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the window adjusts to maintain the product constraint, which is difficult to grasp from code alone.

expand

L ▼

10

0

5

1

2

2

6

3

Metric: 1

Answer: 0

expand

L=R

10

0

5

1

2

2

6

3

Window: [10]

Metric: 10

Answer: 0

record_answer

L=R

10

0

5

1

2

2

6

3

Window: [10]

Metric: 10

Answer: 1

expand

L ▼

10

0

R ▼

5

1

2

2

6

3

Window: [10, 5]

Metric: 50

Answer: 1

record_answer

L ▼

10

0

R ▼

5

1

2

2

6

3

Window: [10, 5]

Metric: 50

Answer: 3

expand

L ▼

10

0

5

1

R ▼

2

2

6

3

Window: [10, 5, 2]

Metric: 100

Answer: 3

shrink

10

0

L ▼

5

1

R ▼

2

2

6

3

Window: [5, 2]

Metric: 10

Answer: 3

record_answer

10

0

L ▼

5

1

R ▼

2

2

6

3

Window: [5, 2]

Metric: 10

Answer: 5

expand

10

0

L ▼

5

1

2

2

R ▼

6

3

Window: [5, 2, 6]

Metric: 60

Answer: 5

record_answer

10

0

L ▼

5

1

2

2

R ▼

6

3

Window: [5, 2, 6]

Metric: 60

Answer: 8

Key Takeaways

✓ The sliding window dynamically expands and shrinks to maintain the product constraint.

This dynamic adjustment is hard to visualize from code but becomes clear when watching the window boundaries and product update step-by-step.

✓ Counting subarrays by adding (right - left + 1) at each step efficiently accumulates all valid subarrays ending at right.

This insight explains why the algorithm runs in linear time and avoids enumerating all subarrays explicitly.

✓ When the product hits or exceeds k, the window shrinks from the left until the product is valid again.

Seeing the product division and left pointer increment in action clarifies the pruning mechanism that keeps the window valid.

Practice

1. You are given two strings s and p. You need to find all start indices in s where a substring is an anagram of p. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings of length equal to p and comparing frequency maps.

B. Sliding window with frequency map comparison and count matching optimization.

C. Dynamic programming to build a table of substring matches based on character counts.

D. Greedy approach by sorting each substring and comparing with sorted p.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding all anagrams of p in s efficiently, ideally in linear time.

2. Step 2: Evaluate algorithmic approaches

   Brute force (checking all substrings) is O(n*m), sorting each substring is O(n*m log m), and DP is not naturally suited here. Sliding window with frequency map and count matching optimizes to O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with count matching is known optimal for fixed-size anagram search [OK]

Hint: Sliding window with count matching -> O(n) time [OK]

Common Mistakes:

• Thinking sorting each substring is efficient enough
• Assuming DP applies directly
• Using brute force for large inputs

2. Consider the following Python code implementing the sliding window with count matching optimization to find all anagrams of p in s. What is the final returned list when s = "cbaebabacd" and p = "abc"?

easy

A. [0, 1, 6]

B. [0, 6, 7]

C. [0, 6, 8]

D. [0, 6]

Solution

1. Step 1: Trace first window (indices 0 to 2)

   Substring "cba" is an anagram of "abc", so index 0 is added.

2. Step 2: Slide window and check matches

   Next valid anagram found at index 6 ("bac"). No other windows match all counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known example output matches [0, 6] [OK]

Hint: Anagrams appear at indices 0 and 6 only [OK]

Common Mistakes:

• Including indices where substring is not full anagram
• Off-by-one errors in window boundaries

3. You manage a bookstore where customers arrive each minute, but the owner sometimes gets grumpy and ignores customers during certain minutes. You can choose a continuous time window of fixed length to calm the owner, making them satisfied during that window. Which algorithmic approach guarantees finding the maximum total satisfied customers?

easy

A. Sliding window to find the window maximizing extra satisfied customers plus base satisfaction

B. Dynamic programming over all subsets of minutes to maximize satisfaction

C. Greedy approach selecting the largest single minute with grumpy customers

D. Sorting customers by count and picking top X minutes regardless of continuity

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting a continuous window of fixed length to maximize extra satisfaction, so continuity matters.

2. Step 2: Identify suitable algorithm

   Sliding window efficiently finds the maximum sum of grumpy customers in any continuous window, combined with base satisfaction from non-grumpy minutes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window handles continuous windows optimally [OK]

Hint: Continuous window optimization -> sliding window [OK]

Common Mistakes:

• Thinking greedy picking largest single minute suffices
• Ignoring continuity of window
• Trying DP over subsets unnecessarily

4. The following code attempts to solve the fruits problem using a sliding window. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def totalFruit(fruits):
    basket = {}
    left = 0
    max_length = 0
    for right in range(len(fruits)):
        basket[fruits[right]] = basket.get(fruits[right], 0) + 1
        while len(basket) > 2:
            basket[fruits[left]] -= 1
            # BUG: Missing removal of fruit type when count reaches zero
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

medium

A. Line where basket[fruits[right]] is incremented

B. Line where basket[fruits[left]] is decremented

C. Line where fruit type is deleted when count reaches zero (missing here)

D. Line where max_length is updated

Solution

1. Step 1: Identify missing removal of fruit type

   When basket[fruits[left]] count reaches zero, the fruit type must be deleted to keep basket size accurate.

2. Step 2: Consequence of missing deletion

   Without deletion, basket size remains > 2 incorrectly, causing unnecessary window shrinking and wrong max length.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Deleting fruit type when count hits zero is essential [OK]

Hint: Check if fruit count zero triggers deletion [OK]

Common Mistakes:

• Forgetting to delete fruit type
• Shrinking window too early
• Updating max_length incorrectly

5. Suppose the problem is modified so that the array can contain negative numbers as well as positive numbers. Which of the following statements about applying the sliding window approach to find the minimum size subarray sum ≥ target is true?

hard

A. Sliding window fails because negative numbers can cause the sum to decrease unpredictably, breaking the monotonic window property

B. Sorting the array first allows sliding window to work correctly with negatives

C. Sliding window still works unchanged because the sum can be adjusted dynamically

D. Prefix sums with binary search is invalid because sums can be negative

Solution

1. Step 1: Understand sliding window assumptions

   Sliding window relies on sums increasing as right pointer moves forward and shrinking from left to reduce sum, which requires all positive numbers.

2. Step 2: Effect of negative numbers

   Negative numbers can decrease sum inside the window unpredictably, so shrinking or expanding window does not guarantee monotonic sum changes, breaking the approach.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window requires non-negative numbers for correctness [OK]

Hint: Negative numbers break sliding window monotonic sum property [OK]

Common Mistakes:

• Assuming sliding window works with negatives
• Thinking sorting fixes contiguous subarray sums
• Believing prefix sums binary search fails with negatives