Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution Problem Challenge 5: Counting Subarrays with Product Less than a Target
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given an array nums with positive numbers and a positive integer target, return the count of contiguous subarrays whose product is less than the target number.

Examples

Example 1:

  • Input: nums = [2, 5, 3, 10], target=30
  • Output: 6
  • Explanation: There are six contiguous subarrays ([2], [5], [2, 5], [3], [5, 3], [10]) whose product is less than the target.

Example 2:

  • Input: nums = [8, 2, 6, 5], target=50
  • Output: 7
  • Explanation: There are seven contiguous subarrays ([8], [2], [8, 2], [6], [2, 6], [5], [6, 5]) whose product is less than the target.

Example 3:

  • Input: nums = [10, 5, 2, 6], k = 0
  • Expected Output: 0
  • Explanation: Subarrays with product less than 0 doesn't exists.

Constraints:

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

Solution

To solve the "Subarray Product Less Than Target" problem, we utilize the Two-Pointer Sliding Window technique. This approach is highly effective for handling problems involving contiguous subarrays. Here's how it works:

  • Sliding Window Concept: We maintain a window defined by two pointers, left and right, which represent the current range of elements under consideration. The window slides through the array to include new elements and exclude old ones based on the product constraint.

  • Maintaining the Product: As we expand the window by moving the right pointer, we multiply the current element to a running product. If this product exceeds or equals the target, we shrink the window from the left by moving the left pointer and dividing the product by the element being excluded. This ensures that the product of the elements within the window always remains below the target.

  • Counting Valid Subarrays: For each position of the right pointer, the number of valid subarrays ending at that position is equal to the size of the current window (right - left + 1). We accumulate this count in a variable totalCount.

Step-by-Step Algorithm

  1. Initialize Variables:

    • totalCount: Set to 0. This variable will store the total number of valid subarrays found.
    • product: Set to 1. This will hold the product of elements within the current window.
    • left: Set to 0. This pointer represents the left boundary of the sliding window.

  2. Handle Edge Cases:

    • If the target is less than or equal to 1, return 0 immediately since no positive product can be less than 1.

  3. Iterate Through the Array:

    • For each index right from 0 to nums.length - 1:

      • Update Product:

        • Multiply product by nums[right] to include the current element in the window.

      • Adjust the Left Boundary:

        • While product is greater than or equal to target and left is less than or equal to right:
          • Divide product by nums[left] to exclude the leftmost element from the window.
          • Increment left by 1 to shrink the window from the left.
          • This step ensures the product of the current window remains below the target by removing elements that cause the product to exceed the target.

      • Calculate Valid Subarrays:

        • Add (right - left + 1) to totalCount. This represents the number of new subarrays ending at index right that have a product less than the target. Each element from left to right forms a valid subarray.

  4. Return the Result:

    • After completing the iteration, return totalCount as the total number of valid subarrays.

Algorithm Walkthrough

Let's walk through the algorithm using the input nums = [2, 5, 3, 10] and target = 30.

Image

  1. Initialization:

    • totalCount = 0
    • product = 1
    • left = 0

  2. First Iteration (right = 0):

    • Current Element: nums[0] = 2
    • Update Product: product = 1 * 2 = 2
    • Check Product: 2 < 30 (No adjustment needed)
    • Calculate Subarrays: right - left + 1 = 0 - 0 + 1 = 1
    • Update totalCount: totalCount = 0 + 1 = 1
    • Valid Subarrays: [2]

  3. Second Iteration (right = 1):

    • Current Element: nums[1] = 5
    • Update Product: product = 2 * 5 = 10
    • Check Product: 10 < 30 (No adjustment needed)
    • Calculate Subarrays: 1 - 0 + 1 = 2
    • Update totalCount: 1 + 2 = 3
    • Valid Subarrays: [2, 5], [5]

  4. Third Iteration (right = 2):

    • Current Element: nums[2] = 3
    • Update Product: product = 10 * 3 = 30
    • Check Product: 30 >= 30 (Adjustment needed)
      • Adjust Left Boundary:
        • Divide Product: product = 30 / 2 = 15
        • Increment Left: left = 0 + 1 = 1
      • Check Again: 15 < 30 (Stop adjusting)
    • Calculate Subarrays: 2 - 1 + 1 = 2
    • Update totalCount: 3 + 2 = 5
    • Valid Subarrays: [5, 3], [3]

  5. Fourth Iteration (right = 3):

    • Current Element: nums[3] = 10
    • Update Product: product = 15 * 10 = 150
    • Check Product: 150 >= 30 (Adjustment needed)
      • Adjust Left Boundary:
        • Divide Product: product = 150 / 5 = 30
        • Increment Left: left = 1 + 1 = 2
      • Check Again: 30 >= 30 (Continue adjusting)
        • Divide Product: product = 30 / 3 = 10
        • Increment Left: left = 2 + 1 = 3
      • Check Again: 10 < 30 (Stop adjusting)
    • Calculate Subarrays: 3 - 3 + 1 = 1
    • Update totalCount: 5 + 1 = 6
    • Valid Subarrays: [10]

  6. Final Result:

    • totalCount = 6
    • Valid Subarrays:
      1. [2]
      2. [2, 5]
      3. [5]
      4. [5, 3]
      5. [3]
      6. [10]

Thus, the total number of contiguous subarrays where the product of all elements is strictly less than 30 is 6.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

The algorithm operates in O(n) time complexity, where n is the length of the input array arr. Here's why:

  • Single Pass Through the Array: The main for loop iterates through each element of the array exactly once.
  • Sliding Window Mechanism: The inner while loop advances the left pointer only when the product of the current window (product) is greater than or equal to the target. Importantly, each element is visited at most twice—once by the right pointer and once by the left pointer. This ensures that the total number of operations remains proportional to n.

As a result, despite having a nested loop structure, the overall number of operations scales linearly with the size of the input, maintaining an efficient O(n) time complexity.

Space Complexity

The algorithm uses O(1) space complexity, meaning it requires constant additional space regardless of the input size. Here's the breakdown:

  • Variables Used: The algorithm utilizes a fixed number of variables (totalCount, product, left, and right) to keep track of counts and indices.
  • No Additional Data Structures: No auxiliary data structures (like arrays, lists, or hash maps) are used that grow with the input size.

Therefore, the space required by the algorithm does not increase with the size of the input array, ensuring an optimal O(1) space complexity.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible