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 <= 105Sort 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.
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.
C
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as we're sorting in place.
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.
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.
JavaScript
Time complexity: O(n log n) because of sorting.
Space complexity: O(1), with the in-place sort.
| 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. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,649 views views
Watch 9 more video solutions →Practice The Number of Weak Characters in the Game with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor