The Number of Weak Characters in the Game

Medium
403.

The Number of Weak Characters in the Game

The Number of Weak Characters in the Game is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

You are playing a game with characters, where properties[i] = [attack, defense].

A character is weak if some other character has strictly greater attack and strictly greater defense. Return the number of weak characters.

Example 1

Input
properties = [[5,5],[6,3],[3,6]]
Output
0

Example 2

Input
properties = [[2,2],[3,3]]
Output
1

Example 3

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

Constraints

  • 2 <= properties.length <= 40
  • 1 <= attack, defense <= 100000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} properties
 * @return {number}
 */
var numberOfWeakCharacters = function(properties) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

The Number of Weak Characters in the Game — Solution

The Number of Weak Characters in the Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

The Number of Weak Characters in the Game is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

Problem statement

You are playing a game with characters, where properties[i] = [attack, defense].

A character is weak if some other character has strictly greater attack and strictly greater defense. Return the number of weak characters.

Example 1

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

Example 2

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

Example 3

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

Constraints

  • 2 <= properties.length <= 40
  • 1 <= attack, defense <= 100000

Hints for The Number of Weak Characters in the Game

  1. Hint 1

    Sort by attack descending, breaking ties by defense ascending.

  2. Hint 2

    That tie-break guarantees equal-attack characters never count each other as weak.

  3. Hint 3

    Then sweep once, tracking the largest defense seen so far; anything below it is weak.

How to solve The Number of Weak Characters in the Game

Sort by attack descending with ties by defense ascending, then sweep tracking the maximum defense seen; a character with lower defense than that is weak.

Approach

  1. Sort by (-attack, defense).
  2. For each character, if defense < maxDefense, count it weak; else update maxDefense.

Why it works

Every earlier character has strictly greater attack, except ties, which the ascending-defense tie-break places so that an equal-attack character never has a larger defense before it. A larger defense seen earlier therefore comes from a strictly stronger character.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Ties by defense descending would wrongly mark equal-attack characters weak.

Reference solution

Python

def numberOfWeakCharacters(properties) -> int:
    ordered = sorted(properties, key=lambda p: (-p[0], p[1]))
    max_defense = 0
    weak = 0
    for _, defense in ordered:
        if defense < max_defense:
            weak += 1
        else:
            max_defense = defense
    return weak

Java

public static int numberOfWeakCharacters(int[][] properties) {
    int[][] s = properties.clone();
    Arrays.sort(s, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
    int maxDefense = 0, weak = 0;
    for (int[] p : s) {
        if (p[1] < maxDefense) weak++;
        else maxDefense = p[1];
    }
    return weak;
}

C++

int numberOfWeakCharacters(vector<vector<int>>& properties) {
    vector<vector<int>> s = properties;
    sort(s.begin(), s.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] > b[0];
        return a[1] < b[1];
    });
    int maxDefense = 0, weak = 0;
    for (const auto& p : s) {
        if (p[1] < maxDefense) weak++;
        else maxDefense = p[1];
    }
    return weak;
}

JavaScript

var numberOfWeakCharacters = function(properties) {
    const sorted = properties.slice().sort(function(a, b) {
        return a[0] !== b[0] ? b[0] - a[0] : a[1] - b[1];
    });
    let maxDefense = 0, weak = 0;
    for (let i = 0; i < sorted.length; i++) {
        if (sorted[i][1] < maxDefense) weak++;
        else maxDefense = sorted[i][1];
    }
    return weak;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms