Subarray Product Less Than K

LeetCode 713 | Difficulty: Medium

Medium

Problem Description

Given an array of 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.

Example 1:

Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

Example 2:

Input: nums = [1,2,3], k = 0
Output: 0

Constraints:

- `1 <= nums.length <= 3 * 10^4`

- `1 <= nums[i] <= 1000`

- `0 <= k <= 10^6`

Topics: Array, Binary Search, Sliding Window, Prefix Sum

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 377 ms)

Metric	Value
Runtime	377 ms
Memory	43.9 MB
Date	2022-01-17

Solution

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

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$
Sliding Window	$O(n)$	$O(k)$
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: For each j, let opt(j) be the smallest i so that nums[i] nums[i+1] ... * nums[j] is less than k. opt is an increasing function.