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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Subarray Product Less Than K

Difficulty: Medium

Problem Description

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.

Key Insights

  • A subarray is a contiguous part of an array.
  • The product of elements in a subarray must be calculated to determine if it is less than k.
  • The sliding window technique can be used to maintain the product of the current subarray efficiently.
  • If the product exceeds or equals k, the left end of the window can be moved to reduce the product.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array, as we iterate through the array with two pointers. Space Complexity: O(1), since we are using a fixed amount of extra space regardless of the input size.

Solution

The problem can be solved using the sliding window technique. We maintain a window defined by two pointers: left and right. The right pointer expands the window by moving to the right, and we multiply the current product by nums[right]. If the product is greater than or equal to k, we shrink the window from the left by incrementing left until the product is less than k. The count of valid subarrays can be calculated by the difference between right and left.

Code Solutions

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0  # No valid subarray possible
    
    product = 1
    left = 0
    count = 0
    
    for right in range(len(nums)):
        product *= nums[right]  # Expand the window
        
        while product >= k:  # Shrink the window
            product //= nums[left]
            left += 1
        
        count += right - left + 1  # Count valid subarrays
    
    return count
← Back to All Questions