Objective: Given an array and integer k, write an algorithm to find the maximum element in each subarray of size k.
Example:
int [] nums = { 1, 2, 3, 2, 4, 1, 5, 6,1}; Output: 3, 3, 4, 4, 5, 6, 6 Subarrays – [1, 2, 3], max = 3 [2, 3, 2], max = 3 [3, 2, 4], max = 4 [2, 4, 1], max = 4 [4, 1, 5], max = 5 [1, 5, 6], max = 6 [5, 6, 1], max = 6
Approach:
Naïve Approach:
- Have 2 nested loops.
- Outer loop will navigate the array.
- Inner loop with track the maximum element in every k elements (all k windows or all subarrays with size k)
Time Complexity: O(nk) where n is the size of array and k is the subarrays size.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class SlidingWindowMaximumNaive { | |
public void slidingWindow(int [] nums, int k){ | |
for (int i = 0; i <nums.length – k ; i++) { | |
int max = nums[i]; | |
for (int j = 1; j<=k ; j++) { | |
if(nums[i+j]>max) | |
max = nums[i+j]; | |
} | |
System.out.print(max + " "); | |
} | |
} | |
public static void main(String[] args) { | |
int [] nums = {1, 2, 3, 2, 4, 1, 5, 6, 1}; | |
int k = 3; | |
SlidingWindowMaximumNaive s = new SlidingWindowMaximumNaive(); | |
s.slidingWindow(nums, k); | |
} | |
} |
Output:
3 3 4 4 5 6 6
Using Deque: Time complexity O(n)
- Use Deque – Double ended queue and store only the data which is necessary or useful. Will store the index of array element in deque to keep track of k elements.
- Deque will always have the data for max k elements (window). Initially will create the deque with first k elements and then slide the window by one element at a time, means discard the data which falls outside the new window and all data which falls within the new window.
- To create the window for first k elements –
- Every new element going into window(deque), Remove all the smaller elements indexes from the deque (since these elements are no longer required) and add the new element at the end.
- Once the window is created for first k elements then for every new element going into window(deque) –
- Remove the element index which falls outside the window.
- And again remove all the smaller elements indexes from the deque (since these elements are no longer required) and add the new element index at the end.
- Output from each window will be the first element in the deque (since deque is constructed in descending order as per the steps above.
Time Complexity: O(n), Space Complexity: O(k)
Example:
int [] nums = { 11,12, 13, 12, 14, 11, 10, 9}; K = 3 Create deque for first k elements int [] nums = { 11,12, 13, 12, 14, 11, 10, 9}; Deque: Output: __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; NOTE : we are adding the array index, not element Deque: 0 Output: __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 12>11, remove 11 from deque and add 12’s index at the end Deque: 1 Output: __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 13>12, remove 12 from deque and add 13’s index at the end Deque: 2 Output: 13 (First index in deque) At this point our first window with k elements is prepared. Now we will start discarding the elements from the deque which falls outside the window. __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 1. Indexes for new window 1-3 so remove indexes less than 1 from deque if present. 2. 12<13, add 12’s index at the end Deque: 2 3 Output: 13 13 __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 1. Indexes for new window 2-4 so remove indexes less than 2 from deque if present. 2. 14>12, remove 12 and 14>13, remove 13. Add 14 at the end Deque: 4 Output: 13 13 14 __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 1. Indexes for new window 3-5 so remove indexes less than 3 from deque if present. 2. 11< 14, Add 11 at the end Deque: 4 5 Output: 13 13 14 14 __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 1. Indexes for new window 4-6 so remove indexes less than 4 from deque if present. 2. 10< 11, Add 10 at the end Deque: 4 5 6 Output: 13 13 14 14 14 __________________________________ int [] nums = { 11, 12, 13, 12, 14, 11, 10, 9}; 1. Indexes for new window 4-7 so remove indexes less than 4 from deque if present. So 4 will be removed from deque. 2. Deque: 5 6 3. 9< 10, Add 9 at the end Deque: 5 6 7 Output: 13 13 14 14 14 11 __________________________________
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Deque; | |
import java.util.LinkedList; | |
public class SlidingWindowMaximum_Deque { | |
public void slidingWindow(int [] nums, int k){ | |
Deque<Integer> deque = new LinkedList<>(); | |
//Step 1: handle first k elements in sliding window | |
for (int i = 0; i <k ; i++) { | |
//remove all the elements which are smaller than the current elements | |
while(deque.isEmpty()==false && nums[deque.peekLast()]<=nums[i]) | |
deque.removeLast(); | |
//add new element at the end | |
deque.addLast(i); | |
} | |
//Step 2: handle rest of the element, one at a time nums[k] to nums[n-1] | |
for (int i = k; i <nums.length ; i++) { | |
//before we do anything, print the first element in deque | |
//since its a maximum among previous k elements | |
System.out.print(nums[deque.peekFirst()] + " "); | |
//Now remove the elements which are out for next window (next k elements) | |
while(deque.isEmpty()==false && deque.peekFirst()<=i–k) | |
deque.removeFirst(); | |
//Add the next element in the window = index i | |
//remove all the elements which are smaller than the next element = index i | |
while(deque.isEmpty()==false && nums[deque.peekLast()]<=nums[i]) | |
deque.removeLast(); | |
//add new element at the end | |
deque.addLast(i); | |
} | |
//to print the last max element | |
System.out.print(nums[deque.peekFirst()] + " "); | |
} | |
public static void main(String[] args) { | |
int [] nums = {1, 2, 3, 2, 4, 1, 5, 6, 1}; | |
int k = 3; | |
SlidingWindowMaximum_Deque s = new SlidingWindowMaximum_Deque(); | |
s.slidingWindow(nums, k); | |
} | |
} |
Output:
3 3 4 4 5 6 6
Line 5 in Nested Loop approach
should be
i <= nums.length -k
Index is starting from 0 that is why is < instead of <=
Deque approach is not printing the max element of the last window.
Need one sop statement out of for loop for printing last element
Thanks Lipsa. Corrected the code.
in nested loop approach line no 7 should be
for (int j = 1; j <= k ; j++)
Thanks Gaurav, Corrected the code.
Can you post solution of Maximum Unsorted Subarray problem – https://www.interviewbit.com/problems/maximum-unsorted-subarray/