Reference: LeetCode
Difficulty: Hard

My Post: [Java] All Solutions (B-F, PQ, Deque, DP) with Explanation and Complexity Analysis

Problem

Given an array nums, 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. Return the max sliding window.

Note: You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [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

Follow up: Could you solve it in linear time?

Analysis

Brute-Force

Check every sliding window and compute the maximum value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  int n = nums.length;
  if (n == 0 || k == 0) {
    return new int[0];
  }
  
  int numOfWindow = n - k + 1;
  int[] result = new int[numOfWindow]; // number of windows
  
  for (int start = 0; start < numOfWindow; ++start) {
    int end = start + k - 1;
    int maxVal = nums[start];
    for (int i = start + 1; i <= end; ++i) {
      if (nums[i] > maxVal) { // update
        maxVal = nums[i];
      }
    }
    result[start] = maxVal;
  }
  
  return result;
}

Time: $O(Nk)$
Space: $O(1)$ not including the output array

Priority Queue

In theory, we can use priority queue to achieve $O(N\log{k})$. However, if we stick to the build-in PriorityQueue in Java, it still takes $O(Nk)$:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
  int i = indexOf(o);
  if (i == -1) {
    return false;
  } else {
    removeAt(i);
    return true;
  }
}

private int indexOf(Object o) {
  if (o != null) {
    final Object[] es = queue;
    for (int i = 0, n = size; i < n; i++) {
      if (o.equals(es[i])) return i;
    }
  }
  return -1;
}

The code in indexOf() shows that this naive method takes $O(N)$ time in the worst case. Therefore, if we use the built-in method in Java, it takes $O(Nk)$.

In terms of $O(N\log{k})$, the basic idea is that we are keeping the size of the heap as at most k by removing the elements that are out of the k-size window. If we assume that remove() takes $O(\log{k})$ time (if we implement the priority queue by ourselves), it would have that logarithmic time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  if (nums.length == 0 || k == 0) {
    return new int[0];
  }
  int n = nums.length;
  int[] result = new int[n - k + 1]; // number of windows
  
  PriorityQueue<Integer> maxPQ = new PriorityQueue<>((o1, o2) -> (o2 - o1)); // stores values
  
  for (int i = 0; i < n; ++i) {
    int start = i - k;
    if (start >= 0) {
      maxPQ.remove(nums[start]); // remove the out-of-bound value
    }
    maxPQ.offer(nums[i]);
    if (maxPQ.size() == k) {
      result[i - k + 1] = maxPQ.peek();
    }
  }
  return result;
}

This is the first version I came up with. I think for this solution we can dive deeper to see how PriorityQueue in Java works. Consider what would happen if there are duplicates in the heap. Which one to be removed?

Also notice that when we are using the wrapper class Integer in Java we notice the caching feature.

1
2
3
4
5
6
7
8
9
10
Integer val1 = 1;
Integer val2 = 1;
Integer val3 = 200;
Integer val4 = 200;
// comparing the values
val1.equals(val2); // true
val3.equals(val4); // true
// comparing the address
val1 == val2;      // true
val3 == val4;      // false

This occurs because Java does caching for integers between -128 and 127 for better performance. Here is the code in Integer class:

1
2
3
4
5
6
7
8
// Java 1.6 source code
public static Integer valueOf(int i) {
  if (i >= -128 && i <= IntegerCache.high) { // IntegerCache.high = 127
    return IntegerCache.cache[i + 128];
  } else {
    return new Integer(i);
  }
}

Back to the problem. Therefore, if there are duplicates between -128 and 127 in the heap, we cannot delete the object that we want (the leftmost element in the sliding window).

But do duplicates actually matter? In other words, do we really need to consider the case where we have duplicate elements in the window and decide which one to remove?

The answer is NO. We can just remove one of them. For the example {2, 4, 2, 5}, k = 3, removing the first or the second 2 is the same.

However, we can modify the code a little bit and let the priority queue know the specific element we want to remove.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Use indices since they are unique
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  if (nums.length == 0 || k == 0) {
    return new int[0];
  }
  int n = nums.length;
  int[] result = new int[n - k + 1]; // number of windows
  
  PriorityQueue<Integer> maxPQ = new PriorityQueue<>((i1, i2) -> (nums[i2] - nums[i1])); // stores values
  
  for (int i = 0; i < n; ++i) {
    int start = i - k;
    if (start >= 0) {
      maxPQ.remove(start); // remove the out-of-bound value by index
    }
    maxPQ.offer(i);
    if (maxPQ.size() == k) {
      result[i - k + 1] = nums[maxPQ.peek()];
    }
  }
  return result;
}

