1996 - The Number of Weak Characters in the Game (Medium)
Problem Statement
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 <= 105properties[i].length == 21 <= attacki, defensei <= 105
Approach 1: Hash Map
class Solution {
public:
// the idea is to
// 1. rearrange the order of attack and defense
// 2. count weak characters (those defenses less than the current maximum defense)
// 3. update the maximum defense
int numberOfWeakCharacters(vector<vector<int>>& p) {
// the final answer to be returned
int weakCharacters = 0;
// record maximum defense. since 1 <= defense_i <= 10 ^ 5
// we can set the init value to x where x < 1
int maxDefense = 0;
// use a hash map to map the attack and defense with greater<int> as a key_compare
map<int, vector<int>, greater<int>> m;
for(auto x : p) m[x[0]].push_back(x[1]);
// for each attack
for(auto x : m) {
// we count the number of weak characters
// and add it to `weakCharacters`
weakCharacters += count_if(x.second.begin(), x.second.end(), [&](int curDefense){ return curDefense < maxDefense;});
// then update `maxDefense` which is the maximum value in current defenses
maxDefense = max(maxDefense, *max_element(x.second.begin(), x.second.end()));
}
return weakCharacters;
}
};
Approach 2: Sort with custom comparator
class Solution {
public:
// the idea is to
// 1. rearrange the order of attack and defense
// 2. count weak characters (those defenses less than the current maximum defense)
// 3. update the maximum defense
int numberOfWeakCharacters(vector<vector<int>>& p) {
// the final answer to be returned
int weakCharacters = 0;
// record maximum defense. since 1 <= defense_i <= 10 ^ 5
// we can set the init value to x where x < 1
int maxDefense = 0;
// sort properties with custom sort comparator
sort(p.begin(), p.end(), [](const vector<int>& x, const vector<int>& y) {
// if the attack is same, then sort defense in ascending order
// otherwise, sort attack in in descending order
return x[0] == y[0] ? x[1] < y[1] : x[0] > y[0];
});
// by doing so, we don't need to compare starting from the back
for (auto& x : p) {
// x[1] is defense of properties[i]
// if it is less than current maxDefense, then it means it is a weak character
weakCharacters += x[1] < maxDefense;
// update maxDefense
maxDefense = max(maxDefense, x[1]);
}
return weakCharacters;
}
};
class Solution:
# the idea is to
# 1. rearrange the order of attack and defense
# 2. count weak characters (those defenses less than the current maximum defense)
# 3. update the maximum defense
def numberOfWeakCharacters(self, p: List[List[int]]) -> int:
# the final answer to be returned
weakCharacters = 0
# record maximum defense. since 1 <= defense_i <= 10 ^ 5
# we can set the init value to x where x < 1
maxDefense = 0
# sort properties with custom sort comparator
# if the attack is same, then sort defense in descending order
# otherwise, sort attack in in ascending order
p.sort(key = lambda x: (x[0], -x[1]), reverse = True)
# or we can do it like
# p.sort(key = lambda x: (-x[0], x[1]))
for _, defense in p:
# if it is less than current maxDefense, then it means it is a weak character
if defense < maxDefense: weakCharacters += 1
# update maxDefense
else: maxDefense = defense
return weakCharacters
// the idea is to
// 1. rearrange the order of attack and defense
// 2. count weak characters (those defenses less than the current maximum defense)
// 3. update the maximum defense
func numberOfWeakCharacters(properties [][]int) int {
// Weak starts at 0, this is the variable which is going to be returned
weekCharacterCount := 0
maxDefence := 0
// Sorting the order of the desending order of the attack
sort.Sort(ByAttack(properties))
for _, elem := range properties {
// Appending the count if the current element is less than the max defense
// Else change the max defence
if(elem[1] < maxDefence){
weekCharacterCount++;
}else {
maxDefence = elem[1]
}
}
return weekCharacterCount
}
// Custom sorting Logic by attack
type ByAttack [][]int
func (a ByAttack) Len() int { return len(a) }
func (a ByAttack) Less(i, j int) bool {
if(a[i][0] == a[j][0]){
return a[i][1] < a[j][1]
}
return a[i][0] > a[j][0]
}
func (a ByAttack) Swap(i, j int) { a[i], a[j] = a[j], a[i] }