Queue (Medium)

Computer Science Level pending

A group of \(n\) people with heights \(1,2,3, \dots, n\) is standing in a queue, with arbitrary order. They can see everyone in front (left) of them, until there is someone taller than them. For clarity, look at queue of \(6\) people :

The circle represent their height and the number below them indicates the number of people they can see.

Starting from the first person, you ask them the question "How many people can you see standing in front of you?" and note down their response. When you are going to trace back their heights, you noticed that some information are wrong! That is, it's not possible for the person to see that number of people despite the sequence of heights in the queue. Given the \(30\) responses, find the first (leftmost) information that is wrong.

0 1 2 0 0 0 0 0 8 0 10 0 1 2 0 0 0 2 0 6 0 1 0 0 10 0 1 16 0 0

If you think that the \(3\)-rd person from the left is the one who gave wrong information, output your answer as \(3\). If all information are correct (possible to generate a sequence of heights), output your answer as \(0\).

You are encouraged to solve the Easy version of this problem first.


Problem Loading...

Note Loading...

Set Loading...