educative.io

Why do we only check the first index for falling out of the current window in the window deque?

Courses
,
#1

Why do we only check the first index for falling out of the current window in the window deque ? Shouldn’t all the previous indexes from the previous iterations be checked to be safe ?

Corresponding code:
// Remove first index from the window deque if
// it doesn’t fall in the current window anymore
if ((!window.isEmpty()) && window.peek()<= (i - windowSize))
window.removeFirst();

Course: Grokking Coding Interview Patterns in Java - Learn Interactively
Lesson: Solution: Find Maximum in Sliding Window - Grokking Coding Interview Patterns in Java

1 Like
#2

did you figure it out

#3

Hello @Anuj_Johri and @AHMED_IBRAHIM_HASSAN ,

I hope you are fine,

Since we only keep track of two indexes in the deque window, the first index represents the maximum value in the current window. As the window moves, and the first element leaves the window, we discard it and the next element becomes the highest element in the window. Now, when a new element is added, we compare it with the elements present in the deque.

We hope you enjoy your experience with us at Educative! Happy learning!

#4

Hi
I have the same question as to why we don’t check every element in the current_window if it belongs to the previous window.
Why only checking the first element is enough?
The answer above is not clear to me.
Thanks for the help.

#5

Hi, @Nikki
I hope the following explanation will help you understand the logic. If it doesn’t, kindly let me know i will send you a Dry run of the algo.

In this sliding window problem, the cleanUp function is used to remove elements from the currentWindow that are not relevant to the current window being considered. The key point is that elements in currentWindow are stored in descending order of their values.

When checking if an element belongs to the previous window, the code specifically checks the first element of currentWindow (currentWindow.getFirst()). This is because elements in currentWindow are stored in descending order, and the first element represents the maximum value in the current window.

Here’s the relevant part of the code:

while (currentWindow.size() != 0 && nums[i] >= nums[currentWindow.getLast()]) {
    currentWindow.removeLast();
}

This loop removes elements from the end of currentWindow until the current element (nums[i]) is greater than or equal to the value represented by the last element in currentWindow. Since the elements in currentWindow are in descending order, this ensures that the maximum element of the current window is always at the front (first) of the deque.

By checking and updating only the first element, the code efficiently maintains the maximum element in the current window and removes elements that are no longer relevant. This approach avoids unnecessary comparisons with other elements in the currentWindow that are already known to be smaller than the current element. It optimizes the algorithm by taking advantage of the descending order of elements in the deque.

I hope this helps.