Subarrays Product Less than a Target

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.

Key Ideas

1. Keep moving a pointer(right) from the left to the right while keeping a pointer(left) at the left. (sliding window — we expand the window by moving the right pointer)
2. Add the current number to product .
3. If at any point the product is larger or equal to the target, move the left pointer to the right. (sliding window — we are shrinking the window by moving the left pointer)
4. Add the subarray (from left pointer to right pointer) to the result.
5. If the product of the subarray is less than target , then all product of the subarray elements are less than target as well.
6. Consider the case [2,3,4], target = 50 , if 2 * 3 * 4 < 50, then 2, 2 * 3, 3, 3 * 4 are all less than target . Add all of them to result.

Code

Time and Space Complexity

Time Complexity

We have an outer loop and inner loop, the worst case is that we have to iterate the entire array every time in the inner loop, so it will be O(N²). Notice we create a new list at line 29

result.push([...list])

In the worst case, it takes O(N). Thus, our algorithm takes O(N³) in time complexity.

Space Complexity

It takes O(N) space for our list.

How about the result list?

Finding all contiguous subarrays of an array is basically finding the number of ways to choose two indices, i and j, in the array such that i <= j.

Let’s consider the array has n length

• When i=0 , j can be anything from 0 to n-1 => n number of choices
• When i=1 , j can be anything from 1 to n-1 => n-1 number of choices
• When i=2 , j can be anything from 2 to n-2 => n-2 number of choices
• ….
• When i = n-1, j can only have only 1 choice

If we combine all the choices of j , it looks something like this

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

Which is n∗(n+1)/2 => O(N²)

So in total, our algorithm takes O(N³) space.