The Number of Weak Characters in the Game: Sorting Trick

LeetCode The Number of Weak Characters in the Game (problem 1996, medium) asks you to count characters that are dominated by at least one other character. A character is "weak" if some other character has strictly greater attack AND strictly greater defense. The brute force is obvious, but there is a clever sorting trick that reduces a 2D comparison problem to a single linear scan.

The problem

You are given a 2D integer array properties where properties[i] = [attack_i, defense_i] represents the attack and defense values of the i-th character. A character is weak if there exists another character with strictly greater attack and strictly greater defense. Return the number of weak characters.

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

Character [7,7] dominates [5,5], [6,3], and [3,6], because its attack and defense are both strictly greater. Only [7,7] itself is not weak.

Why this problem matters

This problem tests your ability to reduce a 2D comparison to a simpler 1D scan. Comparing every pair in two dimensions is expensive. The sorting trick collapses one dimension (attack) into a guaranteed ordering, leaving you with only one dimension (defense) to check. It is a clean example of how custom sort orders unlock efficient algorithms.

The brute force

Check every pair. For each character, scan all other characters to see if any one has strictly greater attack and defense.

def numberOfWeakCharacters(properties):
    count = 0
    for i in range(len(properties)):
        for j in range(len(properties)):
            if i != j:
                if properties[j][0] > properties[i][0] and properties[j][1] > properties[i][1]:
                    count += 1
                    break
    return count

This is O(n^2) and will time out on large inputs. Each character checks against every other character, and there is no way to prune the search without additional structure.

The sorting insight

Here is the key idea. Sort the characters by attack in descending order. For characters with the same attack, sort by defense in ascending order.

After sorting, scan left to right while tracking the maximum defense seen so far. If the current character's defense is less than the max defense, it must be weak. Why? Every character to the left has attack greater than or equal to the current character's attack. And the max defense came from one of those left-side characters. So at least one character has both strictly greater attack and strictly greater defense.

But wait, what about characters with the same attack? This is where the ascending defense sort matters. If two characters have attack = 6 and defenses 3 and 8, sorting defense ascending puts [6,3] before [6,8]. When we scan [6,3], the max defense so far comes from characters with attack strictly greater than 6 (not from [6,8], which has not been scanned yet). This prevents characters with the same attack from incorrectly flagging each other as weak.

Clean Python solution

def numberOfWeakCharacters(properties):
    properties.sort(key=lambda x: (-x[0], x[1]))
    max_def = 0
    count = 0
    for atk, dfn in properties:
        if dfn < max_def:
            count += 1
        else:
            max_def = dfn
    return count

Step-by-step walkthrough

Let's trace through properties = [[5,5],[6,3],[3,6],[7,7]]. After sorting by attack descending and defense ascending for ties, we get [[7,7],[6,3],[5,5],[3,6]]. We scan left to right, tracking the maximum defense.

The scan touches each character exactly once. The only state we maintain is a single integer, maxDef. When a character's defense falls below this running maximum, we know it is dominated because the character that set the maximum had a strictly greater attack (guaranteed by the sort order) and a strictly greater defense (guaranteed by the comparison).

Why sort defense ascending for same attack?

This is the critical detail that makes the algorithm correct. Consider two characters with the same attack: [6,3] and [6,8]. Neither dominates the other because their attacks are equal (not strictly greater).

If we sorted defense descending within the same attack, [6,8] would come first. When we later scan [6,3], the max defense would be 8 (set by [6,8]), and we would incorrectly count [6,3] as weak. But [6,8] does not dominate [6,3] because the attacks are equal.

Sorting defense ascending within the same attack ensures that when we scan a character, the max defense so far only reflects characters with strictly greater attack. Characters with the same attack appear in defense-ascending order, so their defenses never pollute the running maximum before same-attack peers are checked.

Complexity analysis

Time: O(n log n). Sorting dominates. The scan is O(n).

Space: O(n). The sort may use O(n) auxiliary space depending on the language. The scan itself uses O(1) extra space (just max_def and count).

The building blocks

This problem is built from a few reusable ideas:

Custom sort ordering

Sorting by one key descending and another key ascending within ties is a powerful technique. You see the same idea in problems like meeting rooms, interval scheduling, and envelope sorting. The key=lambda x: (-x[0], x[1]) pattern in Python negates the first field for descending order while keeping the second field in natural ascending order.

Single pass with running maximum

After sorting removes one dimension of complexity, a single left-to-right scan with a running maximum handles the other dimension. This same pattern shows up in Best Time to Buy and Sell Stock (track running minimum) and Daily Temperatures (track from one direction).

2D dominance problem reduction

Whenever you need to compare items on two attributes simultaneously, ask yourself whether sorting on one attribute can simplify the second comparison. This reduction from 2D to 1D is a general technique that appears in the Russian Doll Envelopes problem and longest increasing subsequence variants.

Edge cases

Before submitting, verify your solution handles:

• All same attack like [[3,1],[3,5],[3,2]]: no character can be weak because the "strictly greater attack" condition is never met. The ascending defense sort ensures the running max never falsely triggers.
• All same defense like [[1,5],[3,5],[2,5]]: no character can be weak because the "strictly greater defense" condition is never met. Even though attacks differ, no defense exceeds another.
• Single character [[1,1]]: returns 0. Nothing to compare against.
• All characters identical like [[4,4],[4,4],[4,4]]: returns 0. Equal is not strictly greater.
• Already sorted input like [[1,1],[2,2],[3,3]]: each character is dominated by the next. Returns 2 (all except the strongest).

From understanding to recall

The sorting trick is elegant, but it has a subtle detail (the ascending defense for same attack) that is easy to forget under pressure. In an interview, you might remember to sort by attack descending but forget the tie-breaking rule, leading to wrong answers on edge cases.

Spaced repetition helps here. You drill the sort key (-attack, +defense) and the single-pass max-defense scan until both are automatic. The first time you practice, you think carefully about why ascending defense matters. By the third repetition, the reasoning is internalized and the code flows without hesitation.

Related posts

• 3Sum Closest - Another problem where clever sorting enables a linear scan
• Daily Temperatures - Uses a similar "track maximum from one direction" pattern
• Best Time to Buy and Sell Stock - Single pass with running optimum, same scanning pattern