0

I have given interview with one company where they asked me Sliding Window Minimum value problem as below -

 Find maximum value of minimum values in sub-array of size x
 e.g. arr = [2,5,4,6,8] and x = 3 then subarray would be [2,5,4], [5,4,6] and [4,6,8]. 
 The respective minimum values are 2,4 and 4. The maximum of these values is 4.

I have return below code but it is giving Time Limit Exceeded for some test

public static int max(int x, List<Integer> num){
 int n = num.size();
 List<Integer> minList = new ArrayList<>();
 for(int i = 0; i <= n - x; i++){
    int minVal = Integer.MAX_VALUE;
    for(int j = i; j < i + x; j++){
        minVal = Math.min(min, num.get(j));
    }
    minList.add(minVal);
  }
  return Collections.max(minList);
}

Can someone correct it or point out for correct one.

risingStark
  • 1,161
  • 9
  • 17
ppb
  • 1,659
  • 3
  • 30
  • 63

1 Answers1

-2

The time complexity of your code is O(n*m), but there is a solution with time complexity O(n), it requires just a single pass through the array. For example, take a look here.

Alex Sveshnikov
  • 3,890
  • 1
  • 7
  • 25
  • Saying there is a solution without any hint at what that solution is, is not a *useful* answer. Might be a good comment, but it's not an answer. – Andreas Mar 15 '21 at 06:36
  • Link-only answers are not [good answers](https://meta.stackexchange.com/q/8231/351454). – Andreas Mar 15 '21 at 16:17