The Number of Weak Characters in the Game — Solution
The Number of Weak Characters in the Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
The Number of Weak Characters in the Game is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Stack, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are playing a game with characters, where properties[i] = [attack, defense].
A character is weak if some other character has strictly greater attack and strictly greater defense. Return the number of weak characters.
Example 1
Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Example 2
Input: properties = [[2,2],[3,3]]
Output: 1
Example 3
Input: properties = [[1,5],[10,4],[4,3]]
Output: 1
Constraints
2 <= properties.length <= 401 <= attack, defense <= 100000
Hints for The Number of Weak Characters in the Game
Hint 1
Sort by attack descending, breaking ties by defense ascending.
Hint 2
That tie-break guarantees equal-attack characters never count each other as weak.
Hint 3
Then sweep once, tracking the largest defense seen so far; anything below it is weak.
How to solve The Number of Weak Characters in the Game
Sort by attack descending with ties by defense ascending, then sweep tracking the maximum defense seen; a character with lower defense than that is weak.
Approach
- Sort by
(-attack, defense). - For each character, if
defense < maxDefense, count it weak; else updatemaxDefense.
Why it works
Every earlier character has strictly greater attack, except ties, which the ascending-defense tie-break places so that an equal-attack character never has a larger defense before it. A larger defense seen earlier therefore comes from a strictly stronger character.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Ties by defense descending would wrongly mark equal-attack characters weak.
Reference solution
Python
def numberOfWeakCharacters(properties) -> int:
ordered = sorted(properties, key=lambda p: (-p[0], p[1]))
max_defense = 0
weak = 0
for _, defense in ordered:
if defense < max_defense:
weak += 1
else:
max_defense = defense
return weakJava
public static int numberOfWeakCharacters(int[][] properties) {
int[][] s = properties.clone();
Arrays.sort(s, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
int maxDefense = 0, weak = 0;
for (int[] p : s) {
if (p[1] < maxDefense) weak++;
else maxDefense = p[1];
}
return weak;
}C++
int numberOfWeakCharacters(vector<vector<int>>& properties) {
vector<vector<int>> s = properties;
sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
if (a[0] != b[0]) return a[0] > b[0];
return a[1] < b[1];
});
int maxDefense = 0, weak = 0;
for (const auto& p : s) {
if (p[1] < maxDefense) weak++;
else maxDefense = p[1];
}
return weak;
}JavaScript
var numberOfWeakCharacters = function(properties) {
const sorted = properties.slice().sort(function(a, b) {
return a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1];
});
let maxDefense = 0, weak = 0;
for (let i = 0; i < sorted.length; i++) {
if (sorted[i][1] < maxDefense) weak++;
else maxDefense = sorted[i][1];
}
return weak;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms