2282. Number of People That Can Be Seen in a Grid

You are given an m x n 0-indexed 2D array of positive integers heights where heights[i][j] is the height of the person standing at position (i, j).

A person standing at position (row1, col1) can see a person standing at position (row2, col2) if:

• The person at (row2, col2) is to the right or below the person at (row1, col1). More formally, this means that either row1 == row2 and col1 < col2 or row1 < row2 and col1 == col2.
• Everyone in between them is shorter than both of them.

Return an m x n 2D array of integers answer where answer[i][j] is the number of people that the person at position (i, j) can see.

• monotonic stack + binary search solution
• Time : O(nm(logn + logm))
• Space : O(max(n,m))

c++

class Solution {
public:
    vector<vector<int>> seePeople(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        vector<vector<int>> res(n, vector<int>(m));
        vector<int> st;
        for(int i = 0; i < n; i++) {
            st.clear();
            for(int j = m - 1; j >= 0; j--) {
                if(!st.empty()) {
                    if(st[0] <= A[i][j]) res[i][j] += st.size();
                    else res[i][j] += lower_bound(rbegin(st), rend(st), A[i][j]) - rbegin(st) + 1;
                }
                
                while(!st.empty() and st.back() <= A[i][j]) st.pop_back();
                st.push_back(A[i][j]);
            }
        }

        for(int j = 0; j < m; j++) {
            st.clear();
            for(int i = n - 1; i >= 0; i--) {
                if(!st.empty()) {
                    if(st[0] <= A[i][j]) res[i][j] += st.size();
                    else res[i][j] += lower_bound(rbegin(st), rend(st), A[i][j]) - rbegin(st) + 1;
                }
                
                while(!st.empty() and st.back() <= A[i][j]) st.pop_back();
                st.push_back(A[i][j]);
            }
        }

        return res;
    }
};

• monotonic stack solution
• Time : O(nm)
• Space : O(max(n,m))

c++

class Solution {
public:
    vector<vector<int>> seePeople(vector<vector<int>>& A) {
        int n = A.size(), m = A[0].size();
        vector<vector<int>> res(n, vector<int>(m));
        vector<int> st;
        for(int i = 0; i < n; i++) {
            st.clear();
            for(int j = m - 1; j >= 0; j--) {
                int seen = 0;
                while(!st.empty() and st.back() < A[i][j]) {
                    seen++;
                    st.pop_back();
                }
                
                res[i][j] += seen + (!st.empty());
                
                if(st.empty() or st.back() != A[i][j])
                    st.push_back(A[i][j]);
            }
        }

        for(int j = 0; j < m; j++) {
            st.clear();
            for(int i = n - 1; i >= 0; i--) {
                int seen = 0;
                while(!st.empty() and st.back() < A[i][j]) {
                    seen++;
                    st.pop_back();
                }

                res[i][j] += seen + (!st.empty());
                
                if(st.empty() or st.back() != A[i][j])
                    st.push_back(A[i][j]);
            }
        }

        return res;
    }
};