LeetCode 1996 - The Number of Weak Characters in the Game

In this problem, every character in the game has two attributes: - attack - defense The input is a 2D array called properties, where: represents the stats of the i-th character.

leetcodemediumarraystackgreedysortingmonotonic-stack

LeetCode Problem 1996

Difficulty: 🟡 Medium
Topics: Array, Stack, Greedy, Sorting, Monotonic Stack

Solution

Problem Understanding

In this problem, every character in the game has two attributes:

  • attack
  • defense

The input is a 2D array called properties, where:

properties[i] = [attacki, defensei]

represents the stats of the i-th character.

A character is considered weak if there exists another character with:

  • strictly greater attack
  • strictly greater defense

Both conditions must be true at the same time.

For example:

A = [2, 3]
B = [5, 4]

Character A is weak because:

5 > 2
4 > 3

Both attack and defense are strictly larger.

However:

A = [2, 5]
B = [5, 4]

is not weak because even though attack is larger, defense is not.

The goal is to count how many characters are weak.

The constraints are important:

2 <= properties.length <= 100000

This means we may need to process up to one hundred thousand characters. A quadratic solution that compares every pair of characters would require:

O(n^2)

operations, which becomes too slow for large inputs.

The values of attack and defense can also be as large as 100000, but that mainly affects storage, not algorithm choice.

Several edge cases are important:

  • Multiple characters can have the same attack value.
  • Multiple characters can have the same defense value.
  • A character is only weak if another character has strictly greater values for both attributes.
  • Characters with equal attack values must not incorrectly count each other as weak.
  • Sorting order becomes extremely important for correctness.

For example:

[[5,5], [5,6]]

Neither character is weak because attack values are equal, even though one defense is larger.

Handling equal attack values correctly is the core challenge of the problem.

Approaches

Brute Force Approach

The most direct solution is to compare every character with every other character.

For each character i, we scan all other characters j and check:

attackj > attacki AND defensej > defensei

If such a character exists, then character i is weak.

This approach is correct because it explicitly checks the exact condition from the problem statement for every pair of characters.

However, the time complexity is too large.

If there are n characters, we perform roughly:

n * n

comparisons.

With n = 100000, this becomes approximately:

10^10

operations, which is far beyond acceptable limits.

Optimal Greedy + Sorting Approach

The key observation is that after sorting the characters properly, we can process them in one pass while tracking the maximum defense seen so far.

The critical detail is how we sort:

  • Sort by attack in descending order
  • If attack values are equal, sort defense in ascending order

Why does this help?

When we process characters from left to right after sorting:

  • Every previously seen character has attack greater than or equal to the current one.
  • Because equal attack values are sorted by ascending defense, characters with the same attack cannot incorrectly mark each other as weak.

While iterating, we maintain:

max_defense_seen

If the current character's defense is smaller than max_defense_seen, then we already encountered a character with:

  • strictly larger attack
  • larger defense

Therefore, the current character is weak.

This transforms the problem into a single linear scan after sorting.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compare every pair of characters
Optimal O(n log n) O(1) or O(log n) Sort characters and scan once

Algorithm Walkthrough

  1. Sort the characters by:
  • attack in descending order
  • defense in ascending order when attacks are equal

This ordering is essential.

Descending attack ensures that previously processed characters always have attack greater than or equal to the current character.

Ascending defense for equal attacks prevents characters with the same attack from incorrectly being counted as weak. 2. Initialize:

  • max_defense = 0
  • weak_count = 0

max_defense tracks the highest defense value encountered so far among characters with greater attack. 3. Iterate through the sorted array from left to right. 4. For each character:

  • If its defense is smaller than max_defense, then the character is weak.
  • Increment weak_count.
  1. Otherwise, update:
max_defense = current_defense

because this defense is now the largest seen so far. 6. Continue until all characters are processed. 7. Return weak_count.

Why it works

After sorting, every previously processed character has attack greater than or equal to the current character.

For characters with equal attack, sorting defense in ascending order guarantees that no equal attack character can falsely mark another as weak. A larger defense among equal attacks appears later, not earlier.

Therefore, if the current defense is less than the maximum defense seen so far, the corresponding earlier character must have:

  • strictly larger attack
  • strictly larger defense

which exactly matches the definition of a weak character.

Python Solution

from typing import List

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda p: (-p[0], p[1]))

        max_defense = 0
        weak_count = 0

        for attack, defense in properties:
            if defense < max_defense:
                weak_count += 1
            else:
                max_defense = defense

        return weak_count

The implementation begins by sorting the array using a custom key.

key=lambda p: (-p[0], p[1])

This means:

  • higher attack comes first
  • for equal attack, lower defense comes first

This sorting order is the foundation of the algorithm's correctness.

After sorting, the algorithm scans the array once.

max_defense stores the largest defense encountered among previously processed characters.

For each character:

if defense < max_defense:

we know a stronger character already exists, so the character is weak.

Otherwise, we update:

max_defense = defense

because this becomes the new strongest defense seen so far.

The algorithm only needs one pass after sorting, making it efficient enough for the problem constraints.

Go Solution

package main

import "sort"

