educative.io

Could this be N^2 worst case?

Courses
,
#1

This is a somewhat ugly solution, but it seems to be N^2 worst case instead of N^3

public static List<List<Integer>> findSubarrays(int[] arr, int target) {
    List<List<Integer>> subarrays = new ArrayList<>();
    
    if(arr == null || arr.length == 0) {
      return subarrays;
    }

    int start = 0;
    int end = 0;
    int prod = 1;
    LinkedList<Integer> acc = new LinkedList<>();
    while(start <= end && start < arr.length) {      
      if(end < arr.length && (prod * arr[end]) < target) {
        acc.add(arr[end]);
        subarrays.add(new ArrayList<>(acc));
        prod *= arr[end];
        end++;
      }
      else {
        if(!acc.isEmpty()) {
          acc.removeFirst();     
          if(!acc.isEmpty()) {
            subarrays.add(new ArrayList<>(acc));
          }
        }        
        prod /= arr[start];
        start++;
      }
    }

    if(prod < target && !acc.isEmpty()) {
      subarrays.add(acc);
    }

    return subarrays;
  }

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5902703286812672