Repository: TheAlgorithms/Java
Pull request #5848 (2024-10-15 10:16:55)

Added Maximum Sliding Window algorithm using deque for efficient O(n) solution.
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5848?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `0%` with `21 lines` in your changes missing coverage. Please review.
> Project coverage is 65.97%. Comparing base [(`be70801`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/be70801aa2fde9d9f183a3ae8d7f787fbc372992?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`3f4f359`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/3f4f359aa2988d180fe4d1e4fb47da83fde7ec25?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5848?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...com/thealgorithms/others/MaximumSlidingWindow.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5848?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fothers%2FMaximumSlidingWindow.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9vdGhlcnMvTWF4aW11bVNsaWRpbmdXaW5kb3cuamF2YQ==) | 0.00% | [21 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5848?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5848      +/-   ##
============================================
- Coverage     66.07%   65.97%   -0.10%     
+ Complexity     4416     4415       -1     
============================================
  Files           606      607       +1     
  Lines         16845    16866      +21     
  Branches       3237     3242       +5     
============================================
- Hits          11130    11128       -2     
- Misses         5267     5289      +22     
- Partials        448      449       +1     
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5848?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

pranayh24: Pull Request Description
Title: Add Maximum Sliding Window Algorithm Implementation

Overview: This pull request adds an implementation of the Maximum Sliding Window algorithm using a deque (double-ended queue) for efficient O(n) time complexity. The algorithm allows you to find the maximum value in every sliding window of size k in an array of integers.

Key Features:

Efficient Implementation: Utilizes a deque to maintain the indices of useful elements in the current window, allowing for optimal performance.
Input and Output:
Input: An array of integers and a window size k.
Output: An array of the maximum values for each sliding window.
Space Complexity: O(k) for the deque, which holds at most k elements at any time.

Feedback: I welcome any feedback or suggestions for improvements on this implementation.



Patch:
diff --git a/src/main/java/com/thealgorithms/others/MaximumSlidingWindow.java b/src/main/java/com/thealgorithms/others/MaximumSlidingWindow.java
new file mode 100644
index 00000000..d0b2c2a0
--- /dev/null
+++ b/src/main/java/com/thealgorithms/others/MaximumSlidingWindow.java
@@ -0,0 +1,56 @@
+package com.thealgorithms.others;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+
+/**
+ * Maximum Sliding Window Algorithm
+ *
+ * This algorithm finds the maximum element in each sliding window of size k
+ * in a given array of integers. It uses a deque (double-ended queue) to
+ * efficiently keep track of potential maximum values in the current window.
+ *
+ * Time Complexity: O(n), where n is the number of elements in the input array
+ * Space Complexity: O(k), where k is the size of the sliding window
+ */
+
+public class MaximumSlidingWindow {
+
+    /**
+     * Finds the maximum values in each sliding window of size k.
+     *
+     * @param nums The input array of integers
+     * @param windowSize The size of the sliding window
+     * @return An array of integers representing the maximums in each window
+     */
+    public int[] maxSlidingWindow(int[] nums, int windowSize) {
+        if (nums == null || nums.length == 0 || windowSize <= 0 || windowSize > nums.length) {
+            return new int[0]; // Handle edge cases
+        }
+
+        int[] result = new int[nums.length - windowSize + 1];
+        Deque<Integer> deque = new ArrayDeque<>();
+
+        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
+
+            // Remove the first element if it's outside the current window
+            if (!deque.isEmpty() && deque.peekFirst() == currentIndex - windowSize) {
+                deque.pollFirst();
+            }
+
+            // Remove all elements smaller than the current element from the end
+            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[currentIndex]) {
+                deque.pollLast();
+            }
+
+            // Add the current element's index to the deque
+            deque.offerLast(currentIndex);
+
+            // If we have processed at least k elements, add to result
+            if (currentIndex >= windowSize - 1) {
+                result[currentIndex - windowSize + 1] = nums[deque.peekFirst()];
+            }
+        }
+        return result;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/others/MaximumSlidingWindowTest.java b/src/test/java/com/thealgorithms/others/MaximumSlidingWindowTest.java
new file mode 100644
index 00000000..9209136a
--- /dev/null
+++ b/src/test/java/com/thealgorithms/others/MaximumSlidingWindowTest.java
@@ -0,0 +1,63 @@
+package com.thealgorithms.others;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import org.junit.jupiter.api.BeforeEach;
+import org.junit.jupiter.api.Test;
+
+class MaximumSlidingWindowTest {
+
+    MaximumSlidingWindow msw;
+    int[] nums;
+    int k;
+
+    @BeforeEach
+    void setUp() {
+        msw = new MaximumSlidingWindow(); // Initialize the MaximumSlidingWindow object
+    }
+
+    // Test for a simple sliding window case
+    @Test
+    void testMaxSlidingWindowSimpleCase() {
+        nums = new int[] {1, 3, -1, -3, 5, 3, 6, 7};
+        k = 3;
+        int[] expected = {3, 3, 5, 5, 6, 7};
+        assertArrayEquals(expected, msw.maxSlidingWindow(nums, k));
+    }
+
+    // Test when window size is 1 (output should be the array itself)
+    @Test
+    void testMaxSlidingWindowWindowSizeOne() {
+        nums = new int[] {4, 2, 12, 11, -5};
+        k = 1;
+        int[] expected = {4, 2, 12, 11, -5};
+        assertArrayEquals(expected, msw.maxSlidingWindow(nums, k));
+    }
+
+    // Test when the window size is equal to the array length (output should be a single max element)
+    @Test
+    void testMaxSlidingWindowWindowSizeEqualsArrayLength() {
+        nums = new int[] {4, 2, 12, 11, -5};
+        k = nums.length;
+        int[] expected = {12}; // Maximum of the entire array
+        assertArrayEquals(expected, msw.maxSlidingWindow(nums, k));
+    }
+
+    // Test when the input array is empty
+    @Test
+    void testMaxSlidingWindowEmptyArray() {
+        nums = new int[] {};
+        k = 3;
+        int[] expected = {};
+        assertArrayEquals(expected, msw.maxSlidingWindow(nums, k));
+    }
+
+    // Test when the window size is larger than the array (should return empty)
+    @Test
+    void testMaxSlidingWindowWindowSizeLargerThanArray() {
+        nums = new int[] {1, 2, 3};
+        k = 5;
+        int[] expected = {}; // Window size is too large, so no result
+        assertArrayEquals(expected, msw.maxSlidingWindow(nums, k));
+    }
+}