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

Problem Description

In this problem, we have a 2D array called heights that represents the heights of individuals standing in a grid. The grid has m rows and n columns, and heights[i][j] is the height of the person at position (i, j).

A person at position (row1, col1) can see another person at position (row2, col2) if two conditions are met:

1. The person at (row2, col2) is either to the right or to the below of the person at (row1, col1). Specifically, this means either row1 is the same as row2 and col1 < col2, or row1 < row2 and col1 is the same as col2.
2. Everyone standing in the direct line of sight (in between these two positions horizontally or vertically) is shorter than both the observing person and the observed person.

The goal is to return a new m x n 2D array named answer, where answer[i][j] contains the number of people that the person at position (i, j) can see based on the above rules.

Intuition

The solution to this problem can be approached using stacks to efficiently keep track of the people in line of sight. We iterate through each row and each column to count how many people a person at (i, j) can see to their right and below respectively.

For each row, we start from the rightmost position and move left. We maintain a stack that keeps track of the heights of the people who are in direct line of sight and not blocked by anyone taller so far. If a new person is taller than the person at the top of the stack, then we keep popping people off the stack until we find someone taller or the stack is empty. The number of people popped is the number of people this new person can see to their right. If there is still someone on the stack, it means the new person can also see them, so we add 1 more. If there are people with the same height, we remove them since they will be blocked by the new person.

After we process all rows using the above logic, we follow a similar approach for each column to count the number of people visible below. We start from the bottommost position of each column and move upwards. Again, we use a stack to keep track of the visible heights.

Finally, we combine the counts of visible people from both horizontal and vertical directions. Each position (i, j) in the output answer is the sum of counts from corresponding row and column individual calculations.

By breaking this down into two 1-dimensional problems (first rows, then columns), we are able to solve the whole 2-dimensional problem efficiently.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution uses the function f(nums: List[int]) -> List[int] to process a 1-dimensional list of heights and returns a list of counts representing how many people can be seen from each position when looking in one direction (to the right for rows or upwards for columns). It utilizes a stack data structure, which is a LIFO (Last In, First Out) structure to keep track of potential candidates that people can see.

For each row in the heights array, we call this function and treat the row as a standalone list:

1. We iterate from right to left (the reverse direction) because we want to check how many people each person can see to their right.
2. We use a stack (stk) to maintain the heights of the people in the current line of sight.
3. For each person, we compare their height with the height at the top of the stack. If the current person is taller:
   • We pop all the people off the stack that are shorter than the current person and increment the visible count for the current person (since they can see over these shorter people).
   • If there is someone left on the stack after this, we increment the count by one since the current person can see this next one.
   • We also pop any people off the stack who are the same height as the current person, since they will be blocked.
4. We push the current person's height onto the stack, signifying that subsequent shorter people will be able to see this person.

After processing all rows, we repeat a similar approach for each column. We extract each column from the heights array and treat it as an independent list to pass to the f function:

1. We iterate from the bottom to the top since we want to determine how many people can be seen upwards.
2. We apply the same logic with the stack to calculate the visible counts as we did for rows.

Finally, for each position (i, j), we sum up the values from the row and column processing – the resulting ans[i][j] will contain the total number of people the person at (i, j) can see to their right and below them.

The primary algorithms and patterns used here are iteration, stack data structure (for efficiently finding larger elements and keeping track), and reversing the direction of iteration (to maintain the correct order of sight based on problem constraints). With this approach, each person is processed in O(1) time on average (since each element is pushed and popped from the stack once), leading to an overall time complexity of O(m*n) where m is the number of rows and n is the number of columns.

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Imagine we have the following heights array:

1[
2  [3, 1],
3  [4, 2]
4]

Here we have 2 rows and 2 columns (m=2, n=2). Now let's walk through the algorithm:

For rows:

• For the first row [3, 1]:

  1. We start from the last person (rightmost), which has a height of 1.
  2. There's nobody to the right, so push 1 onto the stack.
  3. Move to the next left person with height 3. Since 3 is taller than 1, 3 can see over 1.
  4. Pop 1 out of the stack, increment visibility count for 3 by 1.
  5. Push 3 onto the stack.

• After processing the first row, our visible count array is [1, 0]. This means the person at (0, 0) can see 1 person to their right, the person at (0, 1) can see nobody to their right.

• For the second row [4, 2], repeat similar steps:

  1. Push 2 onto the stack.
  2. Next, 4 is taller than 2, so 4 can see over 2.
  3. Pop 2 out, increment the visibility count for 4 by 1.
  4. Push 4 onto the stack.

• After processing the second row, our visible count array is [1, 0]. Same as the first row, person at (1, 0) can see 1 person, person at (1, 1) can see nobody to their right.

For columns:

• For the first column [3, 4] (using the original heights array):

  1. Starting from the bottom, 4 doesn't see anybody above it, so push 4 onto the stack.
  2. Moving up, 3 cannot see over 4 because 4 is taller.

• Visible count for the first column is [0, 0]. Nobody can see anyone above them because the bottom person is taller.

• For the second column [1, 2]:

  1. Push 2 onto the stack.
  2. 1 is shorter than 2, so it doesn't see anyone above it.

• Visible count for the second column is also [0, 0].

Finally, we combine the counts from rows and columns:

• For (0,0), the count is 1 (row) + 0 (column) = 1
• For (0,1), the count is 0 (row) + 0 (column) = 0
• For (1,0), the count is 1 (row) + 0 (column) = 1
• For (1,1), the count is 0 (row) + 0 (column) = 0

Our final answer array showcasing how many people each person at (i, j) can see to their right and below them will be:

1[
2  [1, 0],
3  [1, 0]
4]

In this example, the person at position (0, 0) can see 1 person, and so can the person at (1, 0), while the others cannot see anyone based on the given problem constraints.

Solution Implementation

Time and Space Complexity

The given code defines a method seePeople that takes a 2D list of integers representing the heights and returns a 2D list representing how many people each person can see in their row and column. There are two main parts in the code: 1) the nested function f processes a list to find how many people can be seen by each person in a single row or column, and 2) the main function applies this logic to each row and column in the given heights matrix.

Time Complexity:

The nested function f(nums) has the time complexity of O(n) for a single row or column since it processes each element once, popping from the stack takes O(1) time per operation, but each element can only be popped once. Hence, for processing one row or column of size n, it would be O(n).

When the function f is applied to each row:

• There are m rows, and the length of each row is n.
• The function is called m times, leading to a time complexity of O(m * n) for processing all rows

For the columns:

• The same function is being applied to each of n columns, and each column has m items.
• This leads to a time complexity of O(n * m) once again for processing all columns.

Since we process both rows and columns separately, the total time complexity is O(m * n) + O(n * m) which simplifies to O(2 * m * n) and further to O(m * n) since constant factors are dropped in Big O notation.

Space Complexity:

The auxiliary space is used for the stack within function f and the list that holds answers.

• The stack stk in its worst case can grow to O(n) for a row or O(m) for a column, i.e., the size of the row or column it's processing.
• The list ans is initialized with the same size as the input list nums, so it's O(n) for a row and O(m) for a column.
• When processing rows, this is done in-place, so we only need space for the stack and one row's ans, which is O(n).

Since for the columns, a similar stack is used and the add list is generated for each column, the space complexity would also be O(m) at any instance since we process each column one at a time.

• Temporarily, for the add list generated for columns, it's O(m) as well.

So, the overall space complexity would be O(m + n). However, typically, for space complexity, we mention the higher term if m and n are not in the same range. Thus, if m is approximately equal to n, space complexity can be simplified to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.