Given a list of players, for each player, find a younger player to the left of him with the highest strength

Question

Suppose we have a list of players like below

Player format = {id, age, strength}

Input format = { player1, player2, ....}

Input : { {0, 14, 75}, {1, 17, 65}, {2, 17, 50}, {3, 13, 40}, {4, 16, 90}, {5, 17, 84}, {6, 16, 67} }

Given input as above, for each player find a younger player to left of him with highest strength and add this strength to the result else -1, For simplicity we can assume player ids same as index of the array

For the above input, output is

Output : { -1 , 75 , 75 , -1 , 75 , 90 , 75}

My approach is O(N^2):

int[] findStrengths() {
    int[][] players = new int[n][3];
    int[] res = new int[n];
    Arrays.fill(res, -1);
    for(int i=0;i<n;i++) {
        for(int j=0;j<i;j++) {
            if(players[j][1] < players[i][1]) {
                res[i] = Math.max(res[i], players[j][2]);
            }
        }
    }
    return res;
}

Is it possible to solve this problem in O(Nlog(N)) using some BST structure, or in O(N) using a monotonic stack / queue ?

Answer 1

Here is a simpler approach than the other one.

Create an ordered data structure mapping age to strength. For example an AVL tree. We will only keep the people who are stronger than anyone the same age or younger. It starts off empty. We can call it best_strength.

Let's assume it has methods to add, delete, find_at_most find (if any) the last entry that is at most a given age, and find_next one to find the first entry above that age.

The logic then goes like this.

create best_strength
create output
for player in players:
    (prev_age, prev_strength) = best_strength.find_at_most(player.age)
    if prev_strength is None or prev_strength < player.strength:
        output.append(-1)
        best_strength.add(age, player.strength)
        while True: # break loop inside
            (next_age, next_strength) = best_strength.find_next(player.age)
            if next_strength is None or player.strength < next_strength:
                best_strength.remove(next_age)
            else:
                break # exit loop here
    else:
        output.append(prev_strength)

This is O(n log(n)) and you can use an existing ordered data structure.