Watch 10 video solutions for The Number of Weak Characters in the Game, a medium level problem involving Array, Stack, Greedy. This walkthrough by Tech Adora by Nivedita has 4,766 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 105Problem 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 | 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. |