Matrix Problem : Find the number of persons seen

Given a grid G of numbers representing heights of persons standing next to each other.

  • A person can see another person in the grid if the height of everyone in between is shorter than them
  • A person can see to the right and down
    Return a grid A where A[x][y] is the sum of all the persons seen from G[x][y]

Example
[9, 6, 8, 5, 11]
[1, 5, 3, 7, 9]
[2, 1, 4, 6, 1]

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

For example:
In last row:

For :[2, 1, 4, 6, 1]
for 2: [1, 4, 6] = 3
for 1: [4, 6] = 2
for 4: [6] = 1
for 6: [1] = 1
for 1: [] = 0

Idea: Going to use monotonic stack to solve this problem

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
svalak

svalak

Passionate about problem solving; #WritesOnQuora #VoraciousReader #MBTIEnthusiast #LovePsychology https://www.quora.com/profile/Shaila-Hegde-2