The Number of Weak Characters in the Game

Problem

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

Examples

Example 1:

1
2
3
4
5


Input:
properties = [[5,5],[6,3],[3,6]]
Output:
 0
Explanation: No character has strictly greater attack and defense than the other.

Example 2:

1
2
3
4
5


Input:
properties = [[2,2],[3,3]]
Output:
 1
Explanation: The first character is weak because the second character has a strictly greater attack and defense.

Example 3:

1
2
3
4
5


Input:
properties = [[1,5],[10,4],[4,3]]
Output:
 1
Explanation: The third character is weak because the second character has a strictly greater attack and defense.

Solution

Method 1 - Sorting Attack in Ascending and Defense in Descending Order

Given properties[i] = [attacki, defensei], a common approach is to

first sort by attack in ascending order and, for equal attacks, by defense in descending order. This way, the array looks like [1,5], [1,3], [2,7], [3,9], [4,20], [5,15], [5,14], .... So the next step is how to compare the properties[i][1].
we can iterate from the end, keeping track of the maximum defense seen so far, and count characters whose defense is less than this maximum.
the trick we can lean from this problem is sort properties[i][1] in an opposite way from properties[i][0]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        sort(properties.begin(), properties.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
        });
        int n = properties.size();
        int maxDef = properties[n - 1][1], cnt = 0;
        for (int i = n - 2; i >= 0; --i) {
            if (properties[i][1] < maxDef) cnt++;
            maxDef = max(maxDef, properties[i][1]);
        }
        return cnt;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int max = properties[properties.length - 1][1];
        int count = 0;
        for (int i = properties.length - 2; i >= 0; i--) {
            if (properties[i][1] < max) count++;
            max = Math.max(max, properties[i][1]);
        }
        return count;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: (x[0], -x[1]))
        max_def = properties[-1][1]
        cnt = 0
        for i in range(len(properties) - 2, -1, -1):
            if properties[i][1] < max_def:
                cnt += 1
            max_def = max(max_def, properties[i][1])
        return cnt

Complexity

⏰ Time complexity: O(n log n)
🧺 Space complexity: O(1)

Problem#

Examples#

Solution#

Method 1 - Sorting Attack in Ascending and Defense in Descending Order#

Code#

Complexity#