# 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.

# 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.

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.

--

--

Software engineer in Singapore. Write random tech stuff. Still figuring out this “life” thing in life.