# The Number of Weak Characters in the Game
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-number-of-weak-characters-in-the-game)
Canonical: https://scaleengineer.com/dsa/problems/the-number-of-weak-characters-in-the-game
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Pinterest](https://scaleengineer.com/companies/pinterest)
---
## Problem
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 <= 105`
* `properties[i].length == 2`
* `1 <= attacki, defensei <= 105`

# Approaches
## Brute Force
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.
**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.
**Pros:** Simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** Extremely inefficient for the given constraints (`n` up to 10^5).; The O(N^2) complexity will lead to a 'Time Limit Exceeded' (TLE) error on most platforms.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `weakCharacters` to 0.
- Iterate through each character `i` from `0` to `n-1`, where `n` is the number of characters.
- For each character `i`, start a nested loop to iterate through all other characters `j` from `0` to `n-1`.
- If `i` and `j` are the same character, skip to the next iteration.
- Check if character `j` is strictly stronger than character `i` by comparing their properties: `properties[j][0] > properties[i][0]` and `properties[j][1] > properties[i][1]`.
- If a stronger character `j` is found, it means character `i` is weak. We increment `weakCharacters` and break the inner loop, as we only need one such character to confirm weakness.
- After the loops complete, return the total `weakCharacters` count.

## Sorting
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Sort the `properties` array 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 = 0` and a variable `maxDefense = 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 than `maxDefense`, it means we have already seen a character with a strictly greater attack and a greater defense. Increment `weakCharacters`.
  - Update `maxDefense` to be the maximum of its current value and the current character's defense: `maxDefense = Math.max(maxDefense, p[1])`.
- Return `weakCharacters`.

## Linear Scan with Bucketing
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.
**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.
**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.
### Explanation
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.

1.  We create an array `maxDefenseForAttack` to store the maximum defense for each possible attack value.
2.  We iterate through the input properties and populate this array.
3.  We then make a second pass over `maxDefenseForAttack`, but this time backwards. This transforms the array into a suffix-maximum array, where `maxDefenseForAttack[i]` now holds the maximum defense found among all characters with an attack value of `i` or more.
4.  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.

```java
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;
    }
}
```
### Algorithm
- First, find the maximum attack value (`maxAttack`) present in the `properties` array.
- Create an integer array, let's call it `maxDefenseForAttack`, of size `maxAttack + 2`.
- Iterate through the `properties` array. 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 attack `i`.
- Now, process `maxDefenseForAttack` backwards from `i = maxAttack - 1` down to `1`. Update `maxDefenseForAttack[i] = Math.max(maxDefenseForAttack[i], maxDefenseForAttack[i + 1])`. This step ensures `maxDefenseForAttack[i]` stores the maximum defense among all characters with an attack of `i` or greater.
- Initialize `weakCharacters = 0`.
- Iterate through the `properties` array 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 `attack` is now stored in `maxDefenseForAttack[attack + 1]`.
  - If `defense < maxDefenseForAttack[attack + 1]`, increment `weakCharacters`.
- Return `weakCharacters`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @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;
  };

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```