The Number of Weak Characters in the Game

The Number of Weak Characters in the Game

What is this problem about?

Imagine a video game where characters have two primary attributes: attack and defense. A character is considered "weak" if there exists another character in the game who has both strictly greater attack and strictly greater defense. Given a list of characters with their attributes, your task is to count how many characters are weak.

Why is this asked in interviews?

This the Number of Weak Characters in the Game interview question is a popular challenge at Pinterest and Google. It tests your ability to optimize a comparison-heavy problem. A naive O(n^2) approach checking every pair of characters is too slow for large inputs. The problem evaluates your understanding of sorting and greedy strategies, specifically how to arrange data so that a single pass can identify all weak elements.

Algorithmic pattern used

This problem utilizes the Array, Monotonic Stack, Sorting, Stack, Greedy interview pattern.

1. Sort the characters by attack in descending order.
2. For characters with the same attack, sort them by defense in ascending order. This is the crucial trick: it ensures that when we process a character, any previously seen character with a larger attack has a defense that we can safely compare against.
3. Iterate through the sorted characters while maintaining the maximum defense seen so far.
4. If a character's defense is strictly less than the maximum defense seen from characters with a higher attack, that character is weak.
5. Because we sorted defenses in ascending order for the same attack, we won't accidentally mark a character as weak because of another character with the same attack.

Example explanation

Characters: [[5, 5], [6, 3], [3, 6]].

1. Sort by Attack (desc), then Defense (asc):
   • [6, 3]
   • [5, 5]
   • [3, 6]
2. Processing:
   • [6, 3]: Max Defense = 3. Count = 0.
   • [5, 5]: 5 > 3. Max Defense becomes 5. (Not weak because 5 is not < 3).
   • [3, 6]: 6 > 5. Max Defense becomes 6. (Not weak). Wait, if we had [[5, 5], [6, 7], [3, 6]]:
3. Sorted: [6, 7], [5, 5], [3, 6].
4. [6, 7]: Max = 7.
5. [5, 5]: 5 < 7. Count = 1 (Weak!).
6. [3, 6]: 6 < 7. Count = 2 (Weak!).

Common mistakes candidates make

The most common mistake in "The Number of Weak Characters in the Game coding problem" is sorting both attributes in the same direction (both descending). This makes it difficult to handle characters with the same attack. Another mistake is failing to realize that "strictly greater" applies to both attributes, which is why the sorting trick for equal attacks is so important.

Interview preparation tip

Sorting is often the first step in optimizing a search or comparison problem. When a problem has two attributes, try sorting by one and observing the behavior of the other. The "descending/ascending" sort combination is a powerful pattern for problems involving 2D dominance.