Home/

...

/

Subarrays with Product Less than a Target (medium)

Subarrays with Product Less than a Target (medium)

General Discussion

One approach can be to sort the array, and then traverse it while multiplying the elements from left till the end of the array, collecting the elements in a result variable whenever the product is less than the target. The problem is that the sorting step destroys the contiguity relationships among the array elements.

In this problem, we are looking for the consecutive elements forming a subarray whose product is less than the target. This is different from finding a subset of the array elements that meets the given criterion. By definition, subarray implies using a sequence of elements in the original array that are contiguous, whereas the order is irrelevant when forming subsets.

Dry-run templates

This is the implementation of the solution provided for the problem posed in the lesson:

Press + to interact
Python 3.5
from collections import deque
def find_subarrays(arr, target):
  result = []
  product = 1
  left = 0
  for right in range(len(arr)):
    product *= arr[right]
    while (product >= target and left < len(arr)):
      product /= arr[left]
      left += 1
    # since the product of all numbers from left to right is less than the target therefore,
    # all subarrays from left to right will have a product less than the target too; to avoid
    # duplicates, we will start with a subarray containing only arr[right] and then extend it
    temp_list = deque()
    for i in range(right, left-1, -1):
      temp_list.appendleft(arr[i])
      result.append(list(temp_list))
  return result
def main():
  print(find_subarrays([2, 5, 3, 10], 30))
  print(find_subarrays([8, 2, 6, 5], 50))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

Input array: [2, 5, 3, 10]
Target: 30

Iteration No.

Line No.

Product

left

right

result

-

3-5

1

0

-

[]

1

7

2

0

0

[]

1

15-17

2

0

0

[[2]]

2

7

10

0

1

[[2]]

2

15-17

10

0

1

[[2],[5]]

2

15-17

10

0

1

[[2],[5],[2,5]]

3

7

30

0

2

[[2],[5],[2,5]]

3

8-10

15

1

2

[[2],[5],[2,5]]

3

15-17

15

1

2

[[2],[5],[2,5],[3]]

3

15-17

15

1

2

[[2],[5],[2,5],[3],[5,3]]

4

7

150

1

3

[[2],[5],[2,5],[3],[5,3]]

4

8-10

30

2

3

[[2],[5],[2,5],[3],[5,3]]

4

8-10

10

3

3

[[2],[5],[2,5],[3],[5,3]]

4

15-17

10

3

3

[[2], [5], [2, 5], [3], [5, 3], [10]]

Sample Input #2

Input array: [1, 10, 20, 2, 50]
Target: 500

Students may be encouraged to complete the dry-run with this input:

Iteration No.

Line No.

Product

left

right

result

-

3-5

1

0

-

[]

1

7

1

0

0

[]

1

15-17

1

0

0

[[1]]

2

7

10

0

1

[[1]]

2

15-17

10

0

1

[[1],[10]]

2

15-17

10

0

1

[[1],[10],[1,10]]

...

...

...

...

...

...

Step-by-step solution construction

Let’s iterate through the array from left to the right and generate the subarrays against each index.

Following is the explanation of the code below:

  1. On line 5, we initialize an empty array called result.
  2. On line 6, we iterate through the input array, arr, from 0 to len(arr) -1, that is, from the first to the last index of the array.
  3. On lines 10-11, we generate subarrays from the 0th index to right, by appending the array items in reverse in a special data structure, a double-ended queue, also called a deque. The use of the deque is natural as we need to append the new elements to the left of the previous elements. A quick overview of the deque data structure in Python is provided here.
  4. On line 12, we convert each generated subarray to a regular list and then append it to result.
Press + to interact
Python 3.5
from collections import deque
def find_subarrays(arr, target):
  print("Given array: "+str(arr))
  print("Given target: " + str(target))
  result = []
  for right in range(len(arr)):
    temp_list = deque()
    print("right: " + str(right))
    print("\tsub arrays computed in the current iteration are: ")
    for i in range(right, -1, -1):
      temp_list.appendleft(arr[i])
      result.append(list(temp_list))
      print("\t\ttemp_list",end=" ")
      print(list(temp_list))
    print("\tresult array at the end of iteration " + str(right) + " is " + str(result))
  return result
def main():
  inputs = [[[2, 5, 3, 10], 30],[[8, 2, 6, 5], 50]]
  for i in range(len(inputs)):
      result = find_subarrays(inputs[i][0], inputs[i][1])
      print("\nThe subarrays for the array "+ str(inputs[i][0]) + " with target "+ str(inputs[i][1]) + " are: " + str(result))
      print("-"*100)
      
  
  #print(find_subarrays([8, 2, 6, 5], 50))
