Here is an easy one to balance the last, given an array representing the height of people standing behind each other from left to right, find how many people have an unobstructed view in front of them.
We can do this in O(N) time and constant space by walking the array from right to left tracking each time the tallest person we have found. If the current person is NOT taller than the current tallest, he won't be able to see.
You can check my implementation of witnessOfTheTallPeople on my Gist along with some tests in WitnessOfTheTallPeopleJtests.
No comments:
Post a Comment
With great power comes great responsibility