Problem:
Given an integer array and an Integer k, k represents a sliding window with size k that starts at the array's left end, moves one step at a time until reaches the array's right end. Each time the sliding window moves, it brings in a new number from right and removes an old number at left. Return an array which contains the max number in the sliding window at each move.For Example:
Given array [1,3,-1,-3,5,3,6,7], and k = 3
The output is: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
1 <= k <= array.length
Solution:
The brutal force solution is search k elements for the max at each array index from 0 to n - k. The time complexity will be nk.
There is a time complexity O(N) solution if we redesign the problem.
We can divide the original array into k sized chunks. When the k sized sliding window slides through the array, the chunk's boundary will cut the window into 2 parts. The original problem of finding the max value in the sliding window is converted to find the max value for the left half, max value for the right half, then combine the 2 max values we can find the max value in the sliding window.
 |
| imaginary boundary cut the k sized sliding window into 2 halves |
With the imaginary k sized boundary added, the rest of the work is easy. In order to find the max value for the left half of the sliding window, we only have to scan from the boundary leftward, for the max value for the right half of the sliding window, we only have to scan from the boundary rightward. We can scan these max values and store them in array left and right. Then we can iterate the original array, use the pre-scanned left and right max value arrays to find the left half and right half's max values.
import java.util.*;
public class Solution {
public static int[] maxNum(int[] arr, int k) {
int n = arr.length;
int[] result = new int[n - k + 1];
int[] left = new int[n];
int[] right = new int[n];
left[0] = arr[0];
right[n - 1] = arr[n - 1];
for(int i = 1; i < n; i++) {
//left -> right
if(i % k == 0) {
left[i] = arr[i]; //reset max at boundary
} else {
left[i] = Math.max(left[i - 1], arr[i]); //compare with left
}
//right -> left
if((n - i) % k == 0) {
right[n - i - 1] = arr[n - i - 1]; //reset max at boundary
} else {
right[n - i - 1] = Math.max(right[n - i], arr[n - i - 1]); //compare with right
}
}
for(int i = 0; i <= n - k; i++) {
result[i] = Math.max(right[i], left[i + k - 1]); //right[i] is the max value of the sliding window's left half
}
return result;
}
public static void main(String...args) {
int[] arr = new int[]{1,3,-1,-3,5,3,6,7};
for(int i : maxNum(arr, 3)) {
System.out.print(i + " ");
}
}
}
public class Solution {
public static int[] maxNum(int[] arr, int k) {
int n = arr.length;
int[] result = new int[n - k + 1];
int[] left = new int[n];
int[] right = new int[n];
left[0] = arr[0];
right[n - 1] = arr[n - 1];
for(int i = 1; i < n; i++) {
//left -> right
if(i % k == 0) {
left[i] = arr[i]; //reset max at boundary
} else {
left[i] = Math.max(left[i - 1], arr[i]); //compare with left
}
//right -> left
if((n - i) % k == 0) {
right[n - i - 1] = arr[n - i - 1]; //reset max at boundary
} else {
right[n - i - 1] = Math.max(right[n - i], arr[n - i - 1]); //compare with right
}
}
for(int i = 0; i <= n - k; i++) {
result[i] = Math.max(right[i], left[i + k - 1]); //right[i] is the max value of the sliding window's left half
}
return result;
}
public static void main(String...args) {
int[] arr = new int[]{1,3,-1,-3,5,3,6,7};
for(int i : maxNum(arr, 3)) {
System.out.print(i + " ");
}
}
}
We need to iterate the array once to generate the max value array left and right, we need to iterate the array the second time to calculate the sliding window's left and half max value, then combine them to find the max value in the sliding window. The time complexity is O(N), the space complexity is O(N) because of the left and right array for max values.