Time: $O(Nk)$ (if we implement PQ by ourselves, it is $O(N\log{k})$)
Space: $O(k)$

Deque

If we can add and remove elements from both sides of the sliding window, we can solve this problem in linear time. It turns out that we can use Deque to achieve the goal. In the Deque, we add and remove indices.

Basically, for each element nums[i] in the array that we are about to insert, we first check whether the leftmost index in the sliding window is out of bound. If so, we remove it by pollFirst() in constant time.

Then we continuously remove the rightmost indices if their corresponding elements are less than nums[i] (the element we are about to insert). The idea is that the elements that are less than the element we’ll insert won’t have any contributions to the maximum element of the sliding window. So it is safe to remove them.

After removal pollLast() and insertion offerLast(i) (the element nums[i]), we can say that the leftmost element in the window is maximum. Think about it why. Notice that the maximum element could be the one we just insert.

Last but not least, adding the maximum elements to the result array when necessary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  int n = nums.length;
  if (n == 0 || k == 0) {
    return new int[0];
  }
  int[] result = new int[n - k + 1]; // number of windows
  Deque<Integer> win = new ArrayDeque<>(); // stores indices
  
  for (int i = 0; i < n; ++i) {
    // remove indices that are out of bound
    while (win.size() > 0 && win.peekFirst() <= i - k) {
      win.pollFirst();
    }
    // remove indices whose corresponding values are less than nums[i]
    while (win.size() > 0 && nums[win.peekLast()] < nums[i]) {
      win.pollLast();
    }
    // add nums[i]
    win.offerLast(i);
    // add to result
    if (i >= k - 1) {
      result[i - k + 1] = nums[win.peekFirst()];
    }
  }
  return result;
}

Time: $O(N)$ since each element is processed (add/remove) at most twice.
Space: $O(k)$

DP

This method is very hacky. The explanation in solution section is readable.

Note: Don’t read the code of my first attempt.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// my first attempt
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  if (nums.length == 0 || k == 0) {
    return new int[0];
  }
  int n = nums.length;
  int[] result = new int[n - k + 1]; // number of windows
  
  // left & right
  int[] left = new int[n];
  int[] right = new int[n];

  for (int i = 0; i < n; ++i) {
    // left
    if (i % k == 0) { // beginning of the group
      left[i] = nums[i];
    } else {
      left[i] = Math.max(left[i - 1], nums[i]);
    }
    
    // right (* to be improved)
    int temp = (i / k + 1) * k - 1; // last of the group
    if (temp > n - 1) temp = n - 1;
    
    int j = temp - i % k;
    if (j % k == (k - 1) || j == n - 1) {
      right[j] = nums[j];
    } else {
      right[j] = Math.max(right[j + 1], nums[j]);
    }
  }
  
  // dp
  for (int i = 0, j = i + k - 1; j < n; ++i, ++j) {
    result[i] = Math.max(right[i], left[j]);
  }
  
  return result;
}

The better version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] maxSlidingWindow(int[] nums, int k) {
  // assume nums is not null
  if (nums.length == 0 || k == 0) {
    return new int[0];
  }
  int n = nums.length;
  int[] result = new int[n - k + 1]; // number of windows
  
  // left & right
  int[] left = new int[n];
  int[] right = new int[n];
  left[0] = nums[0]; // init
  right[n - 1] = nums[n - 1];
  
  for (int i = 1; i < n; ++i) {
    // left
    if (i % k == 0) left[i] = nums[i];
    else            left[i] = Math.max(left[i - 1], nums[i]);
    // right
    int j = n - i - 1;
    if (j % k == (k - 1)) right[j] = nums[j];
    else                  right[j] = Math.max(right[j + 1], nums[j]);
  }
  
  // dp
  for (int i = 0, j = i + k - 1; j < n; ++i, ++j) {
    result[i] = Math.max(right[i], left[j]);
  }
  
  return result;
}

Time: $O(N)$
Space: $O(N)$