Domain 2MediumMEDIUM

Subarray Product Less Than K

LeetCode problem 713: Subarray Product Less Than K (medium).

Domain: medium•Updated: 2026-08-30
#Array#Two Pointers

Problem Breakdown

We need to count all contiguous subarrays within a given array of positive integers where their product is strictly less than a target value k.

Inputs:

  • An array nums containing only positive integers (1 or greater).
  • A threshold integer k.

Outputs:

  • The total number of valid subarrays.

Constraints & Edge Cases to Consider:

  • Positive Integers Only: Since every element is ≥1\ge 1, multiplying more elements never decreases the product. This monotonicity is key for optimization.
  • Threshold k≤1k \le 1: If k is less than or equal to 1, no subarray can satisfy the condition because the minimum possible product of positive integers is 1 (e.g., [1]). We must handle this immediately to avoid infinite loops or incorrect logic in sliding window.
  • Large NN: With length up to 50,000, an O(N2)O(N^2) solution will time out. We need something closer to linear time.

Intuition

A brute-force approach would iterate through every possible start and end index for subarrays (O(N2)O(N^2)) and calculate the product each time (potentially leading to overflow or redundant calculations). Even optimizing the inner loop doesn’t change the worst-case complexity significantly enough for N=50,000N=50,000.

Key Insight: Because all numbers are positive integers ≥1\ge 1, expanding a window from left to right always increases (or maintains) the product. Conversely, shrinking from the left decreases it. This monotonic behavior allows us to use a Sliding Window / Two Pointers technique.

For any valid subarray ending at index right, if we know the smallest starting index left such that the window [left...right] has a product <k< k, then all windows between left and right (inclusive) are also valid because removing elements from the left only reduces or keeps the product constant. Thus, for each step of right, we simply add (right - left + 1) to our count after adjusting left.

Approach

  1. Handle Base Case: If k≤1k \le 1, return 0 immediately since all elements are ≥1\ge 1.
  2. Initialize Variables: Set a sliding window pointer left at the start, and maintain a running product variable initialized to 1. Initialize count to 0.
  3. Iterate with Right Pointer: Loop through each element in nums, treating it as the end of our current subarray (right).
  4. Expand Window: Multiply the current window’s product by nums[right].
  5. Shrink Window if Needed: While the running product is ≥k\ge k, divide the product by nums[left] and increment left. This ensures we maintain a valid state where product < k. Note: If an individual element itself causes overflow or exceeds kk (e.g., [10, ...], k=5k=5), this loop will shrink until the window is empty (left > right).
  6. Count Valid Subarrays: Once the product condition is met for right, every subarray ending at right starting from any index between left and right is valid. Add (right - left + 1) to count.
  7. Return Result.

Complexity Analysis

  • Time Complexity: O(N)O(N). The right pointer moves forward once, and the left pointer also moves at most as many times (each element enters and leaves the window exactly once). Operations inside are constant time arithmetic.
  • Space Complexity: O(1)O(1). We only use a few integer variables for pointers and product tracking regardless of input size.

Solution

def numSubarrayProductLessThanK(nums, k):
    # If k <= 1, no subarray can have product < k since nums[i] >= 1
    if k <= 1:
        return 0
    
    left = 0
    prod = 1
    count = 0
    
    for right in range(len(nums)):
        prod *= nums[right]
        
        # Shrink window from the left until product is strictly less than k
        while prod >= k and left <= right:
            prod //= nums[left]
            left += 1
            
        # All subarrays ending at 'right' starting between 'left' and 'right' are valid.
        count += (right - left + 1)
        
    return count

# Example usage matching problem description
nums = [10, 5, 2, 6]
k = 100
print(numSubarrayProductLessThanK(nums, k)) # Output: 8

Edge Cases Handled

  • k≤1k \le 1: Explicitly returns 0 at the start to prevent logic errors where product never drops below kk.
  • Single element ≥k\ge k: The while loop condition ensures that if a single number makes the window invalid, we shrink until left > right, resulting in adding 0 for that step (correct behavior).
  • Product Overflow: Python handles large integers automatically. However, since k<106k < 10^6 and elements are small, standard integer arithmetic is safe without modulo logic needed here.