Problem Description

You have a game with multiple characters where each character has two properties: attack and defense. These properties are given as a 2D array properties where properties[i] = [attack_i, defense_i] represents the attack and defense values for the i-th character.

A character is considered weak if there exists at least one other character that has both higher attack AND higher defense values. In other words, character i is weak if there's another character j such that:

• attack_j > attack_i
• defense_j > defense_i

Your task is to count how many weak characters exist in total.

The solution uses a clever sorting strategy. By sorting characters with attack in descending order and defense in ascending order (when attacks are equal), we can process characters in a specific order. The key insight is that when we sort by (-attack, defense):

1. Characters are grouped by attack value (highest to lowest)
2. Within the same attack value, characters are ordered by defense (lowest to highest)

As we traverse through the sorted list:

• We maintain a variable mx to track the maximum defense seen so far
• For each character, if its defense is less than mx, it means there's a previously seen character with both higher attack (because we're moving from higher to lower attacks) and higher defense
• The sorting ensures we don't incorrectly count characters with the same attack value as dominating each other

For example, with properties = [[5,5],[6,3],[3,6]]:

• After sorting: [[6,3],[5,5],[3,6]]
• Process [6,3]: mx = 3, no weak character
• Process [5,5]: defense 5 > mx 3, so not weak, update mx = 5
• Process [3,6]: defense 6 > mx 5, so not weak, update mx = 6
• Result: 1 weak character (the one with [5,5] is dominated by [3,6])

Intuition

The key challenge is determining which characters are weak without comparing every pair, which would be inefficient. We need a way to systematically check if any character dominates another.

Let's think about what makes a character weak: it needs to have both lower attack AND lower defense than some other character. If we randomly check characters, we'd need to compare each one against all others, leading to O(n²) comparisons.

The breakthrough comes from realizing that if we process characters in a specific order, we can keep track of just one value (maximum defense) instead of comparing with all previous characters.

Why sort by attack descending? When we process characters from highest to lowest attack, any character we've already seen is guaranteed to have higher or equal attack. This handles one condition automatically.

But what about characters with the same attack value? They can't dominate each other (since domination requires strictly greater values). To avoid false positives, we sort characters with the same attack by defense in ascending order. This ensures that when we encounter a character with the same attack value, the maximum defense we've tracked so far doesn't include characters with the same attack level that have higher defense.

Here's the clever part: as we traverse the sorted list:

• If current defense < maximum defense seen so far, then there must be a previous character with both higher attack (due to our traversal order) and higher defense
• If current defense ≥ maximum defense, this character isn't weak (at least not by any character we've seen so far)

The sorting pattern (-attack, defense) creates this perfect processing order where we only need to track one variable (mx for maximum defense) and make one comparison per character, reducing complexity from O(n²) to O(n log n).

Learn more about Stack, Greedy, Sorting and Monotonic Stack patterns.

Solution Approach

The implementation follows these steps:

Step 1: Sort the characters

properties.sort(key=lambda x: (-x[0], x[1]))

We sort the properties array using a custom key. The lambda function (-x[0], x[1]) creates a tuple where:

• -x[0] sorts by attack in descending order (negative value reverses the order)
• x[1] sorts by defense in ascending order when attacks are equal

This ensures characters are ordered from highest to lowest attack, and within the same attack level, from lowest to highest defense.

Step 2: Initialize tracking variables

ans = mx = 0

• ans: Counter for weak characters
• mx: Tracks the maximum defense value seen so far

Step 3: Traverse and count weak characters

for _, x in properties:
    ans += x < mx
    mx = max(mx, x)

For each character in the sorted list:

• We only care about the defense value x (attack is handled by sorting)
• x < mx: If current defense is less than the maximum defense seen, this character is weak
• ans += x < mx: In Python, True equals 1 and False equals 0, so this increments ans when the character is weak
• mx = max(mx, x): Update the maximum defense for future comparisons

Why this works:

• When we check x < mx, we know that mx comes from characters with higher attack values (due to our traversal order)
• The ascending defense sort within same attack values prevents false positives
• Each character is processed exactly once, making this O(n) for traversal after O(n log n) sorting

Time Complexity: O(n log n) for sorting + O(n) for traversal = O(n log n)
Space Complexity: O(1) if we don't count the sorting space, otherwise O(log n) for sorting

