educative.io

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

Courses
,
#1

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) {
                    tempList.add(arr[right]);
                    result.add(new ArrayList<>(tempList));
                    right++;
                    if (right < arr.length) {
                        product *= arr[right];
                    }
                }
            }
            left++;
        }
        return result;
    }
#2

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) {
        subarrays.add(Arrays.asList(arr[left]));
      }
      List<Integer> subset = new ArrayList<>();
      subset.add(arr[left]);
      for(int right=left+1;right<arr.length; right++) {
        currProd = currProd * arr[right];
        if(currProd < target) {
          subset.add(arr[right]);
          subarrays.add(subset);
        } else {
          break;
        }
      }
    }
    return subarrays;
  }
#3

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
#4 
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++) {
      current.add(arr[right]);
      currProduct = currProduct * arr[right];
      if(currProduct < target) {
        subarrays.add(new ArrayList<Integer>(current));
      }
      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.

#5

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:

subarrays.add(new ArrayList(current));