Subarray Product Less Than K

📋

Problem

Imagine you are analyzing a stream of sales data, and you want to find how many consecutive days had a combined sales product less than a certain threshold to identify stable periods.

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.

1 ≤ nums.length ≤ 10^51 ≤ nums[i] ≤ 10000 ≤ k ≤ 10^6

Edge cases: k = 0 → output 0 because no product can be less than 0k = 1 → output 0 because product of positive integers ≥ 1nums contains 1s → subarrays with 1s can be many and affect count

</>

IDE

def numSubarrayProductLessThanK(nums: list[int], k: int) -> int:public int numSubarrayProductLessThanK(int[] nums, int k)int numSubarrayProductLessThanK(vector<int>& nums, int k)function numSubarrayProductLessThanK(nums, k)

def numSubarrayProductLessThanK(nums, k):
    # Write your solution here
    pass

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    // Write your solution here
    return 0;
}

function numSubarrayProductLessThanK(nums, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Too large countNot shrinking window when product >= k, causing overcounting.✅ Add while loop to move left pointer and divide product until product < k.

Wrong: Zero count when k > 1Returning 0 immediately for k <= 1 without checking product properly.✅ Return 0 only if k <= 1; otherwise, proceed with sliding window.

Wrong: Crash or errorNot handling empty input array properly.✅ Add check for empty array and return 0 immediately.

Wrong: Incorrect count due to non-contiguous subarraysTreating problem like unbounded knapsack or allowing non-contiguous subarrays.✅ Use sliding window to count only contiguous subarrays.

Wrong: TLE on large inputUsing brute force O(n^2) nested loops approach.✅ Implement O(n) sliding window approach with two pointers.

✓

Test Cases

Focus on handling edge cases like empty input and single elements correctly.

Watch out for common algorithmic traps like greedy approaches and continuity assumptions.

Optimize your solution to linear time using sliding window to handle large inputs.

t1_01basic

Input{"nums":[10,5,2,6],"k":100}

Expected8

⏱ Performance - must finish in 2000ms

The 8 subarrays are: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]. Each has product less than 100.

💡 Consider using a sliding window to track the product of elements.

💡 Use two pointers to expand and shrink the window while product < k.

💡 Count subarrays ending at each right pointer as (right - left + 1).

Why it failed: Incorrect count likely due to not shrinking window when product >= k. Fix by moving left pointer and dividing product accordingly.

✓ Correctly counts all subarrays with product less than k using sliding window.

t1_02basic

Input{"nums":[1,2,3,4],"k":10}

Expected7

⏱ Performance - must finish in 2000ms

Subarrays with product < 10 are: [1], [2], [3], [4], [1,2], [2,3], [3,4].

💡 Remember to count all subarrays ending at each index with product < k.

💡 Sliding window approach helps efficiently track product and window size.

💡 Increment count by window size (right - left + 1) after adjusting window.

Why it failed: If count is too low, likely missing subarrays ending at current right pointer. Fix by adding (right - left + 1) to count each step.

✓ Correctly counts all valid subarrays using sliding window.

t2_01edge

Input{"nums":[],"k":10}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no subarrays, so count is 0.

💡 Check how your code handles empty input arrays.

💡 Make sure to return 0 immediately if nums is empty.

💡 Avoid accessing elements when array length is zero.

Why it failed: Code crashes or returns non-zero for empty input. Fix by adding a check for empty array and returning 0.

✓ Correctly returns 0 for empty input.

t2_02edge

Input{"nums":[5],"k":5}

Expected0

⏱ Performance - must finish in 2000ms

Single element 5 is not less than k=5, so no valid subarrays.

💡 Check single element arrays where element >= k.

💡 Remember product must be strictly less than k.

💡 Return 0 if single element is >= k.

Why it failed: Returns 1 instead of 0 for single element equal to or greater than k. Fix by checking product < k strictly.

✓ Correctly returns 0 when single element >= k.

t2_03edge

Input{"nums":[1,1,1],"k":2}

Expected6

⏱ Performance - must finish in 2000ms

All subarrays have product 1 which is less than 2. Number of subarrays = n*(n+1)/2 = 6.

💡 Consider how multiple 1s affect the product and count.

💡 All subarrays of 1s have product 1, so all count if k > 1.

💡 Count all subarrays: n*(n+1)/2 when product always < k.

Why it failed: Fails to count all subarrays when elements are 1. Fix by not shrinking window unnecessarily when product < k.

✓ Correctly counts all subarrays when product always < k.

t3_01corner

Input{"nums":[10,5,2,6],"k":8}

Expected3

⏱ Performance - must finish in 2000ms

Subarrays with product < 8 are: [5], [2], [6].

💡 Check if your solution handles cases where k is small and excludes many subarrays.

💡 Sliding window must shrink aggressively when product >= k.

💡 Ensure window moves left pointer correctly to maintain product < k.

Why it failed: Incorrect count due to not shrinking window enough when product >= k. Fix by moving left pointer until product < k.

✓ Correctly handles small k values by shrinking window properly.

t3_02corner

Input{"nums":[1,2,3,4],"k":7}

Expected7

⏱ Performance - must finish in 2000ms

Subarrays with product < 7 are: [1], [2], [3], [4], [1,2], [2,3].

💡 Beware of greedy approaches that pick largest subarray without shrinking.

💡 Sliding window must adjust left pointer to keep product < k.

💡 Count subarrays ending at each right index correctly.

