Medium

The Number of Weak Characters in the Game

LAB

Given characters [attack,defense], return how many have another character with both higher attack and higher defense.

EXAMPLES

Example 1

Input
{
  "properties": [
    [
      5,
      5
    ],
    [
      6,
      3
    ],
    [
      3,
      6
    ]
  ]
}

Output
0

FUNCTION SHAPE

properties: intMatrix→int

SOLUTION NOTE

Sort by attack descending, defense ascending. Track max defense seen. A character is weak if its defense < max_defense.

Reveal reference solution +

pythonREFERENCE

def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
    # Sort by attack desc, then defense asc
    properties.sort(key=lambda x: (-x[0], x[1]))

    res = 0
    max_defense = 0

    for attack, defense in properties:
        if defense < max_defense:
            res += 1
        max_defense = max(max_defense, defense)

    return res

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