We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subarray Product Less Than K

Number: 713

Difficulty: Medium

Paid? No

Companies: Salesforce, Amazon, Squarepoint Capital, Agoda, Airbnb, Meta, Flexport, ServiceNow, IBM, Google, Apple, Adobe, LinkedIn, PayPal, Nvidia, TikTok, SoFi, Yatra

Problem Description

Given an array of positive integers and an integer k, count the number of contiguous subarrays such that the product of all the elements in the subarray is strictly less than k.

Key Insights

  • Using a sliding window approach is effective when dealing with contiguous subarrays and maintaining a running product.
  • Since the problem involves multiplying numbers, as soon as the running product exceeds or equals k, shrink the window from the left.
  • The number of valid subarrays ending at the current right pointer is given by the length of the window.

Space and Time Complexity

Time Complexity: O(n) because each element is visited at most twice. Space Complexity: O(1) as only a few extra variables are used.

Solution

The solution uses a sliding window technique to maintain a running product of the subarray.

  1. Initialize pointers for the window (left) and variables for the running product (prod) and count of valid subarrays (ans).
  2. Iterate through the array with a right pointer, multiplying the current element to the product.
  3. If the product becomes greater than or equal to k, move the left pointer rightwards while dividing the product by each element passed.
  4. The number of subarrays ending at the current index that satisfy the condition is equal to (right - left + 1). Add this count to ans.
  5. Return the final count stored in ans.

This method efficiently tracks valid subarrays and avoids checking all possible combinations.

Code Solutions

def numSubarrayProductLessThanK(nums, k):
    # If k is less than or equal to 1, no valid subarray exists
    if k <= 1:
        return 0
    prod = 1  # Running product of the current window
    ans = 0   # Counter for valid subarrays
    left = 0  # Left pointer of the sliding window
    # Iterate over the array using the right pointer
    for right, value in enumerate(nums):
        prod *= value  # Multiply the current value into the running product
        # Shrink the window from the left until the product is less than k
        while prod >= k:
            prod //= nums[left]
            left += 1
        # All subarrays ending at 'right' with start indices between 'left' and 'right' are valid
        ans += right - left + 1
    return ans

# Example usage
print(numSubarrayProductLessThanK([10, 5, 2, 6], 100))  # Expected output: 8
← Back to All Questions