sandeepgogarla61's blog

can someone help me out with this leetcode 1944 problem
By sandeepgogarla61, history, 2 years ago, In English

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

  • Vote: I like it
  • -11
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Looks solvable with an increasing stack

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ok

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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:

      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.

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply