algoadvance

Leetcode 713. Subarray Product Less Than K

Problem Statement

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.

Clarifying Questions

  1. Q: Can the input array contain negative integers or zero? A: According to the problem constraints, nums will contain positive integers. Negative numbers or zeroes are not considered.

  2. Q: What should be returned if k is less than or equal to 1? A: If k is less than or equal to 1, it’s impossible to have any subarray with a product less than k since the smallest product of positive integers starts from 1. Therefore, the result should be 0.

  3. Q: What are the constraints on the values of nums and k? A: The problem states:

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

Strategy

To solve this problem, we can use the sliding window (two-pointer) technique to efficiently calculate the subarray products and count those that meet the criteria. Here’s the step-by-step process:

  1. Initialize Two Pointers and Product:
    • Use two pointers, left at the start of the window and right to expand the window.
    • Maintain a variable product to store the product of the elements in the current window.
  2. Expand the Window:
    • Iterate with the right pointer over the array. Multiply the current element to the product.
  3. Shrink the Window:
    • If the product reaches or exceeds k, increment the left pointer to shrink the window until the product is less than k.
  4. Count Subarrays:
    • For each position of right, all subarrays ending with right and starting from left to right are valid. The count of such subarrays is right - left + 1.
  5. Edge Cases:
    • Handle the special case where k is less than or equal to 1.

Code

Here’s how you can implement this in C++:

#include <vector>

int numSubarrayProductLessThanK(std::vector<int>& nums, int k) {
    if (k <= 1) return 0;
    
    int left = 0;
    int product = 1;
    int result = 0;

    for (int right = 0; right < nums.size(); ++right) {
        product *= nums[right];
        
        while (product >= k) {
            product /= nums[left];
            ++left;
        }
        
        result += right - left + 1;
    }

    return result;
}

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the length of the input array nums. This is because each element is processed at most twice (once by right increment and once by left increment). Thus, it is an efficient solution suitable for large inputs given the constraints (1 \leq nums.length \leq 3 \times 10^4).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI