#1996

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

The Number of Weak Characters in the Game

Identify all weak characters in a game by analyzing attack and defense values using a stack-based greedy sorting approach efficiently.

array stack greedy sorting monotonic stack

Problem Statement

In this game, each character has two numeric attributes: attack and defense. You are given a 2D array properties where properties[i] = [attacki, defensei] represents the ith character's attributes. A character is considered weak if there exists another character with both strictly higher attack and defense values. The goal is to return the count of all weak characters in the given set.

Implement an efficient method to determine weak characters by leveraging sorting and stack-based state tracking. Sorting by attack and grouping characters with identical attack values can reduce unnecessary comparisons. Carefully handle the comparison of defense values to ensure only characters with strictly lower defense than a stronger counterpart are counted as weak.

Examples

Example 1

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

Output: 0

No character has strictly greater attack and defense than the other.

Example 2

Input: properties = [[2,2],[3,3]]

Output: 1

The first character is weak because the second character has a strictly greater attack and defense.

Example 3

Input: properties = [[1,5],[10,4],[4,3]]

Output: 1

The third character is weak because the second character has a strictly greater attack and defense.

Constraints

2 <= properties.length <= 105
properties[i].length == 2
1 <= attacki, defensei <= 105

Solution Approach

Sort by Attack Descending and Defense Ascending

Sort the array of characters in descending order of attack. For characters with the same attack value, sort by ascending defense. This ordering ensures that when iterating, any previously seen character with higher attack will automatically dominate current characters, allowing stack-based or running maximum tracking to detect weak characters efficiently.

Use Stack or Running Maximum to Track Defense

Initialize a variable to keep the maximum defense seen so far. Iterate through the sorted characters, and for each character, if its defense is less than the maximum, mark it as weak. Update the maximum defense whenever a character with higher defense is encountered. This stack-like state management prevents repeated full scans and leverages the sorted order to minimize comparisons.

Group Characters with Same Attack for Accurate Counting

When multiple characters have the same attack, process them together to avoid counting them as weak against each other. Only compare their defense against the global maximum defense from characters with strictly higher attack. This grouping prevents overcounting and correctly applies the problem's strict inequality condition.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n) time, iterating through the characters with running maximum is O(n) time, giving an overall O(n log n) time complexity. Space complexity is O(1) if using a single max variable or O(n) if maintaining a stack explicitly.

What Interviewers Usually Probe

Ask about sorting strategy and handling ties in attack values.
Probe if the candidate can maintain state efficiently without nested loops.
Check understanding of strict inequality and grouping by attack.

Common Pitfalls or Variants

Common pitfalls

Failing to group characters with the same attack before comparison.
Counting characters as weak against others with the same attack.
Using nested loops leading to O(n^2) time instead of optimized O(n log n).

Follow-up variants

Return indices of all weak characters instead of just the count.
Modify the problem to allow weak characters if only one attribute is strictly less.
Apply the same stack-based approach to 3D attributes including speed or magic.

FAQ

How do I efficiently find weak characters in this game problem?

Sort characters by descending attack and ascending defense, then use a running maximum or stack to detect those with strictly lower defense than previously seen characters.

Why do we group characters with the same attack before comparison?

Grouping prevents characters from being incorrectly counted as weak against others with identical attack values, satisfying the strict inequality requirement.

Can I use nested loops to compare all characters?

Nested loops are correct but inefficient; they lead to O(n^2) time. Using sorting with stack-based state management reduces time to O(n log n).

Does this approach work if defense values are very large?

Yes, because the algorithm only tracks the maximum defense seen so far, independent of absolute value size.

What pattern does this problem primarily follow?

It follows a stack-based state management pattern, where sorting and maintaining running maxima allow efficient identification of weak characters.

terminal

Solution

Solution 1: Sorting + Traversal

We can sort all characters in descending order of attack power and ascending order of defense power.

1

2

3

4

5

6

7

8

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: (-x[0], x[1]))
        ans = mx = 0
        for _, x in properties:
            ans += x < mx
            mx = max(mx, x)
        return ans

Continue Practicing

#2818 apply operations to maximize score #769 max chunks to make sorted #768 max chunks to make sorted ii