The Number of Weak Characters in the Game - LeetCode
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 <= 105
properties[i].length == 2
1 <= attacki, defensei <= 105
- code
class Solution:
def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
properties.sort(key=lambda x: (-x[0], x[1]))
ct = 0
cur_max_defe = 0
for _, defense in properties:
if defense < cur_max_defe:
ct += 1
else:
cur_max_defe = defense
return ct
- code
class Solution:
def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
properties.sort(key=lambda x: (x[0], -x[1]))
stack = []
ans = 0
for a, d in properties:
while stack and stack[-1] < d:
stack.pop()
ans += 1
stack.append(d)
return ans
- code
class Solution:
def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
ans, dmax = 0, 0
"""
Simple problem, but was confused a bit. Was right about sorting though.
So, sort the players based on their attack in reverse order.
And group them based on their attack.
Move left and keep track of the max defense seen so far.
For a given attack group, all the groups on the left have a higher attack.
And a stronger player can come in only from the left.
So track the max defense seen on the left and for each player in the current group,
check if his defense is lower than the max defense seen on the left so far.
For a player to be weak, we just need any one strong player on the left - doesn't
matter which attack group that strong player belongs to.
"""
for _,G in groupby(sorted(properties, reverse=True), key=lambda p: p[0]):
D = list(zip(*G))[1]
ans += sum(d < dmax for d in D)
dmax = max(dmax, max(D))
return ans