Sliding Window Maximum #LeetCode

https://leetcode.com/problems/sliding-window-maximum/

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.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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
Therefore, return the max sliding window as [3,3,5,5,6,7].

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

Solution 1:

For each window, get maximum using a simple 1 by 1 comparison. O(k)
Total time complexity O(k) * N = O(kN).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: // quick solution vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; int size = nums.size(); if (size == 0) return result; for (int i = 0; i <= size - k; i++) { result.push_back(max(nums, i, i + k - 1)); } return result; } int max(vector<int>& nums, int start, int end) { int max = nums[start]; for (int i = start + 1; i <= end; i++) { if (nums[i] > max) max = nums[i]; } return max; } };

Solution 2:

Using a heap, for each window, remove 1 instance of the beginning element of previous window, and add 1 ending element or current window.
For each window, get maximum using 2 * O(log k)
Total time complexity 2 * O(log k) * N = O(logk * N).

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 41 42 43 44 45

class Solution { public: // quick solution std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) { std::vector<int> result; int size = nums.size(); if (size == 0) return result; // created an ordered std::map for numbers within window std::map<int, int> window; for (int i = 0; i < k; i++) { insertToMap(window, nums[i]); } result.push_back(window.rbegin()->first); int p = 0; while(p < size && p + k < size) { // update window popOffMap(window, nums[p]); insertToMap(window, nums[p+k]); // get the maximum within window result.push_back(window.rbegin()->first); p++; } return result; } void insertToMap(std::map<int, int>& map, int val) { if (map.find(val) != map.end()) map[val] = map[val] + 1; else map[val] = 1; } void popOffMap(std::map<int, int>& map, int val) { if (map[val] == 1) map.erase(val); else map[val] = map[val] - 1; } };