Sliding Window Maximum
Monotonic Stack & Queue Problems DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Find the maximum element in each sliding window of size k in an array (Max Sliding Window problem), Arrays, Sliding Window, Queue, Brute Force, Optimization, Time Complexity, Space Complexity, Loops, Conditional Statements, Data Structures, sliding window, brute force, deque, sliding window optimization, time complexity analysis, Sliding Window Technique, Deque (Double-Ended Queue), Data Structure Operations.
Given an array of integers arr, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your task is to return an array containing the maximum element for each sliding window. Input Specification: An array of integers arr. An integer k, representing the window size. Output Specification: An array of integers, where each element is the maximum value within its corresponding sliding window. Examples: Example 1: Input: arr = [4,0, 1,3,5,3,6,8], k = 3 Output: [4,3,5,5,6,8] Explanation: Window position Max [4 0 1] 3 5 3 6 8 4 4 [0 1 3] 5 3 6 8 3 4 0 [ 1 3 5] 3 6 8 5 4 0 1 [3 5 3] 6 8 5 4 0 1 3 [5 3 6] 8 6 4 0 1 3 5 [3 6 8] 8 For each window of size k=3, we find the maximum element in the window and add it to our output array. Example 2: Input: arr = [20,25], k = 2 Output: [25] Explanation: There’s just one window of size 2 that is possible and the maximum of the two elements is our answer.