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.
Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as we're sorting in place.
1def numberOfWeakCharacters(properties):
2 properties.sort(key=lambda x: (-x[0], x[1]))
3 max_defense = 0
4 weak_count = 0
5 for _, defense in properties:
6 if defense < max_defense:
7 weak_count += 1
8 else:
9 max_defense = defense
10 return weak_countThe 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.
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.
Time complexity: O(n log n) because of sorting.
Space complexity: O(1), with the in-place sort.
1import java.util.*;
2
3public class Solution {
4 public int numberOfWeakCharacters(int[][] properties) {
5 Arrays.sort(properties, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
6 int maxDefense = 0, weakCount = 0;
7 for (int[] prop : properties) {
8 if (prop[1] < maxDefense) {
9 weakCount++;
10 } else {
11 maxDefense = prop[1];
12 }
13 }
14 return weakCount;
15 }
16}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.