Leetcode.com problem 1996: "The Number of Weak Characters in the Game"

Leetcode.com problem 1996: The Number of Weak Characters in the Game"

James S. Plank

Fri Sep 9 13:45:52 EDT 2022

Problem Statement.
Success Rate (as of September, 2022): 42.2%
This is a "medium" problem.
tests.sh: A testing script
answers.txt: Correct output to the testing script
A skeleton with my main() that you can use to test your answer.

In case Leetcode's servers are down

You are to write a method in the class Solution with the following prototype:

int numberOfWeakCharacters(vector<vector<int> >& properties);

You are playing a game with n characters. Each character has an attack value and a defense value. Properties is a vector with n elements, and each element of properties is a two-element vector containing an attack value (index 0) and a defense value (index 1) for character i.

A character is defined as "weak" if there is another character in properties with greater attack and defense values.

Return the number of weak players in properties

0 < n ≤ 100,000, and attack/defense values are numbers between 1 and 100,000.

Hints

Let's look at the following input (line 6 from tests.sh):

UNIX> echo 3 5   5 1   5 3   5 6   7 4 | ./a.out
3
UNIX>

Let's plot each of the characters, and put rectangles with them and the x and y axes:

It's pretty clear that the weak characters are those that are in the interior of another rectangle. Plus, if you look at the non-weak characters, you'll note that if one character i's x value is greater than character j's, then character j's y value has to be greater than character i's.

This gives us a pretty simple strategy for solving the problem. Sort the characters by their x values from high to low. When two character have the same x, sort them by their y values from low to high. Now you can process them, and for each character, all you need to keep track of is the highest y value for a character with a higher x value.

Let's do the example:

x y    highest y to your right      strong/weak
7 4    -                            strong
5 1    4                            weak
5 3    4                            weak
5 6    4                            strong
3 5    6                            weak

Running time is O(n log n) to do the sorting, and O(n) for the processing.

You can either sort by writing your own comparison function for sort(), or use:

map < int, multiset <int> > m;