The Number of Weak Characters in the Game

medium array stack greedy sorting monotonic stack

Problem

A character is weak if some other character has strictly greater attack and strictly greater defense. Return the number of weak characters.

Inputproperties = [[5,5],[6,3],[3,6]]

Output0

No one dominates another in both dimensions strictly.

properties (format: a,d; a,d; ...)

def number_of_weak_characters(properties):
    properties.sort(key=lambda p: (-p[0], p[1]))
    weak = 0
    max_def = 0
    for _, d in properties:
        if d < max_def:
            weak += 1
        else:
            max_def = d
    return weak

function numberOfWeakCharacters(properties) {
  properties.sort((a, b) => a[0] === b[0] ? a[1] - b[1] : b[0] - a[0]);
  let weak = 0, maxDef = 0;
  for (const [, d] of properties) {
    if (d < maxDef) weak++;
    else maxDef = d;
  }
  return weak;
}

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);
        int weak = 0, maxDef = 0;
        for (int[] p : properties) {
            if (p[1] < maxDef) weak++;
            else maxDef = p[1];
        }
        return weak;
    }
}

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 weak = 0, maxDef = 0;
    for (auto& p : properties) {
        if (p[1] < maxDef) weak++;
        else maxDef = p[1];
    }
    return weak;
}

Explanation

A character is weak if someone else beats it in both attack and defense. Checking every pair would be slow, so the trick is to sort cleverly and then make a single sweep.

We sort by attack descending, and for ties in attack we sort by defense ascending. Now as we walk left to right, every character we have already seen has attack greater than or equal to the current one. We keep maxDef, the biggest defense seen so far.

If the current character's defense is strictly less than maxDef, then some earlier character had higher attack and higher defense, so it is weak. The tie-break (defense ascending) is what keeps equal-attack characters from wrongly counting each other.

Example: [[5,5],[6,3],[3,6]] sorts to [[6,3],[5,5],[3,6]]. Sweeping: maxDef becomes 3, then 5, then at [3,6] defense 6 is not below 5, so nobody is weak. Answer is 0.

The sort is the costly part at O(n log n); the sweep itself is a single linear pass.

Time: O(n log n) Space: O(1)