educative.io

Wny not brute force if time complexity is N^3?

Courses
,
#1

Why nto brute force as below?
run a loop i=0 to arr.length
within the loop run another loop i to arr.length and compute product as you go and add to the result array. break if product > target
Although both tests pass, it will be more accurate if I sort beforehand.

import java.util.*;

class SubarrayProductLessThanK {

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

int right = 0 ; // TODO: Write your code here
int currentProduct = 1;
int left = 0;
for (int i = 0 ; i < arr.length; i++){
left = i;
right = i;
currentProduct = 1;
while (right < arr.length){
currentProduct *= arr[right];
if (currentProduct < target){

      ArrayList<Integer> desiredArray = new ArrayList<>();
      for (int j = left ; j <=right; j++){
        desiredArray.add(arr[j]);
      }
      subarrays.add(desiredArray);
      right++;
    }
    else{        
      break;
    }

  }
}
return subarrays;

}
}

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

#2

Hi @bee1,

We appreciate your feedback.
Yes, you are right! we can use brute-force technique as you suggested but this is an interview preparation course and this particular example (as mentioned in the lesson) is inspired by the Triplets with Smaller Sum method. The chapter, “Pattern: Two Pointers”, includes the examples that are solved using two pointers with finding patterns. In this example, we are using two pointers (or array indexes) to find the largest subset array pattern and then creating the possible subarrays which leads the algorithm’s time complexity to O(N^3) in worst case. However, the average time complexity is not the same as worst in this algorithm.

The brute-force solution is never a good option neither to implement nor to show to the interviewer. Including to this, the difference between brute force and this algorithm is that the brute-force always ends up in worst time complexity. Brute-force algorithms will always perform in O(N^3) time complexity in the best case too. But this algorithm can work faster in average and best case in comparison to brute-force.

If you still have any confusion, please let us know.
Thanks.