Find all 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:
- 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.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
