The Number of Weak Characters in the Game - Solution & Explanation

Q: Is The Number of Weak Characters in the Game easy or hard?

The problem is rated Medium because it requires recognizing how sorting order prevents false comparisons between characters with equal attack. Once the ordering trick is understood, the implementation becomes a straightforward greedy scan.

Q: The Number of Weak Characters in the Game Python/Java solution

In Python, the typical implementation sorts the list of pairs and iterates while tracking the maximum defense. In Java, the same strategy works with Arrays.sort and a linear pass. Another Java approach uses TreeMap as a balanced BST to track higher defenses.

Q: How to solve The Number of Weak Characters in the Game in O(n)?

A pure O(n) solution is generally not practical because the problem requires ordering characters by attack to compare dominance relationships. Sorting creates the correct processing order, which leads to the common O(n log n) greedy solution. After sorting, the detection step itself is O(n).

Q: What is the best approach for The Number of Weak Characters in the Game?

The most common solution sorts characters by attack descending and defense ascending, then scans while tracking the maximum defense seen so far. If a character's defense is lower than the current maximum, it is weak. This greedy strategy runs in O(n log n) time due to sorting and O(1) extra space.

Q: Is The Number of Weak Characters in the Game asked at Google/Amazon/Meta?

Variants of dominance and skyline-style comparison problems frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests sorting strategies, greedy thinking, and handling multi-dimensional comparisons efficiently.

Q: What data structure is used in The Number of Weak Characters in the Game?

The most efficient approach primarily relies on array sorting and a running maximum variable. Alternative implementations may use ordered maps or balanced binary search trees such as TreeMap to track defenses and perform dominance queries in O(log n) time.

Q: What is the time complexity of The Number of Weak Characters in the Game?

The optimal solution runs in O(n log n) time because the characters must be sorted by attack. After sorting, the algorithm performs a single linear scan to compare defenses. The extra space usage can be O(1) if sorting is done in place.

MediumArray Stack Greedy Sorting10 min readAsked at: Google

Practice this problem

Problem Statement

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] = [attack_i, defense_i] represents the properties of the i^th 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 attack_j > attack_i and defense_j > defense_i.

Return the number of weak characters.

Example 1:

Input: properties = [[5,5],[6,3],[3,6]]
Output: 0
Explanation: No character has strictly greater attack and defense than the other.

Example 2:

Input: properties = [[2,2],[3,3]]
Output: 1
Explanation: 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
Explanation: The third character is weak because the second character has a strictly greater attack and defense.

Constraints:

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

Approach Overview

Problem Overview: Each character has two attributes: attack and defense. A character is considered weak if another character exists with both strictly higher attack and defense. The task is to count how many such weak characters appear in the input array.

Approach 1: Sort and Track Maximum Defense (O(n log n) time, O(1) space)

This is the standard greedy solution using sorting. First sort characters by attack in descending order. When attacks are equal, sort by defense in ascending order. This ordering prevents characters with the same attack from incorrectly marking each other as weak. After sorting, iterate through the list while tracking the maximum defense seen so far. If the current character's defense is less than this maximum, a previously processed character already has both higher attack and higher defense, so the current one is weak. Otherwise update the maximum defense. The key insight: sorting ensures that every previously visited character already has greater or equal attack, so only the defense comparison remains. This combines greedy reasoning with ordering to reduce the problem to a single pass.

Approach 2: Balanced Binary Search Tree (O(n log n) time, O(n) space)

Another method maintains a structure that allows fast queries for stronger defenses among higher attacks. First group characters by attack value and process attacks in descending order. While iterating groups, store defenses of previously processed higher-attack characters inside a balanced BST (such as TreeMap in Java). For each character, query whether a stored defense greater than the current defense exists. If it does, the character is weak. After finishing a group, insert its defenses into the tree so equal-attack characters do not affect each other. Each lookup and insertion costs O(log n). This approach demonstrates how ordered structures help with dominance queries and is closely related to patterns used in monotonic stack or skyline-style problems.

Recommended for interviews: The sorting + maximum defense scan is what interviewers usually expect. It reduces a 2D comparison problem into a sorted linear pass and keeps the implementation simple. Mentioning the BST approach shows understanding of dominance queries, but the greedy sorted traversal is the cleanest and most common solution.

Approach 1: Sort and Track Maximum Defense

Sort characters by attack in descending order, and by defense in ascending order if attacks are equal. This sorting allows us to easily track the maximum defense for higher attacks. Iterate through the list, and use a variable to keep track of the maximum defense encountered. If a character's defense is less than this maximum, it's considered weak.

The code first sorts the properties array using a lambda function. It sorts the attacks in descending order and defenses in ascending order. Then, it initializes two variables: max_defense to track the maximum defense seen so far, and weak_count to count the weak characters. It iterates over the characters, updating max_defense and counting weak characters.

Code

Python C

Python

Complexity

Time complexity: O(n log n) due to sorting.
Space complexity: O(1) as we're sorting in place.

Try this approach in the editor →

Approach 2: Use a Balanced Binary Search Tree

Another approach is to use a balanced binary search tree to dynamically keep track of the best defenses for each attack level. As you process each character, you can efficiently query and update this data structure to determine if a character is weak.

The Java solution follows a similar logic where sorting is employed, and then iteration through sorted properties to determine weakness. The sorting is done using a lambda in Java, benefiting from the ordered traversal to compare defenses.

Code

Java JavaScript

Java

JavaScript

Complexity

Time complexity: O(n log n) because of sorting.
Space complexity: O(1), with the in-place sort.

Try this approach in the editor →

Approach 3: Sorting + Traversal

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

Then, traverse all characters. For the current character, if its defense power is less than the previous maximum defense power, it is a weak character, and we increment the answer by one. Otherwise, update the maximum defense power.

After the traversal, we get the answer.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of characters.

Code

Python Java C++Go TypeScript JavaScript

Python

Java

C++

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Sort and Track Maximum Defense	Time complexity: O(n log n) due to sorting. Space complexity: O(1) as we're sorting in place.
Use a Balanced Binary Search Tree	Time complexity: O(n log n) because of sorting. Space complexity: O(1), with the in-place sort.
Sorting + Traversal	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Sort and Track Maximum Defense	O(n log n)	O(1)	Best general solution. Simple greedy pass after sorting.
Balanced Binary Search Tree	O(n log n)	O(n)	Useful when maintaining dynamic dominance queries across groups.

Video Solution

1996. The Number of Weak Characters in the Game • Tech Adora by Nivedita • 4,783 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is The Number of Weak Characters in the Game easy or hard?

The problem is rated Medium because it requires recognizing how sorting order prevents false comparisons between characters with equal attack. Once the ordering trick is understood, the implementation becomes a straightforward greedy scan.

The Number of Weak Characters in the Game Python/Java solution

In Python, the typical implementation sorts the list of pairs and iterates while tracking the maximum defense. In Java, the same strategy works with Arrays.sort and a linear pass. Another Java approach uses TreeMap as a balanced BST to track higher defenses.

How to solve The Number of Weak Characters in the Game in O(n)?

A pure O(n) solution is generally not practical because the problem requires ordering characters by attack to compare dominance relationships. Sorting creates the correct processing order, which leads to the common O(n log n) greedy solution. After sorting, the detection step itself is O(n).

What is the best approach for The Number of Weak Characters in the Game?

The most common solution sorts characters by attack descending and defense ascending, then scans while tracking the maximum defense seen so far. If a character's defense is lower than the current maximum, it is weak. This greedy strategy runs in O(n log n) time due to sorting and O(1) extra space.

Is The Number of Weak Characters in the Game asked at Google/Amazon/Meta?

Variants of dominance and skyline-style comparison problems frequently appear in interviews at companies like Amazon, Google, and Meta. The problem tests sorting strategies, greedy thinking, and handling multi-dimensional comparisons efficiently.

What data structure is used in The Number of Weak Characters in the Game?

The most efficient approach primarily relies on array sorting and a running maximum variable. Alternative implementations may use ordered maps or balanced binary search trees such as TreeMap to track defenses and perform dominance queries in O(log n) time.

What is the time complexity of The Number of Weak Characters in the Game?

The optimal solution runs in O(n log n) time because the characters must be sorted by attack. After sorting, the algorithm performs a single linear scan to compare defenses. The extra space usage can be O(1) if sorting is done in place.

Ready to solve this problem?

Practice The Number of Weak Characters in the Game with our built-in code editor and test cases.

Practice on FleetCode

Maximum Height by Stacking Cuboids

Russian Doll Envelopes

Problem Info

DifficultyMedium

Acceptance44.7%

Approaches3

Reading time10 min

Asked at

Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Sort and Track Maximum Defense

Code

Complexity

Approach 2: Use a Balanced Binary Search Tree

Code

Complexity

Approach 3: Sorting + Traversal

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents