Witness of The Tall People

, , ,

Question

There are n people lined up, and each have a height represented as an integer. A murder has happened right in front of them, and only people who are taller than everyone in front of them are able to see what has happened. How many witnesses are there?

Example

1
2
3
4
5
6
7
8
9
10
11
12
Input: [3, 6, 3, 4, 1]  
Output: 3

 #
 #
 # #
####
####
#####
36341                                 x (murder scene)

Only [6, 4, 1] were able to see in front of them.

Solution

We need to traversal backwards and maintain the max during the process.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// time: O(n) space: O(1)
public static int countWitness(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int res = 0;
        int max = 0;
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            if (arr[i] > max) {
                max = arr[i];
                res++;
            }
        }
        return res;
    }