problem link : https://leetcode.com/problems/number-of-visible-people-in-a-queue/ approach for the above mentioned question when duplicates are allowed

eg test case : 11 6 7 5 11 11 o/p : 3 2 2 1 1 0

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | awoo | 164 |

3 | adamant | 162 |

4 | TheScrasse | 159 |

5 | nor | 154 |

6 | maroonrk | 153 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

10 | pajenegod | 144 |

problem link : https://leetcode.com/problems/number-of-visible-people-in-a-queue/ approach for the above mentioned question when duplicates are allowed

eg test case : 11 6 7 5 11 11 o/p : 3 2 2 1 1 0

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2024 10:02:45 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Looks solvable with an increasing stack

ok

I looked at the question again and it's supposed to be a decreasing stack not an increasing stack. My solution for original qn (in Python)

Code:class Solution:

____def canSeePersonsCount(self, heights: List[int]) -> List[int]:

________a = heights

________n = len(a)

________stack = [] # decreasing stack

________ans = [-1] * n

________for i in range(n — 1, -1, -1):

____________cnt = 0

____________while len(stack) > 0 and a[stack[-1]] < a[i]:

________________cnt += 1

________________stack.pop()

____________if len(stack) > 0:

________________ans[i] = cnt + 1

____________else:

________________ans[i] = cnt

____________stack.append(i)

________return ans

If you want to work with duplicated elements, at a[i] you need to add an additional factor k — 1 if the last element in stack after popping is also a[i]. k is the number of elements in the stack equivalent to a[i], which you can binary search since the stack is decreasing.

Sorry my described method for duplicate cases won't work. You need to handle cases like 5 3 3 4 4 3 3 4 4 5. Maybe a decreasing stack storing [value, counts] might work. You'll need to figure out how to merge the counts for repeated elements and to add the counts when popping off the stack.

Hey Sandeep,

What is your solution for the case when all heights are different? I think [this solution] for example, (https://leetcode.com/problems/number-of-visible-people-in-a-queue/discuss/1961776/Number-of-Visible-People-in-a-Queue) should work in both cases.

It is Not working , when duplicates heights are given :|

I think it should work. The person 'i' cannot see anything beyond person 'j' if heights[i] <= heights[j]. The expected result for your example is '3 1 2 1 1 0'. I think you have a typo for the second number, right?

Notice, that LeetCode rejects inputs with repeated elements, but this does not mean the solution does not work.