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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 int *p1 = *(int**)a;
6 int *p2 = *(int**)b;
7 if (p1[0] != p2[0]) return p2[0] - p1[0];
8 return p1[1] - p2[1];
9}
10
11int numberOfWeakCharacters(int** properties, int propertiesSize, int* propertiesColSize) {
12 qsort(properties, propertiesSize, sizeof(int*), compare);
13 int maxDefense = 0, weakCount = 0;
14 for (int i = 0; i < propertiesSize; i++) {
15 if (properties[i][1] < maxDefense) {
16 weakCount++;
17 } else {
18 maxDefense = properties[i][1];
19 }
20 }
21 return weakCount;
22}The C solution uses qsort to sort the character properties. A custom compare function is implemented to sort by attack descending and defense ascending. As it iterates through the sorted properties, it tracks the maximum defense seen, using it to count 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.
1function numberOfWeakCharacters(properties) {
2 properties.sort((a, b) => a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1]);
3 let maxDefense = 0;
4 let weakCount = 0;
5 for (let [_, defense] of properties) {
6 if (defense < maxDefense) {
7 weakCount++;
8 } else {
9 maxDefense = defense;
10 }
11 }
12 return weakCount;
13}The JavaScript solution mirrors the Python and Java implementations with sorting and iterating through the characters while updating maximum defense and counting weak characters based on the conditions as described.