1996. The Number of Weak Characters in the Game¶
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.
Example 1:
Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.
Example 2:
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:
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.
Constraints:
2 <= properties.length <= 10^5properties[i].length == 21 <= attacki, defensei <= 10^5
Analysis¶
Notice the data range is 10^5, in this case we should think about an algorithm that is with complexity of O(n \times \log(n)).
If we sort the array by attack in decreasing order, we can focus on the defence of any adjactant twos, because we can be sure that for any i < j, p[i][0] > p[j][0] and if p[i][0] == p[j][0] then p[i][1] < p[j][1]
However, there is a case when: i < j < k and p[i][1] > p[j][1] > or = p[k][1], and this will contribute another pair due to p[i][1] > p[k][1]. This will only happen when we see a new largest p[i][1], and it will only contribute one more pair. So we need to keep track of the largest defence in each round.
- Time: O(n \times \log(n) + n) due to sorting
- Space: O(1) quick sort without using the aux array will help to achieve it
Code¶
class Solution:
def numberOfWeakCharacters(self, p: List[List[int]]) -> int:
## any i < j, p[i][0] > p[j][0] and if p[i][0] == p[j][0] then p[i][1] < p[j][1]
p.sort(key=lambda x: (-x[0],x[1]))
ans = 0
curr_max = 0
for _, d in p:
if d < curr_max:
ans += 1
else:
curr_max = d
return ans
# a < b < c < d
# a < b, b < c, a < c, c < d, b < d, a < d (1+4)*4/2