MediumArrayBinary SearchSliding WindowPrefix SumUpdated Sep 2026

713. Subarray Product Less Than K

Asked at Apple

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You get an array of positive integers nums and an integer k. Count how many contiguous subarrays have a product that is strictly less than k.

A subarray is a slice of the array with no gaps — you pick a start index and an end index and take every element between them. Single elements count as subarrays too.

Because every number is at least 1, the product only grows as you add more elements to the right. That fact is what makes a sliding window work: once the product is too big, you must drop elements from the left until it becomes small enough again.

Which slices have product under 100?

nums5*2*6 = 60 < 100105260123The slice [5,2,6] has product 60, so it counts.nums10*5*2 = 100, not < 100105260123The slice [10,5,2] has product exactly 100, so it isrejected.
Every unbroken slice of [10,5,2,6] is checked; 8 of them have a product strictly below 100.

Constraints

  • ●1 <= nums.length <= 3 * 10^4
  • ●1 <= nums[i] <= 1000
  • ●0 <= k <= 10^6

Examples

Example 1
Inputnums = [10,5,2,6], k = 100
Output8
WhyThe valid slices are [10], [5], [2], [6], [10,5], [5,2], [2,6] and [5,2,6]. Their products are 10, 5, 2, 6, 50, 10, 12 and 60 — all below 100. The slice [10,5,2] has product exactly 100, which is not strictly less than 100, so it is excluded.
Example 2
Inputnums = [1,2,3], k = 0
Output0
WhyEvery element is at least 1, so every product is at least 1. Nothing can be strictly less than 0, so the count is 0.

Asked At

1 companies
CompanyDifficulty
AppleMediumView all Apple questions →

How to Think About It

1

Brute force: for each starting index, extend the subarray and multiply until product >= k, counting valid subarrays.

2

Prefix product array with binary search for each starting position.

3

Sliding window: maintain a window where the product is less than k, expanding and contracting as needed.

4

For each valid window [left, right], the number of subarrays ending at right is (right - left + 1).

5

Optimal: use a sliding window with two pointers, adding (right - left + 1) to the count when the window is valid.

Optimal Approach

Use a sliding window with two pointers. Maintain a running product. For each new element at the right pointer, multiply it into the product. While the product is >= k, divide out the element at the left pointer and advance left. If the window is valid (product < k), all subarrays ending at the right index are valid, so add (right - left + 1) to the count. This works because all numbers are positive, so the product is monotonic within the window.

Sliding window with a running product

numsproduct = 100105260123leftrightAfter adding 2, the product hits 100, so the window isinvalid and left must move.numsproduct = 10105260123leftrightDropping 10 makes the product 10, so the window [5,2] isvalid and adds 2 subarrays.numsproduct = 60105260123leftrightAdding 6 keeps the product at 60, so the window [5,2,6]adds 3 more subarrays.product *= nums[right]while product >= k: product //= nums[left]; left += 1count += right - left + 1
Grow the window on the right, shrink from the left while the product is too big, then add the number of valid endings.
ComplexityTime O(n)Space O(1)Each index enters and leaves the window at most once, so the two pointers move at most 2n steps in total, and only a few integer variables are stored.

What Trips People Up in Real Interviews

1

The product constraint is strict: product must be strictly less than k.

2

Since all numbers are positive, the product only grows when extending the window.

3

When product >= k, shrink from the left until the product is valid again.

4

Count formula: for a valid window [left, right], add (right - left + 1) new subarrays.

5

Handle edge case where k <= 1 — no subarray can have product less than k for positive integers.

Solution Code

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Subarray Product Less Than K problem?

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

How do you solve Subarray Product Less Than K?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Subarray Product Less Than K?

Subarray Product Less Than K is asked at Apple. It is a medium difficulty problem.

What are common mistakes on Subarray Product Less Than K?
  • The product constraint is strict: product must be strictly less than k.
  • Since all numbers are positive, the product only grows when extending the window.
  • When product >= k, shrink from the left until the product is valid again.
  • Count formula: for a valid window [left, right], add (right - left + 1) new subarrays.
  • Handle edge case where k <= 1 — no subarray can have product less than k for positive integers.