package com.thealgorithms.datastructures.queues;
import java.util.Deque;
import java.util.LinkedList;
/**
* The {@code SlidingWindowMaximum} class provides a method to efficiently compute
* the maximum element within every sliding window of size {@code k} in a given array.
*
* <p>The algorithm uses a deque to maintain the indices of useful elements within
* the current sliding window. The time complexity of this approach is O(n) since
* each element is processed at most twice.
*
* @author Hardvan
*/
public final class SlidingWindowMaximum {
private SlidingWindowMaximum() {
}
/**
* Returns an array of the maximum values for each sliding window of size {@code k}.
* <p>If {@code nums} has fewer elements than {@code k}, the result will be an empty array.
* <p>Example:
* <pre>
* Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
* Output: [3, 3, 5, 5, 6, 7]
* </pre>
*
* @param nums the input array of integers
* @param k the size of the sliding window
* @return an array containing the maximum element for each sliding window
*/
public static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n < k || k == 0) {
return new int[0];
}
int[] result = new int[n - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// Remove elements from the front of the deque if they are out of the current window
if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove elements from the back if they are smaller than the current element
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
// Add the current element's index to the deque
deque.offerLast(i);
// Store the maximum element for the current window (starting from the k-1th element)
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
}