The Number of Weak Characters in the Game solution and explanation
Google
9 more videos on this problem
1996. The Number of Weak Characters in the GameTech Adora by Nivedita · 10:55 · 4K views
LeetCode 1996. The Number of Weak Characters in the GameHappy Coding · 11:35 · 4K views
NUMBER OF WEAK CHARACTERS IN THE GAME | LEETCODE # 1996 | PYTHON BUCKET SORT SOLUTIONCracking FAANG · 18:08 · 3K views
The Number of Weak Characters in the Game | Sorting | LeetCode 1996Prashanth Vaidya · 13:02 · 2K views
Leetcode 1996 The Number of Weak Characters in the Game | Greedy Arrays | Coding Decoded SDE SheetCoding Decoded · 12:06 · 2K views
1996. The Number of Weak Characters in the Game (Leetcode Medium)Programming Live with Larry · 13:40 · 1K views
Leetcode 1996 The Number of Weak Characters in the Game - Tricky Java Solution ExplainedAlgorithmicIQ · 17:45 · 784 views
Daily Leetcode #892: Sep 09, 2022 - 1996. The Number of Weak Characters in the GameProgramming Live with Larry · 9:48 · 740 views
Leetcode 1996. The Number of Weak Characters in the GameLearn Together · 21:01 · 437 views
Leetcode 1996. The Number of Weak Characters in the Game (Weekly Contest 257 Q2)Yinghua Hu · 7:26 · 170 views
The 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.
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 overview
Problem Overview: Each character has two attributes: attack and defense. A character is considered weak if another character exists with both strictly higher attack and defense. The task is to count how many such weak characters appear in the input array.
Approach 1: Sort and Track Maximum Defense (O(n log n) time, O(1) space)
This is the standard greedy solution using sorting. First sort characters by attack in descending order. When attacks are equal, sort by defense in ascending order. This ordering prevents characters with the same attack from incorrectly marking each other as weak. After sorting, iterate through the list while tracking the maximum defense seen so far. If the current character's defense is less than this maximum, a previously processed character already has both higher attack and higher defense, so the current one is weak. Otherwise update the maximum defense. The key insight: sorting ensures that every previously visited character already has greater or equal attack, so only the defense comparison remains. This combines greedy reasoning with ordering to reduce the problem to a single pass.
Approach 2: Balanced Binary Search Tree (O(n log n) time, O(n) space)
Another method maintains a structure that allows fast queries for stronger defenses among higher attacks. First group characters by attack value and process attacks in descending order. While iterating groups, store defenses of previously processed higher-attack characters inside a balanced BST (such as TreeMap in Java). For each character, query whether a stored defense greater than the current defense exists. If it does, the character is weak. After finishing a group, insert its defenses into the tree so equal-attack characters do not affect each other. Each lookup and insertion costs O(log n). This approach demonstrates how ordered structures help with dominance queries and is closely related to patterns used in monotonic stack or skyline-style problems.
Recommended for interviews: The sorting + maximum defense scan is what interviewers usually expect. It reduces a 2D comparison problem into a sorted linear pass and keeps the implementation simple. Mentioning the BST approach shows understanding of dominance queries, but the greedy sorted traversal is the cleanest and most common solution.
Approach 1: Sort and Track Maximum Defense
Sort characters by attack in descending order, and by defense in ascending order if attacks are equal. This sorting allows us to easily track the maximum defense for higher attacks. Iterate through the list, and use a variable to keep track of the maximum defense encountered. If a character's defense is less than this maximum, it's considered weak.
def numberOfWeakCharacters(properties):
properties.sort(key=lambda x: (-x[0], x[1]))
max_defense = 0
weak_count = 0
for _, defense in properties:
if defense < max_defense:
weak_count += 1
else:
max_defense = defense
return weak_count#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *p1 = *(int**)a;
int *p2 = *(int**)b;
if (p1[0] != p2[0]) return p2[0] - p1[0];
return p1[1] - p2[1];
}
int numberOfWeakCharacters(int** properties, int propertiesSize, int* propertiesColSize) {
qsort(properties, propertiesSize, sizeof(int*), compare);
int maxDefense = 0, weakCount = 0;
for (int i = 0; i < propertiesSize; i++) {
if (properties[i][1] < maxDefense) {
weakCount++;
} else {
maxDefense = properties[i][1];
}
}
return weakCount;
}The code first sorts the properties array using a lambda function. It sorts the attacks in descending order and defenses in ascending order. Then, it initializes two variables: max_defense to track the maximum defense seen so far, and weak_count to count the weak characters. It iterates over the characters, updating max_defense and counting weak characters.
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as we're sorting in place.
Approach 2: Use a Balanced Binary Search Tree
Another approach is to use a balanced binary search tree to dynamically keep track of the best defenses for each attack level. As you process each character, you can efficiently query and update this data structure to determine if a character is weak.
import java.util.*;
public class Solution {
public int numberOfWeakCharacters(int[][] properties) {
Arrays.sort(properties, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
int maxDefense = 0, weakCount = 0;
for (int[] prop : properties) {
if (prop[1] < maxDefense) {
weakCount++;
} else {
maxDefense = prop[1];
}
}
return weakCount;
}
}function numberOfWeakCharacters(properties) {
properties.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
let maxDefense = 0;
let weakCount = 0;
for (let [_, defense] of properties) {
if (defense < maxDefense) {
weakCount++;
} else {
maxDefense = defense;
}
}
return weakCount;
}The Java solution follows a similar logic where sorting is employed, and then iteration through sorted properties to determine weakness. The sorting is done using a lambda in Java, benefiting from the ordered traversal to compare defenses.
Time complexity: O(n log n) because of sorting.
Space complexity: O(1), with the in-place sort.
Approach 3: Sorting + Traversal
We can sort all characters in descending order of attack power and ascending order of defense power.
Then, traverse all characters. For the current character, if its defense power is less than the previous maximum defense power, it is a weak character, and we increment the answer by one. Otherwise, update the maximum defense power.
After the traversal, we get the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of characters.
class Solution {
public:
int numberOfWeakCharacters(vector<vector<int>>& properties) {
sort(properties.begin(), properties.end(), [&](auto& a, auto& b) { return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0]; });
int ans = 0, mx = 0;
for (auto& x : properties) {
ans += x[1] < mx;
mx = max(mx, x[1]);
}
return ans;
}
};function numberOfWeakCharacters(properties: number[][]): number {
properties.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));
let ans = 0;
let mx = 0;
for (const [, x] of properties) {
if (x < mx) {
ans++;
} else {
mx = x;
}
}
return ans;
}func numberOfWeakCharacters(properties [][]int) (ans int) {
sort.Slice(properties, func(i, j int) bool {
a, b := properties[i], properties[j]
if a[0] == b[0] {
return a[1] < b[1]
}
return a[0] > b[0]
})
mx := 0
for _, x := range properties {
if x[1] < mx {
ans++
} else {
mx = x[1]
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Track Maximum Defense | Time complexity: O(n log n) due to sorting. |
| Use a Balanced Binary Search Tree | Time complexity: O(n log n) because of sorting. |
| Sorting + Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Track Maximum Defense | O(n log n) | O(1) | Best general solution. Simple greedy pass after sorting. |
| Balanced Binary Search Tree | O(n log n) | O(n) | Useful when maintaining dynamic dominance queries across groups. |
Frequently asked questions
Is The Number of Weak Characters in the Game easy or hard?
The problem is rated Medium because it requires recognizing how sorting order prevents false comparisons between characters with equal attack. Once the ordering trick is understood, the implementation becomes a straightforward greedy scan.
The Number of Weak Characters in the Game Python/Java solution
In Python, the typical implementation sorts the list of pairs and iterates while tracking the maximum defense. In Java, the same strategy works with Arrays.sort and a linear pass. Another Java approach uses TreeMap as a balanced BST to track higher defenses.
How to solve The Number of Weak Characters in the Game in O(n)?
A pure O(n) solution is generally not practical because the problem requires ordering characters by attack to compare dominance relationships. Sorting creates the correct processing order, which leads to the common O(n log n) greedy solution. After sorting, the detection step itself is O(n).
What is the best approach for The Number of Weak Characters in the Game?
The most common solution sorts characters by attack descending and defense ascending, then scans while tracking the maximum defense seen so far. If a character's defense is lower than the current maximum, it is weak. This greedy strategy runs in O(n log n) time due to sorting and O(1) extra space.
Is The Number of Weak Characters in the Game asked at Google/Amazon/Meta?
Variants of dominance and skyline-style comparison problems frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests sorting strategies, greedy thinking, and handling multi-dimensional comparisons efficiently.
What data structure is used in The Number of Weak Characters in the Game?
The most efficient approach primarily relies on array sorting and a running maximum variable. Alternative implementations may use ordered maps or balanced binary search trees such as TreeMap to track defenses and perform dominance queries in O(log n) time.
What is the time complexity of The Number of Weak Characters in the Game?
The optimal solution runs in O(n log n) time because the characters must be sorted by attack. After sorting, the algorithm performs a single linear scan to compare defenses. The extra space usage can be O(1) if sorting is done in place.