NUHMAN.com

🔍 Problem Statement

Given an array nums, there is a sliding window of size k which is moving from the very left to the very right of the array. You need to output the maximum value of the window as it moves.

Example 1:

go

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]

Example 2:

go

Input: nums = [1], k = 1
Output: [1]

🧠 Approach

The challenge is to maintain the maximum value of the sliding window as it slides across the array efficiently. A brute-force approach would involve recalculating the maximum for every window, but this would be inefficient, especially for larger arrays, resulting in O(n * k) time complexity.

To solve the problem efficiently, we can use a Deque (double-ended queue) to keep track of indices of the elements that might be the maximum in the window.

Key Insights:

1. Use a deque (double-ended queue) to store indices of elements in the array. The deque is maintained such that:

• The elements in the deque are in decreasing order of their values.
• The front of the deque will always have the index of the largest element for the current window.

1. Window sliding:

• As the window slides, elements that are out of the window are removed from the front of the deque.
• New elements are added to the deque, ensuring that smaller elements (that will never be the maximum in the current window) are removed from the back of the deque.

This approach ensures that each element is processed at most twice (once when added and once when removed from the deque), which results in an O(n) time complexity.

Steps:

1. Initialize a deque to store indices.
2. Iterate through the array:

• For each element, remove elements from the back of the deque if they are smaller than the current element.
• Add the current index to the deque.
• Remove elements from the front if they are out of the window.
• If the window size has reached k, add the maximum (i.e., the element at the front of the deque) to the result.

✅ Go Implementation

go

package main

import "fmt"

// Function to return the maximums in each sliding window
func maxSlidingWindow(nums []int, k int) []int {
    n := len(nums)
    if n == 0 || k == 0 {
        return nil
    }

    result := []int{}
    deque := []int{}  // Deque to store indices

    for i := 0; i < n; i++ {
        // Remove indices that are out of the current window
        if len(deque) > 0 && deque[0] < i-k+1 {
            deque = deque[1:]
        }

        // Remove elements from the back of the deque while the current element is larger
        // than the element at those indices
        for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] {
            deque = deque[:len(deque)-1]
        }

        // Add current element index at the back of the deque
        deque = append(deque, i)

        // Start adding the maximums to the result list once the window has reached size k
        if i >= k-1 {
            result = append(result, nums[deque[0]])  // The front of the deque is the largest element
        }
    }

    return result
}

// Helper function to print the array
func printArray(arr []int) {
    for _, num := range arr {
        fmt.Print(num, " ")
    }
    fmt.Println()
}

// Test the maxSlidingWindow function
func main() {
    // Example 1: Input nums = [1,3,-1,-3,5,3,6,7], k = 3
    nums1 := []int{1, 3, -1, -3, 5, 3, 6, 7}
    k1 := 3
    result1 := maxSlidingWindow(nums1, k1)
    printArray(result1) // Output: [3 3 5 5 6 7]

    // Example 2: Input nums = [1], k = 1
    nums2 := []int{1}
    k2 := 1
    result2 := maxSlidingWindow(nums2, k2)
    printArray(result2) // Output: [1]
}

🧑‍💻 Explanation of the Code

1. maxSlidingWindow function:

• We initialize an empty result array to store the maximums for each window.
• The deque stores the indices of elements. The largest element in the current window will always be at the front of the deque.
• We iterate through the array, and for each element:
• Remove elements from the front of the deque if they are out of the window.
• Remove elements from the back of the deque if they are smaller than the current element (since they will never be useful).
• Add the current element’s index to the deque.
• Once the window size reaches k, add the element at the front of the deque to the result (this element is the largest in the window).

1. printArray function:

• This is a helper function that prints the array.

1. main function:

• It tests the maxSlidingWindow function with two example inputs and prints the results.

📦 Example Usage

go

func main() {
    // Example 1: Input nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
    nums1 := []int{1, 3, -1, -3, 5, 3, 6, 7}
    k1 := 3
    result1 := maxSlidingWindow(nums1, k1)
    printArray(result1) // Output: 3 3 5 5 6 7

    // Example 2: Input nums = [1], k = 1
    nums2 := []int{1}
    k2 := 1
    result2 := maxSlidingWindow(nums2, k2)
    printArray(result2) // Output: 1
}

Example Output:

3 3 5 5 6 7
1

⏱️ Time & Space Complexity

• Time Complexity: O(n)
• Each element is added and removed from the deque at most once, so the total time complexity is linear, O(n).
• Space Complexity: O(k)
• The deque stores up to k elements at any time, so the space complexity is O(k), which is the size of the sliding window.

This solution efficiently computes the sliding window maximums in linear time, making it optimal for large arrays.