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.
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.