The Number of Weak Characters in the Game
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most intuitive way to solve the problem. It directly translates the definition of a weak character into code. We check every possible pair of characters to see if one is strictly stronger than the other.
Algorithm
- Initialize a counter
weakCharactersto 0. - Iterate through each character
ifrom0ton-1, wherenis the number of characters. - For each character
i, start a nested loop to iterate through all other charactersjfrom0ton-1. - If
iandjare the same character, skip to the next iteration. - Check if character
jis strictly stronger than characteriby comparing their properties:properties[j][0] > properties[i][0]andproperties[j][1] > properties[i][1]. - If a stronger character
jis found, it means characteriis weak. We incrementweakCharactersand break the inner loop, as we only need one such character to confirm weakness. - After the loops complete, return the total
weakCharacterscount.
Walkthrough
In this method, we take each character one by one and compare it against every other character in the list. For a character i, we search for any other character j that has both an attack and a defense value strictly greater than character i's values. If we find such a character j, we classify character i as weak, add one to our count, and immediately move to the next character to check, since we only need to find one character that dominates it. This process is repeated for all characters.
class Solution { public int numberOfWeakCharacters(int[][] properties) { int n = properties.length; int weakCharacters = 0; for (int i = 0; i < n; i++) { boolean isWeak = false; for (int j = 0; j < n; j++) { if (properties[j][0] > properties[i][0] && properties[j][1] > properties[i][1]) { isWeak = true; break; } } if (isWeak) { weakCharacters++; } } return weakCharacters; }}Complexity
Time
O(N^2), where N is the number of characters. The nested loops lead to a quadratic number of comparisons.
Space
O(1) extra space. We only use a few variables to keep track of the count and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides a few variables.
Cons
Extremely inefficient for the given constraints (
nup to 10^5).The O(N^2) complexity will lead to a 'Time Limit Exceeded' (TLE) error on most platforms.
A more efficient approach involves sorting the characters. By sorting the characters in a specific way, we can avoid the nested loop and determine the number of weak characters in a single pass over the sorted data. The choice of sorting criteria is key to making this approach work.
Algorithm
- Sort the
propertiesarray using a custom comparator. - The primary sorting criterion is the attack value, in descending order.
- The secondary sorting criterion (for characters with the same attack value) is the defense value, in ascending order.
- Initialize a counter
weakCharacters = 0and a variablemaxDefense = 0. - Iterate through the sorted array from left to right.
- For each character
p = [attack, defense]:- If the character's defense
p[1]is less thanmaxDefense, it means we have already seen a character with a strictly greater attack and a greater defense. IncrementweakCharacters. - Update
maxDefenseto be the maximum of its current value and the current character's defense:maxDefense = Math.max(maxDefense, p[1]).
- If the character's defense
- Return
weakCharacters.
Walkthrough
The core idea is to process characters in an order that allows us to easily check for weakness. We sort the properties array by attack in descending order. If two characters have the same attack, we sort them by defense in ascending order.
After sorting, we iterate through the array and maintain the maximum defense value encountered so far (maxDefense). For any character, if its defense is less than maxDefense, it's a weak character. Why? The maxDefense must have come from a character processed earlier. Due to our sorting, any character processed earlier has an attack value greater than or equal to the current character's attack. The tie-breaking rule (ascending defense for equal attacks) is crucial: if an earlier character had the same attack, its defense would be smaller, so it couldn't have set a maxDefense that is greater than the current character's defense. Therefore, a maxDefense larger than the current defense must have come from a character with a strictly greater attack, satisfying the condition for a weak character.
import java.util.Arrays; class Solution { public int numberOfWeakCharacters(int[][] properties) { // Sort by attack descending, and if attack is same, by defense ascending. Arrays.sort(properties, (a, b) -> { if (a[0] != b[0]) { return b[0] - a[0]; // Descending attack } else { return a[1] - b[1]; // Ascending defense } }); int weakCharacters = 0; int maxDefense = 0; for (int[] p : properties) { if (p[1] < maxDefense) { weakCharacters++; } maxDefense = Math.max(maxDefense, p[1]); } return weakCharacters; }}Complexity
Time
O(N log N), which is dominated by the sorting step. The single pass after sorting takes O(N) time.
Space
O(log N) or O(N), depending on the space requirements of the sorting algorithm used by the programming language's standard library.
Trade-offs
Pros
Much more efficient than the brute-force approach, with O(N log N) time complexity.
Passes the time limits for the given constraints.
Cons
The logic for the custom sorting can be non-obvious to come up with.
The time complexity is dominated by sorting, which is not as fast as a linear-time solution.
The most optimal solution leverages the constraint on the range of attack values. Instead of a comparison-based sort, we can use a form of bucketing to precompute the required information. This allows us to solve the problem in linear time.
Algorithm
- First, find the maximum attack value (
maxAttack) present in thepropertiesarray. - Create an integer array, let's call it
maxDefenseForAttack, of sizemaxAttack + 2. - Iterate through the
propertiesarray. For each character[attack, defense], update the bucket for its attack value:maxDefenseForAttack[attack] = Math.max(maxDefenseForAttack[attack], defense). - After the first pass,
maxDefenseForAttack[i]holds the maximum defense for a character with attacki. - Now, process
maxDefenseForAttackbackwards fromi = maxAttack - 1down to1. UpdatemaxDefenseForAttack[i] = Math.max(maxDefenseForAttack[i], maxDefenseForAttack[i + 1]). This step ensuresmaxDefenseForAttack[i]stores the maximum defense among all characters with an attack ofior greater. - Initialize
weakCharacters = 0. - Iterate through the
propertiesarray one last time. For each character[attack, defense]:- A character is weak if there exists another character with strictly greater attack and defense. The maximum defense for any character with an attack strictly greater than
attackis now stored inmaxDefenseForAttack[attack + 1]. - If
defense < maxDefenseForAttack[attack + 1], incrementweakCharacters.
- A character is weak if there exists another character with strictly greater attack and defense. The maximum defense for any character with an attack strictly greater than
- Return
weakCharacters.
Walkthrough
This approach avoids the O(N log N) sorting step by using an array to group characters by their attack value. The constraints state that attack values are at most 10^5, which makes this feasible.
- We create an array
maxDefenseForAttackto store the maximum defense for each possible attack value. - We iterate through the input properties and populate this array.
- We then make a second pass over
maxDefenseForAttack, but this time backwards. This transforms the array into a suffix-maximum array, wheremaxDefenseForAttack[i]now holds the maximum defense found among all characters with an attack value ofior more. - With this precomputed data, we can make a final pass through the input properties. For any given character
[attack, defense], we can instantly look up the maximum defense of any character with a strictly greater attack (maxDefenseForAttack[attack + 1]). If the current character's defense is less than this value, it is weak.
This method breaks the problem down into a few linear passes, resulting in an overall linear time complexity.
class Solution { public int numberOfWeakCharacters(int[][] properties) { int maxAttack = 0; for (int[] p : properties) { maxAttack = Math.max(maxAttack, p[0]); } int[] maxDefenseForAttack = new int[maxAttack + 2]; for (int[] p : properties) { maxDefenseForAttack[p[0]] = Math.max(maxDefenseForAttack[p[0]], p[1]); } // Create a suffix max array for (int i = maxAttack - 1; i >= 1; i--) { maxDefenseForAttack[i] = Math.max(maxDefenseForAttack[i], maxDefenseForAttack[i + 1]); } int weakCharacters = 0; for (int[] p : properties) { int attack = p[0]; int defense = p[1]; // A character is weak if there's a character with a strictly greater attack // that also has a strictly greater defense. // maxDefenseForAttack[attack + 1] gives the max defense for any attack > 'attack'. if (defense < maxDefenseForAttack[attack + 1]) { weakCharacters++; } } return weakCharacters; }}Complexity
Time
O(N + K), where N is the number of characters and K is the maximum attack value. This is because we make a few passes of size N and one pass of size K.
Space
O(K), where K is the maximum possible attack value. We need an array to store the maximum defense for each attack value.
Trade-offs
Pros
The most efficient solution with a linear time complexity.
Conceptually simple, involving a few passes over the data and an auxiliary array.
Cons
Requires extra space proportional to the maximum attack value, which could be an issue if the range of attack values is extremely large.
Solutions
Solution
class Solution {public int numberOfWeakCharacters(int[][] properties) { Arrays.sort(properties, (a, b)->b[0] - a[0] == 0 ? a[1] - b[1] : b[0] - a[0]); int ans = 0, mx = 0; for (var x : properties) { if (x[1] < mx) { ++ans; } mx = Math.max(mx, x[1]); } return ans; }}/** * @param {number[][]} properties * @return {number} */ var numberOfWeakCharacters = function (properties) { 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; };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; }};class Solution: def numberOfWeakCharacters(self, properties: List[List[int]]) -> int: properties . sort(key=lambda x: (- x[0], x[1])) ans = mx = 0 for _, x in properties: ans += x < mx mx = max(mx, x) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.