713. Subarray Product Less Than K - Detailed Explanation

Problem Statement

Description:

You are given an array of positive integers nums and an integer k. Your task is to return the number of (contiguous) subarrays where the product of all the elements in the subarray is strictly less than k.

Key Points:

• A subarray is a contiguous part of the array.

• You need to count only those subarrays where the product of elements is strictly less than k.

• All numbers in the array are positive.

Example 1:

• Input:
  nums = [10, 5, 2, 6], k = 100
• Output:
  8
• Explanation:
  The subarrays with product less than 100 are:
  • Starting at index 0: [10] (product = 10), [10, 5] (product = 50)
  • Starting at index 1: [5] (product = 5), [5, 2] (product = 10), [5, 2, 6] (product = 60)
  • Starting at index 2: [2] (product = 2), [2, 6] (product = 12)
  • Starting at index 3: [6] (product = 6)
    Total count = 2 + 3 + 2 + 1 = 8.

Example 2:

• Input:
  nums = [1, 2, 3], k = 0
• Output:
  0
• Explanation:
  Since k is 0 and all products are at least 1, no subarray qualifies.

Constraints:

• (1 \leq \text{nums.length} \leq 3 \times 10^4)
• (1 \leq \text{nums}[i] \leq 1000)
• (0 \leq k \leq 10^6)

2. Hints for the Approach

• Hint 1:
  Consider how a brute-force solution would check every possible subarray and compute its product. Can you do better than checking all (O(n^2)) subarrays?

• Hint 2:
  Since the numbers are positive, if you know a subarray’s product, adding another number on the right will only increase the product. This observation makes it possible to use a sliding window (two-pointer) approach.

• Hint 3:
  Keep a running product for your current window. When the product becomes greater than or equal to k, move the left pointer to shrink the window until the product is again less than k. For each new element added (with a valid window), count all subarrays ending at that index.

Approaches

Approach 1: Brute Force (Conceptual Discussion)

• Idea:
  Iterate over every possible subarray, compute the product, and check if it is less than k.
• Drawback:
  This approach takes (O(n^2)) time in the best case and even more if you recalculate products repeatedly, which is too slow for large arrays (up to 30,000 elements).

Approach 2: Sliding Window (Optimal)

Idea

1. Maintain a Window:
   Use two pointers (left and right) to maintain a window in the array.

2. Running Product:
   Keep a running product of the elements in the window.

3. Expand and Contract:

   • Move the right pointer to include new elements and update the product.
   • If the product becomes greater than or equal to k, move the left pointer forward (shrinking the window) until the product is less than k.

4. Count Subarrays:
   When the current window [left, right] has a product less than k, all subarrays ending at right that start anywhere between left and right are valid. The count is right - left + 1.

Pseudocode

if k <= 1:
    return 0

product = 1
result = 0
left = 0

for right from 0 to nums.length - 1:
    product *= nums[right]
    while product >= k and left <= right:
        product /= nums[left]
        left += 1
    result += right - left + 1

return result

Detailed Step-by-Step Walkthrough

Consider nums = [10, 5, 2, 6] and k = 100.

1. Initialize:

   • left = 0, product = 1, result = 0.

2. Iteration 1 (right = 0):

   • Multiply: product = 1 * 10 = 10 (10 < 100, window valid).
   • Count subarrays ending at index 0: right - left + 1 = 0 - 0 + 1 = 1.
     Valid subarray: [10]
   • result = 1.

3. Iteration 2 (right = 1):

   • Multiply: product = 10 * 5 = 50 (50 < 100, window valid).
   • Count subarrays ending at index 1: right - left + 1 = 1 - 0 + 1 = 2.
     Valid subarrays: [5] and [10, 5]
   • result = 1 + 2 = 3.

4. Iteration 3 (right = 2):

   • Multiply: product = 50 * 2 = 100 (100 ≥ 100, window invalid).
   • Shrink window from left:
     • Divide by nums[left] (10): product = 100 / 10 = 10. Increase left to 1.
   • Now window [1,2] has product 10 * 2 = 10 * 2 = 10?
     (Actually, product becomes 50/10 2? Let's recompute carefully:
     After iteration 2, product was 50 (from [10,5]). Then multiplied by 2 gives 100.
     Remove nums[0]=10: new product = 100/10 = 10. Window is now [5,2], product = 52=10, which is valid.)
   • Count subarrays ending at index 2: right - left + 1 = 2 - 1 + 1 = 2.
     Valid subarrays: [2] and [5,2]
   • result = 3 + 2 = 5.

5. Iteration 4 (right = 3):

   • Multiply: product = 10 * 6 = 60 (window [1,2,3]: [5,2,6] with product 526=60, valid).
   • Count subarrays ending at index 3: right - left + 1 = 3 - 1 + 1 = 3.
     Valid subarrays: [6], [2,6], and [5,2,6]
   • result = 5 + 3 = 8.

Final Answer: 8

Code Implementation

Python Implementation