educative.io

Educative

What is the need of such a complicated solution using Deque?

I don’t understand why do we need to use a Deque for this problem? The algorithm seems unncessarily complicated -

public static ArrayDeque<Integer> findMaxSlidingWindow(int[] arr, int windowSize) {

    ArrayDeque<Integer> result = new ArrayDeque<>(); // ArrayDeque for storing values

    Deque<Integer> list = new LinkedList<Integer>(); // creating a linked list

    if(arr.length > 0) {

      if( arr.length < windowSize) // Invalid State

        return result;

      for(int i = 0; i < windowSize; ++i) {

        // Removing last smallest element index

        while(!list.isEmpty() && arr[i] >= arr[list.peekLast()]){

          list.removeLast();      

        }

         

        // Adding newly picked element index

        list.addLast(i);

      }

      for(int i = windowSize; i < arr.length; ++i) {

        result.add(arr[list.peek()]);

        // Removing all the elements indexes which are not in the current window

        while((!list.isEmpty()) && list.peek() <= i-windowSize)

          list.removeFirst();

        // Removing the smaller elements indexes which are not required

        while((!list.isEmpty()) && arr[i] >= arr[list.peekLast()])

          list.removeLast();

        // Adding newly picked element index

        list.addLast(i);

      }

      // Adding the max number of the current window in the result

      result.add(arr[list.peek()]);

      return result; // returning result

    }

    else 

      return result;

  }

Why not just make a simple pass through the array and calculate the maximum number in each window?

public static ArrayDeque<Integer> findMaxSlidingWindow(int[] arr, int windowSize) {
    ArrayDeque<Integer> result = new ArrayDeque<>(); 
    //Write your code
    int max;
    for(int i = 0; i <= (arr.length-windowSize); i++) {
      max = arr[i];

      for(int k = i; k < (i+windowSize); k++) {
        if(arr[k] >= max) {
          max = arr[k];
        }
      }
      result.add(max);
    }
    return result; 
  }

The inner for loop only runs a constant ( = windowSize) number of times for each iteration of the outer loop, so total complexity is still O(n). It can be O(n^2) at the worst, if you consider the windowSize to be the entire array.

1 Like

I agree with all of it and even if the window size is the entire array the inner loop can be avoided be its just max element of the array so it should be O(n) .

1 Like

https://www.youtube.com/watch?v=m-Dqu7csdJk Watch this and you will know that it’s the best solution with o(n) complexity.

The following solution is also valid but I cannot comment on the complexity:

vector<int> find_max_sliding_window(vector<int>& v, int window_size)
{
    vector<int> result;
    int n = v.size() - window_size;
    for (auto i=0; i <= n ; ++i)
    {
        //cout << "i = " << i << endl;
        int* pFirst = &v[i];
        int* pLast = &v[i+window_size];
        int* pMaxVal = max_element(pFirst,pLast);
        result.push_back(*pMaxVal);
        //cout << *pMaxVal << endl;
    }
    return result;
}
1 Like

I also found the code solution to be quite long but after reading through carefully and reviewing the code, it is a great exercise.

The provided solution seems complicated to me. Perhaps the reason it is provided is because it is optimal, I am unsure. I agree there is educational value to reviewing it. Here is my solution:

let findMaxSlidingWindow = function(arr, window_size) {
  var result = [];
  //Write your code

  const length = arr.length + 1;
  
  let startIndex = 0;
  let endIndex = window_size;
  
  while (endIndex < length) {
    
    let subArr = arr.slice(startIndex, endIndex);
    result.push((Math.max(...subArr)));
    startIndex += 1;
    endIndex += 1;
    console.log(endIndex);

  };

  return result;
};
1 Like

I am also wondering why is the deque solution is better than ust finding max() in window?

def find_max_sliding_window(arr, window_size):
  result = []
  left=0
  right = left + window_size
  while right <= len(arr):
    result.append(max(arr[left:right]))
    left += 1
    right = left + window_size
  return result

Would be great to have a better explanation in the lesson