main()

The above code generates the subarrays, but we haven’t put any condition to add only those subarrays to the result whose product is less than target , so let’s add it now.

Press + to interact
Python 3.5
from collections import deque
def find_subarrays(arr, target):
  print("Given array: "+str(arr))
  print("Given target: " + str(target))
  result = []
  product = 1
  left = 0
  for right in range(len(arr)):
    print("right: " + str(right))
    product *= arr[right]
    print("\tproduct: "+str(product))
    while (product >= target and left < len(arr)):
      print("\tDividing product (" + str(product) + ") by arr[left] (" + str(arr[left]) + ")")
      product /= arr[left]
      print("\tupdated product: "+str(product))
      left += 1
      print("\tnew value for left index: "+ str(left))
    # since the product of all numbers from left to right is less than the target therefore,
    # all subarrays from left to right will have a product less than the target too; to avoid
    # duplicates, we will start with a subarray containing only arr[right] and then extend it
    temp_list = deque()
    
    print("\tsub arrays computed in the current iteration are: ")
    for i in range(right, -1, -1):
      temp_list.appendleft(arr[i])
      result.append(list(temp_list))
      print("\t\ttemp_list: ",end=" ")
      print(list(temp_list))
    print("\tresult array at the end of iteration " + str(right) + " is " + str(result))
  return result
def main():
  inputs = [[[2, 5, 3, 10], 30],[[8, 2, 6, 5], 50]]
  for i in range(len(inputs)):
      result = find_subarrays(inputs[i][0], inputs[i][1])
      print("\nThe subarrays for the array "+ str(inputs[i][0]) + " with target "+ str(inputs[i][1]) + " are: " + str(result))
      print("-"*100)
      
  
  #print(find_subarrays([8, 2, 6, 5], 50))
main()
  1. On lines 6-7, we add two variables product & left and initialize them to 1 and 0 respectively.
  2. On line 10, we compute the product by multiplying it with the next item in the array arr[right].
  3. On lines 12-16, we have added the checks to ensure that the elements in the subarray between left and right yield a product less than target.  As long as product is greater than or equal to target and left has not reached the end of the array, we move left one step forward to exclude the item pointed to by left. Also, we decrease the product by dividing it by the excluded item.

As we can see from the output, although left is being moved along correctly to filter out subarrays whose product exceeds target, we are still collecting all the subarrays in result. So, we need to modify the for loop that generates and collects subarrays, to filter out the unwanted subarrays. The for loop on lines 24-26 generates sub-arrays from right to 0, whereas the exact solution should incorporate the left calculated in the while loop on lines 12-16.

Find below the finalized code and compare its output with the output of the previous code:

Press + to interact
Python 3.5
from collections import deque
def find_subarrays(arr, target):
  print("Given array: "+str(arr))
  print("Given target: " + str(target))
  result = []
  product = 1
  left = 0
  for right in range(len(arr)):
    print("right: " + str(right))
    product *= arr[right]
    print("\tproduct: "+str(product))
    while (product >= target and left < len(arr)):
      print("\tDividing product (" + str(product) + ") by arr[left] (" + str(arr[left]) + ")")
      product /= arr[left]
      print("\tupdated product: "+str(product))
      left += 1
      print("\tnew value for left index: "+ str(left))
    # since the product of all numbers from left to right is less than the target therefore,
    # all subarrays from left to right will have a product less than the target too; to avoid
    # duplicates, we will start with a subarray containing only arr[right] and then extend it
    temp_list = deque()
    
    print("\tsub arrays computed in the current iteration are: ")
    for i in range(right, left-1, -1):
      temp_list.appendleft(arr[i])
      result.append(list(temp_list))
      print("\t\ttemp_list: ",end=" ")
      print(list(temp_list))
    print("\tresult array at the end of iteration " + str(right) + " is " + str(result))
  return result
def main():
  inputs = [[[2, 5, 3, 10], 30],[[8, 2, 6, 5], 50]]
  for i in range(len(inputs)):
      result = find_subarrays(inputs[i][0], inputs[i][1])
      print("\nThe subarrays for the array "+ str(inputs[i][0]) + " with target "+ str(inputs[i][1]) + " are: " + str(result))
      print("-"*100)
      
  
  #print(find_subarrays([8, 2, 6, 5], 50))
main()