educative.io

Educative

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

Courses
,
#1 
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) {
        subarrays.add(Arrays.asList(currentNumber)); // 2, 5,[2,5],3,[5,3],10
        currentList.add(currentNumber); // 5,3
      }
      if (currentList.size()>1) {
        while(currentProduct>=target) {
          currentProduct /= arr[start++];
          currentList.remove(0);
        }
        if (currentProduct < target && currentList.size()>1) {
          subarrays.add(new ArrayList<>(currentList));
        }
      }
    }
    return subarrays;
  }
}
#2

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 :blush:

1 Like
#3

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;
		LinkedList<Integer> currList = new LinkedList<>();
		for(rp = 0; rp < arr.length; rp++) {
			if(arr[rp] < target)
				subarrays.add(Arrays.asList(arr[rp]));
			currProd *= arr[rp];
			if(currProd < target && currList.size() > 1) {
				currList.addLast(arr[rp]);
				subarrays.add(new ArrayList<>(currList));
			}
			else {
				currList.addLast(arr[rp]);
				while(currProd >= target) {
					currProd /= arr[lp++];
					currList.removeFirst();
				}
				if(currList.size() > 1)
					subarrays.add(new ArrayList<>(currList));
			}
		}
		while(currList.size() > 2) {
			currList.removeFirst();
			subarrays.add(new ArrayList<>(currList));
		}
		return subarrays;
}

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

Thank You :blush: