How do you solve Subarray Product Less Than K?

Use two pointers, left and right, to define a sliding window. Initialize product to 1. Iterate right over the array, multiplying product by nums[right]. While product >= k, divide product by nums[left] and increment left to shrink the window. At each right, add right - left + 1 to the answer, representing all valid subarrays ending at right. Return the accumulated answer after processing all elements.

Subarray Product Less Than K

Q: What is the time complexity of Subarray Product Less Than K?

O(n). Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer shrinks it. Multiplications and divisions are constant time operations.

Q: What pattern does Subarray Product Less Than K use?

The Pattern: Sliding Window (Variable Size with Multiplicative Constraint) The Heuristic: When counting contiguous subarrays constrained by a product or sum, maintain a window that expands greedily and contracts only when the constraint is violated, enabling O(n) enumeration of all valid subarrays by counting the window size at each step.

Medium Sliding Window

Problem

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 ≤ 3 * 10⁴
1 ≤ nums[i] ≤ 1000
0 ≤ k ≤ 10⁶

Example

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

Output: 8

The brute-force approach would check every subarray and calculate its product, which is O(n²) and inefficient. Instead, the algorithm uses a sliding window to maintain a product of elements within a window. Starting with left and right pointers at the beginning, it expands the right pointer, multiplying the current product by nums[right]. If the product becomes greater than or equal to k, it shrinks the window from the left by dividing out nums[left] and moving left forward until the product is less than k again. At each step, the number of valid subarrays ending at right is right - left + 1, which accumulates the count. This approach efficiently counts all valid subarrays in O(n) time.

Approach

Straightforward Solution

A brute-force approach enumerates all subarrays and calculates their products, resulting in O(n²) time complexity, which is too slow for large inputs.

Core Observation

Since all elements are positive, expanding the window always increases the product and shrinking it always decreases it. Therefore, once the product reaches or exceeds k, the only way to restore a valid window is to move the left pointer forward until the product drops below k again. This behavior is what allows a linear-time sliding-window solution.

Path to Optimal

Preview

Recognizing that the problem asks for contiguous subarrays with a product constraint suggests a sliding window approach. The key insight is to maintain a window with a product less than k by expanding the right pointer and shrinking the left pointer as needed…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, left and right, to define a sliding window. Initialize product to 1…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each element is visited at most twice: once when the right pointer expands the window and once when the left pointer shrinks it. Multiplications and divisions are constant time operations.

Space

O(1)

Only a few integer variables are used to track the product, pointers, and the answer. No additional data structures scale with input size.

Pattern Spotlight

Sliding Window (Variable Size with Multiplicative Constraint)

When counting contiguous subarrays constrained by a product or sum, maintain a window that expands greedily and contracts only when the constraint is violated, enabling O(n) enumeration of all valid subarrays by counting the window size at each step.

Solution

Python

1class Solution:
  def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
      if k <= 1:
          return 0
5
      ans = left = 0
      curr = 1
8
      for right in range(len(nums)):
          curr *= nums[right]
          while curr >= k:
              curr //= nums[left]
              left += 1
              
          ans += right - left + 1
16
      return ans

Step-by-Step Solution

Handle Edge Case Where k is Less Than or Equal to 1

3if k <= 1:
4    return 0

Objective

To immediately return 0 when k is less than or equal to 1, since no positive product subarray can be strictly less than k in this case.

Key Insight

Since all nums[i] are positive integers, the smallest product of any subarray is at least 1. If k ≤ 1, no subarray product can be strictly less than k, so the answer is zero without further computation.

Interview Quick-Check

Core Logic

Recognize that k ≤ 1 is a trivial no-solution case due to positive integer constraints.

State & Boundaries

Return immediately to avoid unnecessary processing and potential division by zero.

Initialize Sliding Window State and Accumulators

To set up the initial state variables for the sliding window: answer accumulator, left pointer, and current product.

Expand Window and Adjust Left Pointer to Maintain Product Constraint

To iterate over the array with the right pointer, multiply the current product by nums[right], and shrink the window from the left while the product violates the constraint.

Accumulate Count of Valid Subarrays Ending at Current Right Index

To add the number of valid subarrays ending at the current right pointer to the answer accumulator.

Return the Total Count of Valid Subarrays

To return the accumulated count of all contiguous subarrays with product less than k.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 15 Critical

ans += right - left + 1

Add the count of valid subarrays ending at right to the answer.

The number of valid subarrays ending at right is the current window size (right - left + 1), so adding this accumulates all valid subarrays efficiently.

Line 3 Critical

if k <= 1:

Check if k is less than or equal to 1.

Since all elements are positive, no product can be less than 1, so if k ≤ 1, no valid subarray exists and the function can return 0 immediately.

Line 11 Critical

while curr >= k:

While product is greater than or equal to k, shrink window from the left.

This loop enforces the product constraint by removing elements from the left until the product is less than k again, maintaining the sliding window invariant.

Full line-by-line criticality + rationale for all 11 lines available on Pro.

Test Your Understanding

Why does adding right - left + 1 to the answer at each step correctly count all valid subarrays ending at right?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Subarray Product Less Than K from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Subarray Product Less Than K drill

or drill a free problem

1	`class Solution:`
2	`def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:`
3	`if k <= 1:`
4	`return 0`
5
6	`ans = left = 0`
7	`curr = 1`
8
9	`for right in range(len(nums)):`
10	`curr *= nums[right]`
11	`while curr >= k:`
12	`curr //= nums[left]`
13	`left += 1`
14
15	`ans += right - left + 1`
16
17	`return ans`