find maximum in sliding window and similar

Next-greater-workout.md

Problem 1

Given array and length of sliding window return array of maximum in each position for sliding window. leetcode

Solution

The algorithm outlook is the following:

1. Precompute array containing for each value nums[i] index of the following value less than nums[i]
2. Iterate over the array using the index pointing to the end. Assume you have computed the maximum in the widow [] as shown below:

i - k      i 
[x .. y] z

Now you need to add a new element z to the window and eliminate element x. To do that, you need to consider different cases (look into the code). The most interesting case if whem x was the minimum on the window. In this case, you need to look for the smallest element in the window using precompute at phase (1) array.

class Solution {
public:
    // For a given index i, finds and saves index of 
    // the first greater element on the right side.
    // If it doesn't exist, -1
    vector<int> findNextGreater(const vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        stack<int> indices;
        for (int i = 0; i < nums.size(); ++i) {
            while (!indices.empty() &&
                   nums[indices.top()] < nums[i]) {
                res[indices.top()] = i;
                indices.pop();
            }
            indices.push(i);
        }
        return res;
    }
    
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        if (nums.size() == 0 || nums.size() < k) return {};
        
        const vector<int>& nextGreater = findNextGreater(nums);
        vector<int> res;
        res.reserve(nums.size() + 1 - k);
        int maxV = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            if (i < k) {
                // just find maximum for the first k elements
                maxV = max(maxV, nums[i]);
                if (i == k - 1)
                    res.push_back(maxV);
            } else {
                // Now i-th element is not yet in the window
                // and we need to exclude (i-k)-th element
                // there are might be options:
                if (nums[i] >= maxV) {
                    // 1) If new element nums[i] >= maxV, just update max
                    maxV = max(maxV, nums[i]);
                } else if (maxV == nums[i-k]) {
                    // 2) if (i-k)-th element wasn't maxV - don't need to do anything
                    // but otherwise we need to find index of next greater for (i-k+1)-th
					// while in the window
                    int ins = i-k+1;
                    int prev = -1;
                    while (ins != -1 && ins <= i) {
                        prev = ins;
                        ins = nextGreater[ins];
                    }
                    maxV = nums[prev];
                }
                res.push_back(maxV);
            }
        }
        return res;
    }
};

Problem 2

max histogram.

Solution

The idea is very simple: for each bar find the area of the rectangle where this bar height defines the height of the whole rectangle. To do that in O(n), we need to find in O(1) the following indices:

1. Index of the first element on the left from current i which is smaller than heights[i]

2. Index of the first element on the right from current i which is smaller than heights[i]

    vector<int> getNextSmaller(const vector<int>& heights) {
        stack<int> st;
        vector<int> res(heights.size(), heights.size());
        for (int i = 0; i < heights.size(); ++i) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                res[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        
        return res;
    }
    // exactly the same as above except for the order
    // and the default element here is -1 (assume the the smaller element is before the start of the array)
    vector<int> getPrevSmaller(const vector<int>& heights) {
        stack<int> st;
        vector<int> res(heights.size(), -1);
        for (int i = heights.size() - 1; i >= 0; --i) {
            while (!st.empty() && heights[st.top()] > heights[i]) {
                res[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }
        
        return res;
    }
    
    int largestRectangleArea(vector<int>& heights) {
        if (heights.size() == 0) return 0;
        
        auto nextSmaller = getNextSmaller(heights);
        auto prevSmaller = getPrevSmaller(heights);
        
        int res = 0;
        for (int i = 0; i < heights.size(); ++i) {
            int r = nextSmaller[i];
            int l = prevSmaller[i];
            res = max(res, heights[i]*(r - l - 1));
        }
        
        return res;
    }

Problem 3

The problem is to find sum_i sum_j {max(segment[i,j]) - min(segment[i,j]}. See cf

Solution

// The problem is to find sum_i sum_j {max(segment[i,j]) - min(segment[i,j]}
// The main observation is that sum(i,j) of max - min = sum(i,j) max - sum(i,j) min
// To find sum of all the maximums we find how many time each number might be maximum by using standard 
// technique of looking forward/backward
// https://codeforces.com/contest/817/problem/D
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

// For a given index i, finds and saves index of 
// the first greater element on the right side.
// If it doesn't exist, -1
vector<int> findNextGreater(const vector<int>& nums) {
    vector<int> res(nums.size(), nums.size());
    stack<int> indices;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!indices.empty() &&
               nums[indices.top()] < nums[i]) {
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findPrevGreater(const vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> indices;
    for (int i = (int)nums.size() - 1; i >= 0 ; --i) {
        while (!indices.empty() &&
               nums[indices.top()] <= nums[i]) { // Note <= is to tackle the nearest because there are dublicates
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findNextSmaller(const vector<int>& nums) {
    vector<int> res(nums.size(), nums.size());
    stack<int> indices;
    for (int i = 0; i < (int)nums.size(); ++i) {
        while (!indices.empty() &&
               nums[indices.top()] > nums[i]) {
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

vector<int> findPrevSmaller(const vector<int>& nums) {
    vector<int> res(nums.size(), -1);
    stack<int> indices;
    for (int i = (int)nums.size() - 1; i >= 0 ; --i) {
        while (!indices.empty() &&
               nums[indices.top()] >= nums[i]) { // Note <= is to tackle the nearest because there are dublicates
            res[indices.top()] = i;
            indices.pop();
        }
        indices.push(i);
    }
    return res;
}

int main(int, char**) {
    ios_base::sync_with_stdio(0); cin.tie(NULL);
    
    int n;
    cin >> n;
    vector<int> ar(n, 0);
    for (int k = 1; k <= n; ++k) {
        cin >> ar[k-1];
    }
    
    vector<int> inextSmaller = findNextSmaller(ar);
    vector<int> iprevSmaller =  findPrevSmaller(ar);
    vector<int> inextGreater = findNextGreater(ar);
    vector<int> iprevGreater =  findPrevGreater(ar);

    lint res = 0;
    for (int i = 0; i < n; ++i) {
        res += ar[i] * ((inextGreater[i] - i) *1LL* (i - iprevGreater[i]) - 
            (inextSmaller[i] - i) *1LL* (i - iprevSmaller[i]));
    }
    
    cout << res << endl;
    
    return 0;
}

Problem 4: trapping rain water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. See lc

This problem requires some modifications of the stack-based algorithm used above.

Solution

class Solution {
public:
    int trap(vector<int>& height) {
        // like nextGreateEq but a bit modified
        if (height.size() == 0) return 0;
        int n = height.size();
        int res = 0 ;
        stack<int> st;
        for (int i = 0; i < n; ++i) {
            while (!st.empty() && height[i] > height[st.top()]) {
                int top = st.top();
                st.pop(); // Important: remove top from stack
                int prevTop = st.top(); // it is previous top which is greater to top
                if (st.empty()) break;
                // we measure water between cur and prev top.
                // by subtracting h[top] we take into account that there are some
                // bricks between them
                int water = (min(height[i],height[prevTop]) - height[top]) * (i - prevTop) - 1);
                res += water;
            }
            st.push(i);
        }
        
        return res;
    }
};