Why it failed: Greedy approach overcounts by not shrinking window properly. Fix by adjusting left pointer until product < k.

✓ Correctly counts subarrays by adjusting window size dynamically.

t3_03corner

Input{"nums":[2,5,3,10],"k":30}

Expected6

⏱ Performance - must finish in 2000ms

Subarrays with product < 30 are: [2], [5], [3], [10], [2,5], [5,3].

💡 Check if your solution mistakenly treats problem as unbounded knapsack or allows repeated elements.

💡 Ensure product is computed for contiguous subarrays only.

💡 Use sliding window to count contiguous subarrays with product < k.

Why it failed: Incorrect count due to treating problem as unbounded or non-contiguous. Fix by using sliding window for contiguous subarrays.

✓ Correctly counts contiguous subarrays with product less than k.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10],"k":1000000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 tests O(n) sliding window solution completes within time limit.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use sliding window with two pointers for O(n) time complexity.

💡 Maintain product and adjust window size dynamically.

Why it failed: TLE due to nested loops O(n^2) approach. Fix by implementing O(n) sliding window solution.

✓ Solution runs efficiently in O(n) time for large inputs.

Practice

1. You are given an array representing types of fruits in a row of trees. You want to collect fruits by choosing a contiguous segment of trees such that you only pick fruits of at most two different types. Which algorithmic approach guarantees finding the longest such segment efficiently?

easy

A. Sorting the array and then using two pointers to find longest subarray with two distinct values

B. Greedy approach that picks fruits until a third type appears, then restarts from the next tree

C. Dynamic programming to store longest segments ending at each index with at most two fruit types

D. Sliding window with a hash map to track counts of fruit types and dynamically adjust window size

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest contiguous subarray with at most two distinct fruit types.

2. Step 2: Identify suitable algorithm

   Sliding window with a hash map efficiently tracks counts of fruit types in the current window and adjusts window size when more than two types appear, ensuring O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with hashmap is classic for variable-size window problems [OK]

Hint: Sliding window with hashmap tracks counts dynamically [OK]

Common Mistakes:

• Assuming greedy restart always works
• Using DP unnecessarily
• Sorting breaks contiguous constraint

2. Consider the following code snippet implementing the sliding window approach to find the maximum average subarray of size k. Given nums = [4, 2, 1, 7] and k = 2, what is the value of max_sum after the loop completes?

easy

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Initialize sums

   Initial window sum = nums[0] + nums[1] = 4 + 2 = 6, so max_sum = 6.

2. Step 2: Iterate through array

   i=2: current_sum = 6 + nums[2] - nums[0] = 6 + 1 - 4 = 3 (max_sum stays 6) i=3: current_sum = 3 + nums[3] - nums[1] = 3 + 7 - 2 = 8 (max_sum updated to 8)

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Max sum found is 8, which matches 8 [OK]

Hint: Track current_sum updates carefully at each iteration [OK]

Common Mistakes:

• Off-by-one errors in indices
• Confusing current_sum with max_sum

3. What is the time complexity of the optimal sliding window solution that uses a queue to track zero positions for the Max Consecutive Ones III problem, given an input array of length n and integer k?

medium

A. O(n * k) because each zero can cause multiple window shifts

B. O(n) because each element is visited at most twice by the two pointers

C. O(n^2) because the queue operations inside the loop cause nested behavior

D. O(k) because the queue size is limited to k zeros only

Solution

1. Step 1: Identify loop behavior

   The right pointer iterates over all n elements once, and the left pointer only moves forward when zeros exceed k.

2. Step 2: Analyze queue operations and pointer moves

   Each zero index is enqueued once and dequeued once, so total operations are O(n). However, each zero can cause the left pointer to move multiple times in worst case, leading to O(n * k) complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   While the queue operations are O(n), the window shifts can multiply by k in worst cases [OK]

Hint: Consider worst-case window shifts caused by zeros [OK]

Common Mistakes:

• Assuming strictly linear without considering multiple shifts
• Confusing queue size with total operations
• Ignoring worst-case scenarios

4. What is the time complexity of the optimal sliding window maximum algorithm using a monotonic deque for an input array of size n and window size k?

medium

A. O(n * k)

B. O(n log k)

C. O(n)

D. O(k)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm iterates over each element once (O(n)). Each element is pushed and popped at most once from the deque, so total deque operations are O(n).

2. Step 2: Check if any hidden costs exist

   No nested loops or log factors; deque operations are O(1) amortized, so total time is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Amortized deque operations ensure linear time [OK]

Hint: Each element is pushed and popped at most once [OK]

Common Mistakes:

• Assuming nested loops cause O(n*k)
• Confusing max-heap complexity with deque
• Ignoring amortized cost of deque operations

5. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the substring in s must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts and require window_count[c] >= t_count[c] for all c, same as original

B. Use brute force to check all substrings since counts no longer matter

C. Sort s and t and use two pointers to find minimal substring

D. Track only presence of characters from t in the window, increment have when a character appears at least once, decrement when it disappears

Solution

1. Step 1: Understand problem change

   Since counts do not matter, only presence of each character is required, so frequency counts can be replaced by boolean presence tracking.

2. Step 2: Modify sliding window logic

   Increment have when a character from t appears first time in window, decrement when it leaves. Shrink window when all characters are present.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Tracking presence instead of counts solves the reuse variant efficiently [OK]

Hint: Track presence, not counts, when duplicates don't matter [OK]

Common Mistakes:

• Using original count-based logic
• Assuming brute force is needed
• Sorting breaks substring order