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.