Skip to main content

1996 - The Number of Weak Characters in the Game

Difficulty: Medium | Pattern: Greedy / Sorting | Company tags: Amazon, Apple

Problem Statement​

You are playing a game that contains multiple characters. Each character has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attack_i, defense_i].

A character is said to be weak if any other character has both a strictly greater attack AND strictly greater defense. Return the number of weak characters.

Example 1:

Input: properties = [[5,5],[6,3],[3,6]]
Output: 0

Example 2:

Input: properties = [[2,2],[3,3]]
Output: 1  (character [2,2] is weak: [3,3] dominates)

Example 3:

Input: properties = [[1,5],[10,4],[4,3]]
Output: 1  ([4,3] is weak: [10,4] has higher attack AND defense... wait: 10>4 but 4=3? No: 4>3 ✓, 10>4 ✓)

Approach: Sort Attack DESC, Defense ASC (same attack) + Track Max Defense — O(n log n)​

Key insight: Sort by attack descending. For characters with the same attack, sort defense ascending (to avoid counting characters with same attack as dominators). Track the running max defense. A character is weak if its defense is less than the max defense seen so far.

def numberOfWeakCharacters(properties: list[list[int]]) -> int:
    # Sort by attack descending; for same attack, sort defense ascending
    properties.sort(key=lambda x: (-x[0], x[1]))
    
    max_def = 0
    weak = 0
    
    for attack, defense in properties:
        if defense < max_def:
            weak += 1
        else:
            max_def = defense
    
    return weak

Why Sort Defense Ascending for Same Attack?​

If two characters have the same attack, neither can dominate the other (need strictly greater attack). By sorting defense ascending for ties, we ensure that when we see a character with the same attack, max_def won't count it as a dominator.

Dry Run​

properties = [[2,2],[3,3]] → sorted: [3,3],[2,2]

charmax_defweak?
[3,3]33 not lt 0 → max_def=3
[2,2]32 lt 3 → weak=1

1 ✓

Edge Cases​

  • All same attack → no dominators → 0 weak
  • Strictly increasing on both dimensions → all but the last are weak
  • Single character → 0

Complexity​

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