# Why do we need a 3rd Loop, can it be done in 2 loops?

I was trying to write the solution for this question following the sliding window pattern.
for each iteration I lock the left position and slide right until the product is less than target.
We can slide the right pointer safely , since we now the array can contain only positive numbers

With this approach we do it in O(n^2), Am I doing anything wrong ?

`````` public static List<List<Integer>> findSubarrays(int[] arr, int target) {
List<List<Integer>> result = new ArrayList<>();

int product;
int left = 0;

while (left < arr.length) {

if (arr[left] < target) {
int right = left;
List<Integer> tempList = new ArrayList<>();
product = arr[right];
while (product < target && right < arr.length) {
right++;
if (right < arr.length) {
product *= arr[right];
}
}
}
left++;
}
return result;
}``````

I did something similar

``````public static List<List<Integer>> findSubarrays(int[] arr, int target) {
List<List<Integer>> subarrays = new ArrayList<>();
// TODO: Write your code here
for(int left=0; left < arr.length; left++) {
int currProd = arr[left];
if(arr[left] < target) {
}
List<Integer> subset = new ArrayList<>();
for(int right=left+1;right<arr.length; right++) {
currProd = currProd * arr[right];
if(currProd < target) {
} else {
break;
}
}
}
return subarrays;
}``````

Same here, looks like possible to do in O(n^2).
Anything I’m doing wrong?

``````def find_subarrays(arr, target):
if len(arr) < 1:
return []

result = []
left = 0
result.append([arr[left]])
right = 1

while right < len(arr):
prod = 1
sub = []
for i in range(left, right + 1):
prod *= arr[i]
sub.append(arr[i])

if prod < target:
result.append(sub)
right += 1
else:
left += 1
result.append([arr[left]])

return result
``````
``````import java.util.*;
``````

class SubarrayProductLessThanK {

public static List<List> findSubarrays(int[] arr, int target) {
List<List> subarrays = new ArrayList<>();

``````  for(int left = 0; left < arr.length; left++) {
List<Integer> current = new ArrayList<>();
int currProduct = 1; // needs to be one so multiplying gets a result.
for(int right = left; right < arr.length; right++) {
currProduct = currProduct * arr[right];
if(currProduct < target) {
}
else {
break;
}
}
}
//System.out.println(subarrays.toString());
return subarrays;
``````

}
}

Yeah I managed to do it in two for loops with an ArrayList getting populated as I went.

Creating a list from an existing list takes O(n), that’s why all the above algorithms are O(n^3). Here is the line that creates a new list from an existing list: