The Number of Weak Characters in the Game - Problem

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense.

You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei.

Return the number of weak characters.

Input & Output

Example 1 — Mixed Characters

$ Input: properties = [[5,5],[6,3],[2,4],[1,6]]

› Output: 1

💡 Note: Character [2,4] is weak because [5,5] has both higher attack (5>2) and higher defense (5>4). All other characters are not dominated by any single character.

Example 2 — All Strong Characters

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

› Output: 1

💡 Note: Character [2,2] is weak because [3,3] has both higher attack (3>2) and higher defense (3>2). Character [3,3] is not weak.

Example 3 — No Weak Characters

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

› Output: 0

💡 Note: No character dominates any other in both attack AND defense: [1,5] has highest defense, [10,4] has highest attack, [4,3] is not dominated by either.

Constraints

2 ≤ properties.length ≤ 10⁵
properties[i].length == 2
1 ≤ attack_i, defense_i ≤ 10⁵

Visualization

Tap to expand

Asked in

a Amazon 45 G Google 38 M Microsoft 32 A Apple 28

The key insight is to sort characters by attack descending, then use either a simple scan or monotonic stack to efficiently find dominated characters. Best approach uses sorting + scanning in O(n log n) time, O(1) space.

Common Approaches

✓ Brute Force Comparison

⏱️ Time: O(n²) Space: O(1)

For each character, iterate through all other characters to check if any character has both higher attack and higher defense values.

Monotonic Stack

⏱️ Time: O(n log n) Space: O(n)

Sort by attack descending and defense ascending, then use a monotonic decreasing stack to track characters. Each time we process a character, all characters in the stack with lower defense are weak.

Sort and Scan

⏱️ Time: O(n log n) Space: O(1)

Sort characters by attack in descending order, then iterate through them while maintaining the maximum defense value seen. A character is weak if its defense is less than the current maximum defense from stronger attackers.

Brute Force Comparison — Algorithm Steps

For each character i
Compare with every other character j
Count how many characters are dominated by at least one other character

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Character 1

Compare [5,5] with all others

Check Character 2

Compare [6,3] with all others

Count Weak

Characters dominated by others

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int properties[][2], int n) {
    int weakCount = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (properties[j][0] > properties[i][0] && properties[j][1] > properties[i][1]) {
                    weakCount++;
                    break;
                }
            }
        }
    }
    
    return weakCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int properties[100000][2];
    int n = 0;
    
    char* ptr = strchr(line, '[') + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int attack = 0, defense = 0;
            sscanf(ptr, "%d,%d", &attack, &defense);
            properties[n][0] = attack;
            properties[n][1] = defense;
            n++;
            while (*ptr && *ptr != ']') ptr++;
            if (*ptr == ']') ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(properties, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops compare each character with every other character

⚡ Linearithmic

Space Complexity

O(1)

Only using a few variables for counting

✓ Linear Space

67.6K Views

Medium-High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

The Number of Weak Characters in the Game - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler