Subarray Product Less Than K Problem

Subarray Product Less Than K Problem — ExecCode Medium DSA Practice

Solve the Subarray Product Less Than K problem on ExecCode. Free online medium DSA practice in Arrays - Basics. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Given an array of positive integers nums and an integer k, count how many contiguous subarrays have product strictly less than k. Because every number is positive, expanding right can only multiply the product upward, and moving left can only reduce it. After shrinking until product < k, every suffix of the current window ending at right is also valid, so add right - left + 1 to the answer.

Examples

Input nums = [10, 5, 2, 6, 8, 3, 7, 4], k = 100; Output 18. Input nums = [10, 5, 2, 6], k = 100; Output 8. Input nums = [1, 2, 3], k = 0; Output 0

Constraints

1 ≤ nums.length ≤ 3×10⁴ 1 ≤ nums[i] ≤ 1000 0 ≤ k ≤ 10⁶

Practice Subarray Product Less Than K free on ExecCode. Browse DSA problems, topic map, and placement guides.