Subarray Product Less Than K

🎯

Subarray Product Less Than K

mediumSLIDING_WINDOWAmazonGoogle

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.

💡 This problem asks us to count the number of contiguous subarrays whose product is less than a given number. Beginners often struggle because products grow multiplicatively, making it tricky to use simple sliding window techniques that work for sums. Understanding how to adjust the window size dynamically is key.

📋

Problem Statement

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

💡

Example

Input"nums = [10, 5, 2, 6], k = 100"

Output8

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

• k = 0 → output 0 because no product can be less than 0
• k = 1 → output 0 because product of positive integers ≥ 1
• nums contains 1s → subarrays with 1s can be many and affect count
• nums length = 1 → output depends on single element vs k

⚠️

Common Mistakes

Not handling k ≤ 1 edge case

Returns incorrect count or runtime error

✅ Add early return 0 if k ≤ 1

Using integer division instead of floating point division in Python

Product does not update correctly, causing infinite loops or wrong counts

✅ Use floating point division '/' instead of integer division '//'

Not shrinking window correctly when product ≥ k

Window grows indefinitely, causing wrong counts or runtime errors

✅ Use while loop to shrink window until product < k

Counting subarrays incorrectly by adding 1 instead of (right - left + 1)

Undercounts valid subarrays

✅ Add (right - left + 1) to count at each step

Not resetting product when starting new subarray in brute force

Product accumulates incorrectly, causing wrong counts

✅ Reset product to 1 at each new start index

🧠

Brute Force (Nested Loops)

💡 Starting with brute force helps understand the problem deeply by enumerating all subarrays and checking their product. Though inefficient, it builds intuition about the problem's nature.

Intuition

Try every possible subarray, calculate its product, and count if it's less than k.

Algorithm

1. Initialize count to 0.
2. Use two nested loops: outer loop picks start index, inner loop picks end index.
3. Calculate product of elements from start to end.
4. If product < k, increment count; else break inner loop early.

💡 The nested loops and product calculation are straightforward but can be slow because we recompute products repeatedly.

</>

Code

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    count = 0
    n = len(nums)
    for start in range(n):
        product = 1
        for end in range(start, n):
            product *= nums[end]
            if product < k:
                count += 1
            else:
                break
    return count

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

Line Notes

if k <= 1:No subarray product can be less than 1 or 0, so return 0 early

for start in range(n):Outer loop selects the start index of subarray

product = 1Reset product for each new start index

for end in range(start, n):Inner loop extends subarray to the right

product *= nums[end]Update product with new element

if product < k:Check if current subarray product is valid

count += 1Increment count for valid subarray

else: breakStop extending subarray if product exceeds k

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int count = 0;
        int n = nums.length;
        for (int start = 0; start < n; start++) {
            int product = 1;
            for (int end = start; end < n; end++) {
                product *= nums[end];
                if (product < k) {
                    count++;
                } else {
                    break;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSubarrayProductLessThanK(new int[]{10,5,2,6}, 100)); // 8
    }
}

Line Notes

if (k <= 1) return 0;Early exit for impossible product conditions

