Cant this question be solved in O(N) time using a sliding window?

``````import java.util.*;

class SubarrayProductLessThanK {

public static List<List<Integer>> findSubarrays(int[] arr, int target) {
List<List<Integer>> subarrays = new ArrayList<>();
List<Integer> currentList = new ArrayList<>();
int currentProduct = 1, start=0;
for (int i=0;i<arr.length;i++) {
int currentNumber = arr[i];
currentProduct *= currentNumber;
if (currentNumber<target) {
}
if (currentList.size()>1) {
while(currentProduct>=target) {
currentProduct /= arr[start++];
currentList.remove(0);
}
if (currentProduct < target && currentList.size()>1) {
}
}
}
return subarrays;
}
}``````

Hello @Satya_Vivek,

Thank you for suggesting this solution of yours. Yes, you are right that we can solve the problem mentioned above in O(N) using the sliding window approach.

I hope I have answered your query; please let me know if you still have any confusion.

Thank You

1 Like

Hello @Satya_Vivek ,

You are right. We can solve the problem mentioned above in O(N^2) as βnew ArrayList<>(collection)β also takes O(N). Above mentioned code might require minor additions to take care of edge cases.
Ex; arr : {2, 5, 3, 10, 1, 30, 1, 1}, target = 30

``````public static List<List<Integer>> findSubarrays(int[] arr, int target) {
List<List<Integer>> subarrays = new ArrayList<>();
int lp = 0, rp = 0, currProd = 1;
for(rp = 0; rp < arr.length; rp++) {
if(arr[rp] < target)
currProd *= arr[rp];
if(currProd < target && currList.size() > 1) {
}
else {
while(currProd >= target) {
currProd /= arr[lp++];
currList.removeFirst();
}
if(currList.size() > 1)