func numberOfWeakCharacters(properties [][]int) int {
    sort.Slice(properties, func(i, j int) bool {
        if properties[i][0] == properties[j][0] {
            return properties[i][1] < properties[j][1]
        }
        return properties[i][0] > properties[j][0]
    })

    maxDefense := 0
    weakCount := 0

    for _, character := range properties {
        defense := character[1]

        if defense < maxDefense {
            weakCount++
        } else {
            maxDefense = defense
        }
    }

    return weakCount
}

The Go implementation follows the same logic as the Python version.

The main difference is sorting syntax. Go uses:

sort.Slice()

with a custom comparator function.

Go slices are reference types, so sorting modifies the original input directly, similar to Python's in place sort.

No integer overflow concerns exist because the values are well within Go's integer range.

The algorithm uses only a few integer variables in addition to the input array.

Worked Examples

Example 1

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

Step 1: Sort

Sorted order:

[[6,3],[5,5],[3,6]]

Step 2: Scan

Character max_defense before Weak? max_defense after weak_count
[6,3] 0 No 3 0
[5,5] 3 No 5 0
[3,6] 5 No 6 0

Final answer:

0

Example 2

properties = [[2,2],[3,3]]

Step 1: Sort

[[3,3],[2,2]]

Step 2: Scan

Character max_defense before Weak? max_defense after weak_count
[3,3] 0 No 3 0
[2,2] 3 Yes 3 1

Final answer:

1

Example 3

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

Step 1: Sort

[[10,4],[4,3],[1,5]]

Step 2: Scan

Character max_defense before Weak? max_defense after weak_count
[10,4] 0 No 4 0
[4,3] 4 Yes 4 1
[1,5] 4 No 5 1

Final answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) or O(log n) Only a few extra variables are used, excluding sort internals

The dominant operation is sorting, which requires:

O(n log n)

time.

The scan afterward is linear:

O(n)

so it does not affect the overall complexity.

The algorithm itself uses constant extra space, although sorting implementations may internally use logarithmic stack space.

Test Cases

from typing import List

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda p: (-p[0], p[1]))

        max_defense = 0
        weak_count = 0

        for attack, defense in properties:
            if defense < max_defense:
                weak_count += 1
            else:
                max_defense = defense

        return weak_count

solution = Solution()

assert solution.numberOfWeakCharacters([[5,5],[6,3],[3,6]]) == 0
# No weak characters

assert solution.numberOfWeakCharacters([[2,2],[3,3]]) == 1
# Simple weak case

assert solution.numberOfWeakCharacters([[1,5],[10,4],[4,3]]) == 1
# Mixed ordering

assert solution.numberOfWeakCharacters([[5,5],[5,6]]) == 0
# Equal attack values should not count

assert solution.numberOfWeakCharacters([[1,1],[2,2],[3,3],[4,4]]) == 3
# Increasing chain

assert solution.numberOfWeakCharacters([[4,4],[3,3],[2,2],[1,1]]) == 3
# Already sorted descending

assert solution.numberOfWeakCharacters([[1,5],[2,4],[3,3],[4,2]]) == 0
# Defense decreases as attack increases

assert solution.numberOfWeakCharacters([[7,7],[1,2],[9,7],[7,3],[3,10]]) == 2
# Mixed complex case

assert solution.numberOfWeakCharacters([[2,2],[2,2],[2,2]]) == 0
# All identical

assert solution.numberOfWeakCharacters([[10,1],[1,10],[5,5]]) == 0
# No pair dominates another

Test Summary

Test Why
[[5,5],[6,3],[3,6]] Verifies no weak characters
[[2,2],[3,3]] Simplest valid weak relationship
[[1,5],[10,4],[4,3]] Mixed attack and defense ordering
[[5,5],[5,6]] Ensures equal attack is handled correctly
Increasing chain Multiple weak characters
Descending chain Verifies sorted input still works
Decreasing defense pattern Ensures no false positives
Mixed complex case Stress test for sorting correctness
All identical Duplicate handling
Cross dominance case Confirms strict inequality logic

Edge Cases

One important edge case occurs when multiple characters have the same attack value.

For example:

[[5,5],[5,6]]

Even though one character has larger defense, neither is weak because attack values are equal. A naive sorting order could incorrectly count one as weak. Sorting equal attacks by ascending defense prevents this issue because equal attack characters never incorrectly dominate earlier ones.

Another important case is when defense values decrease while attack values increase.

Example:

[[1,5],[2,4],[3,3],[4,2]]

Every character has stronger attack than the previous one, but weaker defense. No character satisfies both strict inequalities simultaneously. The algorithm handles this correctly because max_defense never exceeds the earlier large defense values in a way that creates a false positive.

A third edge case involves duplicate characters.

Example:

[[2,2],[2,2],[2,2]]

All characters are identical. Since strict inequality is required for both attack and defense, none are weak. The sorting and comparison logic naturally preserves this behavior because no defense becomes strictly smaller than max_defense for a stronger attack value.

A final important edge case is when almost every character is weak.

Example:

[[1,1],[2,2],[3,3],[4,4]]

Every character except the strongest one is weak. This validates that the algorithm properly accumulates the maximum defense seen so far and correctly identifies all dominated characters.