educative.io

Educative

Why can't this be solved in O(N) using just two pointers?

public static List<List<Integer>> findSubarrays(int[] arr, int target) {
    List<List<Integer>> subarrays = new ArrayList<>();
    // TODO: Write your code here
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] < target) {
            subarrays.add(List.of(arr[i]));
        }
        if (arr[i] * arr[i+1] < target) {
            subarrays.add(List.of(arr[i], arr[i+1]));
        }
    }
    if (arr[arr.length - 1] < target) {
        subarrays.add(List.of(arr[arr.length - 1]));
    }
    return subarrays;
}

Hi @Eddie_Tsedeke

I hope everything is going well with you. I will try my best to answer your query. Thank you for reaching out about this.

The given solution is just for the implementation purpose, there are many other solutions as well with the 0(n) complexity. So, you can use our provided solution or your own approach. It is great seeing our users thinking out of the box and coming up with betterments in the code. Your feedback is much appreciated!

I hope that this guide is helpful. Remember that I am always available via message to help you with any difficulty you might encounter.

Regards,
Happy Learning :slight_smile:

1 Like

Your algorithm doesn’t account for 3 digit pairs. Let’s say the target is 50 and we have {3,5,2}. Your algorithm would only output 3,5,2,{3,5},{5,2}. Sure, you could add another if statement for pairs of 3, then it wouldn’t work for pairs of 4,5…


Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Subarrays with Product Less than a Target (medium) - Grokking the Coding Interview: Patterns for Coding Questions

1 Like

Hi @Sathvik_Reddi, Thank you for contacting the Educative team with your query!

The algorithm used to solve the problem does account for 3-digit pairs. If your input array is {3,5,2} and the target is 50 it will include {3,5,2} in the result as a three-digit pair. Also, it is also working for 4,5,… pairs as well. I have attached the screenshot for your better understanding

Hope the answer to your query. Please feel free to reply here if there is still some confusion.

Hope you have an amazing learning experience on Educative!


i was talking to @Eddie_Tsedeke

1 Like

Hi @Sathvik_Reddi,

Thank you for your interest in this course. As you tagged the course instead of @Eddie_Tsedeke therefore, I thought there is some confusion in the algorithm shared in the lesson. Apologies for the inconvenience.

Happy learning :blush: