#713

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Subarray Product Less Than K

Count subarrays with a product strictly less than a given value k using efficient algorithms like binary search and sliding window.

array binary search sliding window prefix sum

Problem Statement

Given an array of integers nums and a positive integer k, the task is to return the number of contiguous subarrays where the product of the elements in the subarray is strictly less than k. The constraints require an efficient solution, given the potential size of the array (up to 30,000 elements).

The challenge is to utilize binary search or sliding window techniques for an optimal solution, as a brute-force approach that evaluates all subarrays will be too slow. You must balance correctness and efficiency to count all subarrays that meet the condition.

Examples

Example 1

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

Output: 8

The 8 subarrays that have 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 as the product of 100 is not strictly less than k.

Example 2

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

Output: 0

Example details omitted.

Constraints

1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106

Solution Approach

Sliding Window Approach

Use a sliding window to explore the subarrays and their products. Start with an empty window and expand the window by moving the right pointer. When the product exceeds k, move the left pointer to reduce the product. This ensures that each subarray's product is checked efficiently.

Binary Search over Answer Space

For each possible subarray, use binary search to find the smallest starting index where the product of the subarray is less than k. This step leverages the monotonic nature of the function that tracks subarray products, allowing faster determination of valid subarrays.

Optimizing with Prefix Product

Store prefix products to avoid redundant calculations for overlapping subarrays. This will allow you to quickly calculate the product of any subarray, making it easier to check the product constraint and adjust the window size accordingly.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log(n))
Space	O(n)

The time complexity is O(n * log(n)) because for each subarray, we perform a binary search on the valid subarray space. The space complexity is O(n) due to storing the prefix products or intermediate results in arrays.

What Interviewers Usually Probe

Understand how binary search over the valid space works with respect to subarrays.
Candidate uses efficient sliding window or binary search techniques instead of brute-force methods.
Look for ability to balance correctness with time complexity optimizations.

Common Pitfalls or Variants

Common pitfalls

Failing to adjust the window size properly when the product exceeds k.
Using a brute-force approach that evaluates all possible subarrays instead of leveraging efficient algorithms.
Misunderstanding the sliding window or binary search approach, resulting in suboptimal performance.

Follow-up variants

Change the constraint for k to be very large, testing how the solution scales with larger values of k.
Vary the array length significantly to assess performance under different input sizes.
Introduce negative numbers in the array and adjust the problem to handle those.

FAQ

What is the main pattern for solving the Subarray Product Less Than K problem?

The key pattern for this problem is binary search over the valid answer space, combined with a sliding window approach to efficiently track subarray products.

How does the sliding window technique work in this problem?

The sliding window technique expands the window by moving the right pointer, and when the product exceeds k, it shrinks the window from the left to maintain valid subarrays.

Can brute-force solutions work for Subarray Product Less Than K?

Brute-force solutions are inefficient for large arrays, as they would require checking every possible subarray, which is computationally expensive.

What is the time complexity of the optimal solution for Subarray Product Less Than K?

The time complexity of the optimal solution is O(n * log(n)) due to binary search combined with a sliding window to check subarrays.

How can GhostInterview help with understanding binary search in this problem?

GhostInterview provides practice and explanations to deepen understanding of how binary search can be applied to subarrays and their products efficiently.

terminal

Solution

Solution 1: Two Pointers

We can use two pointers to maintain a sliding window, where the product of all elements in the window is less than $k$.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans = l = 0
        p = 1
        for r, x in enumerate(nums):
            p *= x
            while l <= r and p >= k:
                p //= nums[l]
                l += 1
            ans += r - l + 1
        return ans

Continue Practicing

#862 shortest subarray with sum at least k #1004 max consecutive ones iii #209 minimum size subarray sum