Find all subarrays with product less than target

0 / 162
Subarrays with product less than target

Problem Statement

 

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

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.

 

 

 

Solution

 

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

  1. In this problem, the input array is not sorted.
  2. 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.The idea is to loop through the array computing product in each iteration and checking if that product is less than the target and if so, increment one of the pointers which will be a forward pointer (left) and the outer loop pointer (right) will still be pointing to the start of the window. Once we have these 2 pointers,  the next task is to push elements between the 2 pointers to a temp array and then push the temp array into the final output array which will have the resulting list of arrays which match the said criteria.

 

Below is the Javascript code for the above approach

 

<script>

function find_subarrays(arr, target) {
   var result = [];
    var product = 1, left = 0;
    for (var right = 0; right < arr.length; right++) {
      product *= arr[right];
      while (product >= target && left < arr.length)
        product /= arr[left++];
     
      var tempList = [];
      // since the product of all numbers from left to right is less than the target therefore,
      // all subarrays from lef 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
      for (var i = right; i > left-1; i--) {
        tempList.unshift(arr[i]);
        result.push(tempList.join(' ').split(' '));
      }
    }
    
    return result;
};


document.write(JSON.stringify(find_subarrays([2, 5, 3, 10], 30))+'<br/>');
document.write(JSON.stringify(find_subarrays([8, 2, 6, 5], 50))+'<br/>');

</script>

 

The same code can be written in C++ using vectors as below:

 

using namespace std;

#include <deque>
#include <iostream>
#include <vector>

class SubarrayProductLessThanK {
 public:
  static vector<vector<int>> findSubarrays(const vector<int>& arr, int target) {
    vector<vector<int>> result;
    int product = 1, left = 0;
    for (int right = 0; right < arr.size(); right++) {
      product *= arr[right];
      while (product >= target && left < arr.size()) {
        product /= arr[left++];
      }
      // since the product of all numbers from left to right is less than the target therefore,
      // all subarrays from lef 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
      deque<int> tempList;
      for (int i = right; i >= left; i--) {
        tempList.push_front(arr[i]);
        vector<int> resultVec;
        std::move(std::begin(tempList), std::end(tempList), std::back_inserter(resultVec));
        result.push_back(resultVec);
      }
    }
    return result;
  }
};

int main(int argc, char* argv[]) {
  auto result = SubarrayProductLessThanK::findSubarrays(vector<int>{2, 5, 3, 10}, 30);
  for (auto vec : result) {
    cout << "[";
    for (auto num : vec) {
      cout << num << " ";
    }
    cout << "]";
  }
  cout << endl;

  result = SubarrayProductLessThanK::findSubarrays(vector<int>{8, 2, 6, 5}, 50);
  for (auto vec : result) {
    cout << "[";
    for (auto num : vec) {
      cout << num << " ";
    }
    cout << "]";
  }
}

 

Python

 

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 lef 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()

 

Finally Java

 

import java.util.*;

class SubarrayProductLessThanK {

  public static List<List<Integer>> findSubarrays(int[] arr, int target) {
    List<List<Integer>> result = new ArrayList<>();
    int product = 1, left = 0;
    for (int right = 0; right < arr.length; right++) {
      product *= arr[right];
      while (product >= target && left < arr.length)
        product /= arr[left++];
      // since the product of all numbers from left to right is less than the target therefore,
      // all subarrays from lef 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
      List<Integer> tempList = new LinkedList<>();
      for (int i = right; i >= left; i--) {
        tempList.add(0, arr[i]);
        result.add(new ArrayList<>(tempList));
      }
    }
    return result;
  }

  public static void main(String[] args) {
    System.out.println(SubarrayProductLessThanK.findSubarrays(new int[] { 2, 5, 3, 10 }, 30));
    System.out.println(SubarrayProductLessThanK.findSubarrays(new int[] { 8, 2, 6, 5 }, 50));
  }
}

 

Time complexity

 

The main for-loop managing the sliding window takes O(N) but creating subarrays can take up to O(N^2) in the worst case. Therefore overall, our algorithm will take 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.

Since there can be maximum of N arrays with sizes 1 to N, the space required for output list will be summation (1 to N) = N(N+1)/2 which gives O(N^2) space complexity at max (worst case).

 

Comments

comments


An avid reader, responsible for generating creative content ideas for golibrary.co. His interests include algorithms and programming languages. Blogging is a hobby and passion.

Related Posts