Example Walkthrough

Let's walk through a concrete example with properties = [[2,2],[3,3],[1,5],[4,1]].

Step 1: Initial Setup

• Original array: [[2,2],[3,3],[1,5],[4,1]]
• We need to find characters where another character has BOTH higher attack AND defense

Step 2: Sort by (-attack, defense)

• Apply sorting key: (-x[0], x[1])
• [2,2] → key: (-2, 2)
• [3,3] → key: (-3, 3)
• [1,5] → key: (-1, 5)
• [4,1] → key: (-4, 1)
• Sorted: [[4,1],[3,3],[2,2],[1,5]]

Step 3: Process each character

• Initialize: ans = 0, mx = 0

Processing [4,1]:

• Defense = 1, check if 1 < 0? No
• Not weak, update mx = max(0, 1) = 1
• ans = 0

Processing [3,3]:

• Defense = 3, check if 3 < 1? No
• Not weak, update mx = max(1, 3) = 3
• ans = 0

Processing [2,2]:

• Defense = 2, check if 2 < 3? Yes!
• This is weak! (There's a character with attack ≥ 3 and defense = 3)
• Update mx = max(3, 2) = 3
• ans = 1

Processing [1,5]:

• Defense = 5, check if 5 < 3? No
• Not weak, update mx = max(3, 5) = 5
• ans = 1

Result: 1 weak character ([2,2] is dominated by [3,3])

Why the sorting works:

• When we checked [2,2], the mx = 3 came from [3,3] which has attack 3 > 2
• The descending attack sort guarantees any mx value comes from higher attack characters
• The ascending defense sort (within same attack) prevents same-attack characters from incorrectly dominating each other

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the number of characters (length of the properties list). This is dominated by the sorting operation properties.sort(), which uses Python's Timsort algorithm with O(n × log n) complexity. The subsequent iteration through the sorted array takes O(n) time, but this is absorbed by the sorting complexity.

The space complexity is O(log n). While the sorting is done in-place (modifying the original list), Python's Timsort algorithm requires O(log n) space for its internal operations, specifically for maintaining the stack used in the merge process. The additional variables ans and mx only require O(1) space, so the overall space complexity remains O(log n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Sorting Order for Defense Values

The Problem: A common mistake is sorting defense values in descending order when attacks are equal, like this:

properties.sort(key=lambda x: (-x[0], -x[1]))  # WRONG!

This creates a critical issue where characters with the same attack value can incorrectly dominate each other.

Example of the Bug: Consider properties = [[7,7],[7,3],[7,5]]

With incorrect sorting (-attack, -defense):

• Sorted: [[7,7],[7,5],[7,3]]
• Process [7,7]: mx = 7
• Process [7,5]: 5 < 7, counted as weak (WRONG!)
• Process [7,3]: 3 < 7, counted as weak (WRONG!)
• Result: 2 weak characters (incorrect)

The Fix: Sort defense in ascending order when attacks are equal:

properties.sort(key=lambda x: (-x[0], x[1]))  # CORRECT!

With correct sorting:

• Sorted: [[7,3],[7,5],[7,7]]
• Process [7,3]: mx = 3
• Process [7,5]: 5 > 3, not weak, mx = 5
• Process [7,7]: 7 > 5, not weak, mx = 7
• Result: 0 weak characters (correct)

Pitfall 2: Not Understanding Why Defense Must Be Ascending

The Problem: Some might think sorting order doesn't matter as long as we group by attack. This misunderstanding leads to counting characters with the same attack as dominating each other.

Key Insight: By processing lower defense values first within the same attack group:

• The mx variable only gets updated after processing all characters with the current attack level
• This prevents any character from being dominated by another character with the same attack value
• When we move to a lower attack group, mx already contains the highest defense from all higher attack groups

Pitfall 3: Using Nested Loops Instead of Sorting

The Problem: Attempting a brute force O(n²) solution:

def numberOfWeakCharacters(self, 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

Issues:

• Time complexity is O(n²), which times out for large inputs
• Less elegant and harder to optimize

The Fix: Use the sorting approach which reduces complexity to O(n log n) and elegantly handles the comparison logic through ordering.