for (int start = 0; start < n; start++) {Outer loop picks subarray start

int product = 1;Reset product for each start

for (int end = start; end < n; end++) {Inner loop extends subarray

product *= nums[end];Update product with new element

if (product < k) {Check if product is valid

count++;Count valid subarray

else { break; }Stop if product too large

#include <iostream>
#include <vector>
using namespace std;

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int count = 0;
    int n = nums.size();
    for (int start = 0; start < n; ++start) {
        int product = 1;
        for (int end = start; end < n; ++end) {
            product *= nums[end];
            if (product < k) {
                ++count;
            } else {
                break;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {10,5,2,6};
    cout << numSubarrayProductLessThanK(nums, 100) << endl; // 8
    return 0;
}

Line Notes

if (k <= 1) return 0;No valid subarray if k ≤ 1

for (int start = 0; start < n; ++start) {Start index of subarray

int product = 1;Reset product for each start

for (int end = start; end < n; ++end) {Extend subarray to right

product *= nums[end];Multiply product by new element

if (product < k) {Check if product is valid

++count;Increment count for valid subarray

else { break; }Stop if product too large

function numSubarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    let count = 0;
    const n = nums.length;
    for (let start = 0; start < n; start++) {
        let product = 1;
        for (let end = start; end < n; end++) {
            product *= nums[end];
            if (product < k) {
                count++;
            } else {
                break;
            }
        }
    }
    return count;
}

// Test
console.log(numSubarrayProductLessThanK([10,5,2,6], 100)); // 8

Line Notes

if (k <= 1) return 0;No subarray product can be less than 1 or 0

for (let start = 0; start < n; start++) {Outer loop picks start index

let product = 1;Reset product for each start

for (let end = start; end < n; end++) {Inner loop extends subarray

product *= nums[end];Update product with new element

if (product < k) {Check if product is valid

count++;Count valid subarray

else { break; }Stop if product too large

⏱

Complexity

TimeO(n^2)

SpaceO(1)

Two nested loops each can run up to n times, so O(n^2). Product calculation is done incrementally, so no extra space.

💡 For n=1000, this means up to 1,000,000 operations, which is too slow for large inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for big arrays but is useful to understand the problem and correctness before optimizing.

🧠

Sliding Window (Two Pointers)

💡 This approach uses a variable-size sliding window to efficiently count subarrays by maintaining a product and adjusting window boundaries, avoiding repeated product calculations.

Intuition

Expand the right pointer to include elements while product < k, and shrink from the left when product ≥ k, counting valid subarrays ending at each right pointer.

Algorithm

1. Initialize product = 1, left = 0, count = 0.
2. Iterate right pointer over array:
3. Multiply product by nums[right].
4. While product ≥ k and left ≤= right, divide product by nums[left] and increment left.
5. Add (right - left + 1) to count (all subarrays ending at right with product < k).

💡 The key insight is that all subarrays ending at right and starting between left and right are valid if product < k.

</>

Code

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

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

Line Notes

if k <= 1:No valid subarray if k ≤ 1

product = 1Initialize product for sliding window

left = 0Left pointer starts at 0

for right in range(len(nums))Right pointer moves forward

product *= nums[right]Include new element in product

while product >= k and left <= right:Shrink window from left if product too large

product /= nums[left]Remove left element from product

left += 1Move left pointer right

count += right - left + 1Count all valid subarrays ending at right

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        int product = 1, count = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k && left <= right) {
                product /= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSubarrayProductLessThanK(new int[]{10,5,2,6}, 100)); // 8
    }
}

Line Notes

if (k <= 1) return 0;No valid subarray if k ≤ 1

int product = 1, count = 0, left = 0;Initialize variables for sliding window

for (int right = 0; right < nums.length; right++) {Right pointer moves forward

product *= nums[right];Include new element in product

while (product >= k && left <= right) {Shrink window from left if product too large

product /= nums[left++];Remove left element and move left pointer

count += right - left + 1;Count valid subarrays ending at right

#include <iostream>
#include <vector>
using namespace std;

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    int product = 1, count = 0, left = 0;
    for (int right = 0; right < nums.size(); ++right) {
        product *= nums[right];
        while (product >= k && left <= right) {
            product /= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

int main() {
    vector<int> nums = {10,5,2,6};
    cout << numSubarrayProductLessThanK(nums, 100) << endl; // 8
    return 0;
}

Line Notes

if (k <= 1) return 0;No valid subarray if k ≤ 1

int product = 1, count = 0, left = 0;Initialize sliding window variables

for (int right = 0; right < nums.size(); ++right) {Right pointer moves forward

product *= nums[right];Include new element in product

while (product >= k && left <= right) {Shrink window from left if product too large

product /= nums[left++];Remove left element and move left pointer

count += right - left + 1;Count valid subarrays ending at right

function numSubarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    let product = 1, count = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k && left <= right) {
            product /= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

// Test
console.log(numSubarrayProductLessThanK([10,5,2,6], 100)); // 8

Line Notes

if (k <= 1) return 0;No valid subarray if k ≤ 1

let product = 1, count = 0, left = 0;Initialize variables for sliding window

for (let right = 0; right < nums.length; right++) {Right pointer moves forward

product *= nums[right];Include new element in product

while (product >= k && left <= right) {Shrink window from left if product too large

product /= nums[left++];Remove left element and move left pointer

count += right - left + 1;Count valid subarrays ending at right

⏱

Complexity

TimeO(n)

SpaceO(1)

Each element is visited at most twice (once when right pointer moves forward, once when left pointer moves forward), so linear time.

💡 For n=100000, this means about 200000 operations, which is efficient for large inputs.

Interview Verdict: Accepted and optimal

This approach is efficient and suitable for interview coding, demonstrating mastery of sliding window technique.

🧠

Sliding Window with Floating Point Product

💡 This approach is a variant that uses floating point division to handle large products safely, useful when product might overflow integer limits.

Intuition

Use double precision floating point to maintain product and adjust window similarly to the integer sliding window approach.

Algorithm

1. Initialize product = 1.0, left = 0, count = 0.
2. Iterate right pointer over array:
3. Multiply product by nums[right].
4. While product ≥ k and left ≤= right, divide product by nums[left] and increment left.
5. Add (right - left + 1) to count.

💡 Same logic as integer sliding window but using floating point to avoid overflow.

</>

Code

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

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

Line Notes

product = 1.0Use floating point to avoid overflow

product *= nums[right]Multiply product by new element

while product >= k and left <= right:Shrink window if product too large

product /= nums[left]Divide product by left element

count += right - left + 1Count valid subarrays ending at right

public class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k <= 1) return 0;
        double product = 1.0;
        int count = 0, left = 0;
        for (int right = 0; right < nums.length; right++) {
            product *= nums[right];
            while (product >= k && left <= right) {
                product /= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSubarrayProductLessThanK(new int[]{10,5,2,6}, 100)); // 8
    }
}

Line Notes

double product = 1.0;Use double to avoid overflow

product *= nums[right];Multiply product by new element

while (product >= k && left <= right) {Shrink window if product too large

product /= nums[left++];Divide product by left element

count += right - left + 1;Count valid subarrays ending at right

#include <iostream>
#include <vector>
using namespace std;

int numSubarrayProductLessThanK(vector<int>& nums, int k) {
    if (k <= 1) return 0;
    double product = 1.0;
    int count = 0, left = 0;
    for (int right = 0; right < nums.size(); ++right) {
        product *= nums[right];
        while (product >= k && left <= right) {
            product /= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

int main() {
    vector<int> nums = {10,5,2,6};
    cout << numSubarrayProductLessThanK(nums, 100) << endl; // 8
    return 0;
}

Line Notes

double product = 1.0;Use double to avoid overflow

product *= nums[right];Multiply product by new element

while (product >= k && left <= right) {Shrink window if product too large

product /= nums[left++];Divide product by left element

count += right - left + 1;Count valid subarrays ending at right

function numSubarrayProductLessThanK(nums, k) {
    if (k <= 1) return 0;
    let product = 1.0, count = 0, left = 0;
    for (let right = 0; right < nums.length; right++) {
        product *= nums[right];
        while (product >= k && left <= right) {
            product /= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

// Test
console.log(numSubarrayProductLessThanK([10,5,2,6], 100)); // 8

Line Notes

let product = 1.0, count = 0, left = 0;Use floating point to avoid overflow

product *= nums[right];Multiply product by new element

while (product >= k && left <= right) {Shrink window if product too large

product /= nums[left++];Divide product by left element

count += right - left + 1;Count valid subarrays ending at right

⏱

Complexity

TimeO(n)

SpaceO(1)

Same as integer sliding window, linear time and constant space.

💡 This approach is safe for large products but slightly slower due to floating point operations.

Interview Verdict: Accepted, safer for large inputs

Use this if integer overflow is a concern; otherwise integer sliding window is preferred for speed.

📊

All Approaches - One-Glance Tradeoffs

💡 The sliding window approach (Approach 2) is the best to code in interviews due to its optimal time and space complexity and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window (Two Pointers)	O(n)	O(1)	No	N/A	Code this approach for optimal solution
3. Sliding Window with Floating Point	O(n)	O(1)	No	N/A	Use if integer overflow is a concern

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the sliding window approach, and prepare to explain your reasoning clearly in interviews.

How to Present

Clarify the problem and constraints, especially about positive integers and k.Explain the brute force approach to show understanding of the problem.Introduce the sliding window approach as an optimization.Write clean code for the sliding window solution.Test with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to optimize from brute force to linear time, handle edge cases, and write clean, bug-free code.

Common Follow-ups

• What if nums contains zeros? → zeros reset product to zero, so window resets.
• Can you handle negative numbers? → No, product sign changes complicate sliding window.
• What if k is very large? → Sliding window still works efficiently.
• Can you find the shortest subarray with product ≥ k? → Different problem, requires different approach.

💡 These follow-ups test your understanding of problem constraints and ability to adapt the solution.

🔍

Pattern Recognition

When to Use

1) Problem asks for counting or finding subarrays with a product or sum constraint. 2) Input array has positive integers. 3) Need to find contiguous subarrays. 4) Constraints require better than O(n^2) solution.

Signature Phrases

product of all the elements in the subarray is less than knumber of contiguous subarrays

NOT This Pattern When

Problems involving non-contiguous subsequences or requiring DP for overlapping subproblems.

Similar Problems

Minimum Size Subarray Sum - similar sliding window for sum constraintLongest Substring Without Repeating Characters - variable size window for substring constraints

Practice

1. Consider the following Python function implementing the sliding window approach to find the maximum sum subarray of size k. What is the value of window_sum after the second iteration of the for-loop when called with arr = [1, 3, 2, 6] and k = 2?

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

easy

A. 8

B. 9

C. 5

D. 7

Solution

1. Step 1: Initialize variables

   window_sum = sum(arr[:2]) = 1 + 3 = 4, max_sum = 4

2. Step 2: Iterate and update window_sum

   First iteration (i=2): window_sum = 4 + arr[2] - arr[0] = 4 + 2 - 1 = 5 Second iteration (i=3): window_sum = 5 + arr[3] - arr[1] = 5 + 6 - 3 = 8

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   window_sum after second iteration is 8 [OK]

Hint: Track window_sum updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop index
• Confusing window_sum with max_sum
• Forgetting to subtract the element leaving the window

2. Suppose the bookstore owner can be calmed multiple times, each time for a continuous window of length X, possibly overlapping. How should the algorithm be modified to find the maximum total satisfied customers under this new condition?

hard

A. Sum all customers since calming multiple times removes grumpiness entirely

B. Run the original sliding window once and multiply the max extra by the number of windows allowed

C. Use a greedy approach to pick the top non-overlapping windows with highest extra satisfaction

D. Use dynamic programming to select multiple possibly overlapping windows maximizing total extra satisfaction

Solution

1. Step 1: Understand new problem constraints

   Multiple calming windows allowed, possibly overlapping, so simple sliding window max sum is insufficient.

2. Step 2: Identify suitable approach

   Dynamic programming can consider multiple windows and their overlaps to maximize total extra satisfaction.

3. Step 3: Why other options fail

   Multiplying max extra ignores overlaps; greedy picking non-overlapping windows misses overlaps; summing all customers ignores grumpy states.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DP handles multiple overlapping windows optimally [OK]

Hint: Multiple overlapping windows -> DP needed [OK]

Common Mistakes:

• Assuming single window solution suffices
• Ignoring overlaps in greedy
• Over-simplifying to sum all customers

3. Suppose you want to find the longest substring with at most k distinct characters, but now characters can be reused infinitely many times and the string is extremely long. Which modification to the sliding window approach is necessary to handle this efficiently?

hard

A. Use a frequency map with counts and shrink window when counts exceed k distinct characters, ignoring last seen positions

B. Maintain an ordered dictionary of last seen indices and shrink window as usual; no change needed

C. Use a frequency map and shrink the window only when distinct characters exceed k, ignoring last seen indices

D. Switch to a brute force approach since reuse breaks sliding window assumptions

Solution

1. Step 1: Understand reuse impact

   When characters can be reused infinitely, tracking last seen indices is insufficient; frequency counts are needed.

2. Step 2: Modify approach

   Use a frequency map to count occurrences and shrink window when distinct characters exceed k, ignoring last seen positions.

3. Step 3: Confirm efficiency

   This approach maintains O(n) time and handles reuse correctly.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency map with counts is required for reuse scenarios [OK]

Hint: Frequency counts needed when characters can be reused infinitely [OK]

Common Mistakes:

• Assuming last seen indices suffice for reuse
• Thinking brute force is necessary

4. 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

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