sol_067.md

Sliding Window Maximum - Practice - Work@Tech

You are given an array of integers A and a number k which represents the size of the window. The window covers k elements and starts at the left-end of the array. The window moves one index to the right at every step.

You need to return an array with the max element inside the window at every step.

Example:1

Input: 
1 2 3 4
2

Output: 
2 3 4

Example:2

Input: 
1 -1 3 4 5
3

Output: 
3 4 5

Solution 1

Time - O(N * K)
Space - O(1)

vector<int> maxSlidingWindow(vector<int> &A, int k) {
    // add your logic here
	vector<int> ans;
	int n = A.size();
	int maxVal;
	for (int i = 0; i < n-k+1; i++){
		maxVal = A[i];
		for (int j = 1; j < k; j++){
			maxVal = max(maxVal, A[i+j]);
		}
		ans.push_back(maxVal);
	}
	return ans;
}

Solution 2

Time - O(N)
Space - O(N)

 vector<int> maxSlidingWindow(vector<int> &A, int k) {
    // add your logic here
	int n = A.size();
	deque<int> dq;
	vector<int> ans(n-k+1);
	for (int i = 0; i < n; i++){
		if (!dq.empty()){
			 // remove out of window element from front of dq
			if (dq.front() == i-k){
				dq.pop_front();
			}

			// remove elements which is less then curr element from back of dq
			while (!dq.empty() && A[dq.back()] < A[i]){ 
				dq.pop_back();
			}
		}            

		dq.push_back(i);

		// add elements to ans vector after scan k size window
		if(i >= k-1 && !dq.empty()){ 
			ans[i-k+1] = A[dq.front()];
		}
	}
	return ans;
}