Skip to main content

713. Subarray Product Less Than K

medium

Given an array of positive integers and a target k, count contiguous subarrays whose product is strictly less than k. Sliding-window classic with a multiplicative twist.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

Example 1

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

Explanation: The 8 subarrays with 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 because its product 100 is not strictly less than k.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

All numbers are positive, so the product is non-decreasing as the window grows. That monotonicity lets you use a sliding window.

Hint 2

Expand the right pointer; while the product is >= k, shrink the left pointer.

Hint 3

When the window is valid, every subarray ending at right contributes (right - left + 1) to the count.

Solution approach

Reveal approach

Use a two-pointer sliding window. Initialise left = 0, product = 1, and count = 0. Walk right from 0 to n-1: multiply product by nums[right]. While product >= k and left <= right, divide product by nums[left] and increment left to shrink the window until the product drops below k (or the window empties). Then add (right - left + 1) to count — that is the number of valid subarrays ending exactly at right. The technique works because all elements are positive, which makes the product monotonic in window width. Handle the edge case k <= 1 by returning 0 immediately since no product of positive integers can be strictly less than 1.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • sliding-window
  • two-pointers

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Apple

Practice these live with InterviewChamp.AI

Drill Subarray Product Less Than K and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →