Solution Problem Challenge 5: : Subarrays with Product Less than a Target

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution Problem Challenge 5: : Subarrays with Product Less than a Target

Table of Contents

Contents are not accessible

Problem Statement

Given an array with positive numbers and a positive target number, find all of its contiguous subarrays whose product is less than the target number.

Note: This problem is very similar to the previous one. Here, we are trying to find all the subarrays, whereas in the previous problem, we focused on finding only the count of such subarrays.

Example 1:

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

Example 2:

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

Constraints:

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

Solution

This problem follows the Sliding Window and the Two Pointers pattern and shares similarities with Triplets with Smaller Sum with two differences:

In this problem, the input array is not sorted.
Instead of finding triplets with sum less than a target, we need to find all subarrays having a product less than the target.

The implementation will be quite similar to Triplets with Smaller Sum. Here is a step-by-step explanation of the algorithm:

The goal of this algorithm is to find all subarrays of a given integer array where the product of the numbers in the subarray is less than a specified target value.
The algorithm uses a sliding window approach combined with a two-pointer method. A "window" of subarray is defined between the indices pointed to by two pointers, left and right.
The window starts from the leftmost side of the array (both left and right at position 0) and slides to the right one element at a time, expanding the window. This expansion is represented by incrementing right.
As we add a new element into the window (the right element), we multiply our current product with this new element.
If at any point the product of the numbers within the window (from left to right) becomes greater than or equal to the target, we need to make the product smaller. This is achieved by moving the left pointer to the right (incrementing left), effectively excluding the left element from our window, and dividing our product by this removed element. We keep doing this until our product is less than target again.
For each position of right, we create all possible subarrays that end at right, and that have a product less than the target. We do this by starting with a subarray that only includes the right element, then progressively adding the element to its left, and so on, until we reach the left pointer. All of these subarrays are added to the result.
This process is repeated for each element in the array (each position of right), with the left boundary being adjusted as necessary.
At the end of this process, result will contain all possible subarrays that have a product less than the target.

In summary, this algorithm slides a window across the array, expanding and contracting this window as necessary, to find all subarrays where the product of the numbers is less than a target value. For each window, it generates all valid subarrays ending at the right edge of the window.

Algorithm Walkthrough:

Using the input [2, 5, 3, 10] and target 30:

Initialize result = [], product = 1, left = 0.
Iterate with right = 0 (element = 2):
- product = 2.
- Add [2] to result.
Iterate with right = 1 (element = 5):
- product = 10.
- Add [5] and [2, 5] to result.
Iterate with right = 2 (element = 3):
- product = 30.
- Slide left to 1, product = 15.
- Add [3] and [5, 3] to result.
Iterate with right = 3 (element = 10):
- product = 150.
- Slide left to 2, product = 30.
- Slide left to 3, product = 10.
- Add [10] to result.
result: [[2], [5], [2, 5], [3], [5, 3], [10]]

Let's walkthrough the example 1 through below diagram.

Code

Here is what our algorithm will look like:

Python3

. . . .

Complexity Analysis

Time Complexity

Outer loop: The outer loop runs from right = 0 to right = N - 1, where N is the length of the input array. This loop runs $O(N)$ times.
Inner while loop: For each iteration of the outer loop, the inner while loop adjusts the left boundary of the subarray whenever the product is greater than or equal to the target. In the worst case, the while loop moves the left pointer through all elements of the array, but this happens only once per element. Therefore, moving the left pointer takes an amortized $O(N)$ time in total.
Nested subarray generation: For every element added in the result subarray, a new subarray is created and added to the result. The number of subarrays generated grows with each iteration of the outer loop. Specifically, for each value of right, the algorithm creates subarrays by moving from right to left, adding all valid subarrays.
- In the worst case, this generates O(N^2) subarrays.
  - The inner for loop will take $O(N)$ .
  - Creating a new list from an existing list will also take $O(N)$ . Following line in Python result.append(list(temp_list)) and following in Java result.add(new ArrayList<>(tempList)) will take $O(N)$ .

Overall time complexity: The total time complexity is dominated by the outer for loop $O(N)$ and the inner for loop to generate subarrays $O(N^2)$ ; hence the overall time complexity is $O(N^3)$ .

Space Complexity

Ignoring the space required for the output list, the algorithm runs in $O(N)$ space which is used for the temp list.

Can you try estimating how much space will be required for the output list?

   n + (n-1) + (n-2) + ... 3 + 2 + 1

The worst-case will happen when every subarray has a product less than the target!

So the question will be, how many contiguous subarrays an array can have?
It is definitely not all Permutations of the given array; is it all Combinations of the given array?

It is not all the Combinations of all elements of the array!

For an array with distinct elements, finding all of its contiguous subarrays is like finding the number of ways to choose two indices, i and j, in the array such that i <= j.

If there are a total of n elements in the array, here is how we can count all the contiguous subarrays:

When i = 0, j can have any value from 0 to n-1, giving a total of n choices.
When i = 1, j can have any value from 1 to n-1, giving a total of n-1 choices.
Similarly, when i = 2, j can have n-2 choices. … …
When i = n-1, j can only have only 1 choice.

Let’s combine all the choices:

Which gives us a total of: $N*(N+1)/2$ .

So, at most, we need space for $O(N^2)$ output lists. At worst, each subarray can take $O(N)$ space, so overall, our algorithm’s space complexity will be $O(N^3)$ .

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible