Subarray Product Less Than K

MediumSliding Windowsliding window

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given an array of positive integers nums and an integer k, count the contiguous, non-empty subarrays whose product of all elements is **strictly less** than k. Target O(n) time. Every element is at least 1, so a window's product never shrinks when the window grows.

Examples

Input: nums = [10,5,2,6], k = 100
Output: 8
The qualifying subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6] and [5,2,6]. [10,5,2] has product exactly 100, which is not strictly less.
Input: nums = [1,2,3], k = 0
Output: 0
No product of positive integers is below 0.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More sliding window problems