The Number of Weak Characters in the Game

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

Understanding the Visualization

Input Characters

Each character has [attack, defense] values

Find Domination

Check if any character dominates another in both stats

Count Weak

Return number of characters that are dominated

Key Takeaway

🎯 Key Insight: Sort by attack to eliminate one comparison dimension, then efficiently check defense values

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

Approach	Time	Space	Notes
✓ Monotonic Stack	O(n log n)	O(n)	Use a stack to efficiently track characters that can dominate others
Sort and Scan	O(n log n)	O(1)	Sort by attack descending, then track maximum defense seen so far
Brute Force Comparison	O(n²)	O(1)	Compare every character with every other character directly

Monotonic Stack — Algorithm Steps

Sort characters by attack descending, defense ascending
Use monotonic decreasing stack for defense values
When processing character, pop weaker defenses and count them

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Sorted

Handle characters by attack descending

Stack Operations

Pop weaker defenses, count as weak

Final Count

Total weak characters found

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    int* pairA = (int*)a;
    int* pairB = (int*)b;
    if (pairA[0] != pairB[0]) return pairB[0] - pairA[0];
    return pairA[1] - pairB[1];
}

int solution(int properties[][2], int n) {
    qsort(properties, n, sizeof(int[2]), compare);
    
    int stack[100000];
    int stackSize = 0;
    int weakCount = 0;
    
    for (int i = 0; i < n; i++) {
        int attack = properties[i][0], defense = properties[i][1];
        // Count and remove all characters with lower defense
        while (stackSize > 0 && stack[stackSize - 1] < defense) {
            stackSize--;
            weakCount++;
        }
        stack[stackSize++] = defense;
    }
    
    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 log n)

Sorting takes O(n log n), stack operations are O(n) total

⚡ Linearithmic

Space Complexity

O(n)

Stack can store up to n elements in worst case

⚡ Linearithmic Space

67.5K 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Monotonic Stack — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler