How hard is LeetCode 2282. Number of People That Can Be Seen in a Grid?

LeetCode 2282. Number of People That Can Be Seen in a Grid is rated Medium on LeetCode.

What is the time complexity of LeetCode 2282. Number of People That Can Be Seen in a Grid?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 2282. Number of People That Can Be Seen in a Grid?

The Python solution on this page uses O(\max(m, n)) auxiliary space.

What topics does LeetCode 2282. Number of People That Can Be Seen in a Grid cover?

LeetCode 2282. Number of People That Can Be Seen in a Grid is tagged Stack, Array, Matrix and Monotonic Stack on LeetCode.

Is LeetCode 2282. Number of People That Can Be Seen in a Grid a premium problem?

Yes. LeetCode 2282. Number of People That Can Be Seen in a Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of People That Can Be Seen in a Grid — LeetCode 2282 Python Solution

MediumLeetCode PremiumStackArrayMatrixMonotonic Stack

Problem: #2282
Pattern: Stack
Reading time: 5 min
Source: leetcode.com

The problem

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).

Example

Input: heights = [[3,1,4,2,5]]
Output: [[2,1,2,1,0]]
Explanation: - The person at (0, 0) can see the people at (0, 1) and (0, 2).

Python solution

Python

class Solution:
    def seePeople(self, heights: List[List[int]]) -> List[List[int]]:
        def f(nums: List[int]) -> List[int]:
            n = len(nums)
            stk = []
            ans = [0] * n
            for i in range(n - 1, -1, -1):
                while stk and stk[-1] < nums[i]:
                    ans[i] += 1
                    stk.pop()
                if stk:
                    ans[i] += 1
                while stk and stk[-1] == nums[i]:
                    stk.pop()
                stk.append(nums[i])
            return ans

        ans = [f(row) for row in heights]
        m, n = len(heights), len(heights[0])
        for j in range(n):
            add = f([heights[i][j] for i in range(m)])
            for i in range(m):
                ans[i][j] += add[i]
        return ans

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(\max(m, n)) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2282. Number of People That Can Be Seen in a Grid is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2282. Number of People That Can Be Seen in a Grid?: LeetCode 2282. Number of People That Can Be Seen in a Grid is rated Medium on LeetCode.
What is the time complexity of LeetCode 2282. Number of People That Can Be Seen in a Grid?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 2282. Number of People That Can Be Seen in a Grid?: The Python solution on this page uses O(\max(m, n)) auxiliary space.
What topics does LeetCode 2282. Number of People That Can Be Seen in a Grid cover?: LeetCode 2282. Number of People That Can Be Seen in a Grid is tagged Stack, Array, Matrix and Monotonic Stack on LeetCode.
Is LeetCode 2282. Number of People That Can Be Seen in a Grid a premium problem?: Yes. LeetCode 2282. Number of People That Can Be Seen in a Grid is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.