1996. The Number of Weak Characters in the Game


Problem Description

In the given LeetCode problem, you are playing a game with multiple characters. Each character has two properties: attack and defense. These properties are provided in a 2D integer array properties, where properties[i] = [attack_i, defense_i] contains the properties of the i-th character. A character is considered weak if there is another character with both an attack and defense level strictly greater than that of the said character. The goal is to determine how many characters are weak according to these conditions.

Intuition

The key to solving this problem is to optimize the way we look for characters that can be dominated (or are weak compared to others). A brute-force approach of comparing every character with every other character would result in a time-consuming solution. Thus, the main challenge is to reduce the number of comparisons needed.

One effective tactic for reducing comparisons is to sort the characters in a way that allows us to easily identify the weak ones. We can do this by sorting the characters based on their attack values in descending order. If their attack values are the same, we sort based on their defense values in ascending order. This specific ordering makes sure that when we traverse the sorted array, any character we see with a higher defense value will definitely have a lower attack value (because we have sorted them in descending order), thus indicating the presence of a weak character.

The intuition behind sorting by descending attack is to ensure that when iterating over the characters, any subsequently encountered character with a lower defense is guaranteed to be weak since there cannot be a character with a higher attack preceding it.

Once the array is sorted, we initialize two variables, ans and mx. The variable ans keeps track of the number of weak characters, and mx stores the maximum defense value encountered so far. As we iterate through the properties array, we compare each character's defense value with mx. If the defense value is strictly less than mx, this character is weak, and we increment ans by one. Otherwise, we update mx with the current character's defense value if it's higher than the current mx. The final result is the value of ans, which represents the total number of weak characters found.

Learn more about Stack, Greedy, Sorting and Monotonic Stack patterns.

Solution Approach

The solution uses sorting and a one-pass scan through the sorted list of character properties to determine the weak characters.

Here's a step-by-step explanation of the algorithm:

  1. Sorting the Properties: We start by sorting the properties array based on two criteria. First, we sort by the attack value in descending order, and in case of a tie, we sort by defense value in ascending order. This can be achieved using a custom sort function:

    1properties.sort(key=lambda x: (-x[0], x[1]))

    This ensures that for any character i and j where i < j in the sorted array, attack_i >= attack_j. If attack_i == attack_j, then defense_i <= defense_j.

  2. Initialising Counters: Two variables are initialised: ans to count the number of weak characters, and mx to keep track of the maximum defense value seen so far in the iteration.

  3. Iterating Through the Sorted Properties: The array is iterated through after being sorted:

    1for _, defense in properties:
    2    ans += defense < mx
    3    mx = max(mx, defense)

    Each step of the iteration does the following:

    • If the defense of the current character is less than the maximum defense seen so far (mx), then this character is weak, and ans is incremented by 1.
    • The mx is then updated with the maximum of its current value and the defense value of the current character.
  4. Return Weak Characters Count: After the iteration is complete, the value of ans represents the total count of weak characters. It is returned as the final result of the function.

This approach uses a sorting algorithm that typically has a time complexity of O(n log n) and a scan of the sorted array with a time complexity of O(n), resulting in an overall time complexity of O(n log n) where n is the number of characters in the game.

Using a sorted list as the data structure enables an efficient single pass to determine weak characters, leveraging the sorted order to minimize the required comparisons.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example. Suppose we have the following properties array for the characters:

1properties = [[5,5],[6,3],[3,6]]

This array tells us that we have three characters:

  • Character 1 has an attack of 5 and a defense of 5.
  • Character 2 has an attack of 6 and a defense of 3.
  • Character 3 has an attack of 3 and a defense of 6.

Following through the steps of the solution:

  1. Sorting the Properties: Sort the characters so that those with higher attack values come first. In case of a tie in the attack values, the one with the lower defense value comes first. After sorting:
1properties after sorting = [[6,3], [5,5], [3,6]]

Now the list is ordered in such a way that it's easier to determine whether a character is weak without having to compare it with all other characters.

  1. Initialising Counters: Initialize ans to 0 and mx to -1 (assuming all defense values are positive).

  2. Iterating Through the Sorted Properties:

    • Character 1: Attack = 6, Defense = 3. Since mx is -1, we don't increase ans. We update mx to 3.
    • Character 2: Attack = 5, Defense = 5. Because the defense (5) is greater than mx (3), Character 2 is not weak. We update mx to 5.
    • Character 3: Attack = 3, Defense = 6. Here, the defense (6) is greater than the current mx (5), so Character 3 is also not weak. mx updates to 6.

No character's defense was strictly less than the maximum defense seen so far after them, so:

  1. Return Weak Characters Count: ans remains 0. Therefore, according to our algorithm, there are no weak characters in this example.

Solution Implementation

1from typing import List
2
3class Solution:
4    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
5        # Sort the characters in descending order of their attack value.
6        # If two characters have the same attack value, sort them in 
7        # ascending order of their defense value.
8        properties.sort(key=lambda character: (-character[0], character[1]))
9      
10        # Initialize the count of weak characters to zero.
11        weak_characters_count = 0
12      
13        # Initialize the maximum defense found so far to zero.
14        max_defense = 0
15      
16        # Iterate over the characters, which are now sorted by the rules above.
17        for _, defense in properties:
18            # If the current character's defense is less than the maximum 
19            # defense found so far, it is a weak character.
20            if defense < max_defense:
21                weak_characters_count += 1
22            else:
23                # Update the maximum defense for future comparisons.
24                max_defense = defense
25      
26        # Return the total count of weak characters.
27        return weak_characters_count
28
1class Solution {
2    public int numberOfWeakCharacters(int[][] properties) {
3        // Sorting the properties array with a custom comparator
4        // Characters are sorted by attack in descending order
5        // If attacks are equal, they're sorted by defense in ascending order
6        Arrays.sort(properties, (a, b) -> {
7            if (b[0] - a[0] == 0) {
8                return a[1] - b[1]; // Sort by defense ascending if attacks are equal
9            } else {
10                return b[0] - a[0]; // Otherwise, sort by attack descending
11            }
12        });
13
14        int countWeakCharacters = 0; // Initialize counter for weak characters
15        int maxDefense = 0; // To store the maximum defense seen so far
16      
17        // Iterate over the sorted array to count weak characters
18        for (int[] character : properties) {
19            // If the current character's defense is less than the maximum
20            // defense seen so far, it is a weak character
21            if (character[1] < maxDefense) {
22                countWeakCharacters++; // Increment weak character count
23            }
24            // Update the maximum defense seen so far
25            maxDefense = Math.max(maxDefense, character[1]);
26        }
27
28        return countWeakCharacters;  // Return the total count of weak characters
29    }
30}
31
1class Solution {
2public:
3    // This function calculates the number of weak characters in the game.
4    // A weak character is defined as one whose attack and defense are both 
5    // strictly less than another character's attack and defense.
6    // @param properties: A 2D vector where each inner vector contains the attack
7    //                    and defense values of a character.
8    // @return: The number of weak characters.
9    int numberOfWeakCharacters(vector<vector<int>>& properties) {
10        // Sort the properties in descending order by attack and if two characters have
11        // the same attack, then sort in ascending order by defense.
12        sort(properties.begin(), properties.end(), [](const auto& a, const auto& b) {
13            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
14        });
15
16        int countWeakCharacters = 0; // This variable stores the count of weak characters.
17        int maxDefense = 0; // This variable stores the maximum defense seen so far.
18
19        // Iterate through each of the characters in the sorted properties.
20        for (const auto& character : properties) {
21            // If the current character's defense is less than the maximum defense seen
22            // so far, it means that there is another character with both higher attack
23            // and defense, so the current character is weak.
24            if (character[1] < maxDefense) {
25                ++countWeakCharacters;
26            }
27            // Update the maximum defense seen so far.
28            maxDefense = max(maxDefense, character[1]);
29        }
30
31        // Return the final count of weak characters.
32        return countWeakCharacters;
33    }
34};
35
1/**
2 * Determines the number of weak characters.
3 * @param properties - A 2D array where each subarray contains the attack and defense values of a character.
4 * @returns The count of weak characters.
5 */
6function numberOfWeakCharacters(properties: number[][]): number {
7    // Sort the characters primarily by their attack in descending order,
8    // and secondarily by their defense in ascending order.
9    properties.sort((firstCharacter, secondCharacter) => (
10        firstCharacter[0] === secondCharacter[0]
11            ? firstCharacter[1] - secondCharacter[1] // Ascending defense sort if attacks are equal
12            : secondCharacter[0] - firstCharacter[0] // Descending attack sort
13    ));
14
15    // Initialize the count of weak characters and the maximum defense found so far.
16    let weakCharacterCount = 0;
17    let maxDefense = 0;
18
19    // Iterate over each character to determine if it's weak.
20    for (const [, defense] of properties) {
21        if (defense < maxDefense) {
22            // If the character's defense is less than the max defense found, it is weak.
23            weakCharacterCount++;
24        } else {
25            // Update the maximum defense seen so far if the current defense is higher.
26            maxDefense = defense;
27        }
28    }
29
30    // Return the total count of weak characters.
31    return weakCharacterCount;
32}
33

Time and Space Complexity

The time complexity of the given code is primarily governed by the sorting operation and then the single pass through the properties array. The sorting operation has a time complexity of O(n log n) where n is the number of elements in properties. The subsequent for loop is linear, providing a time complexity of O(n). Therefore, the overall time complexity is O(n log n) due to the sort being the most significant operation.

The space complexity of the code is O(1) or constant space, not counting the space used for the input and output of the function. While the sort() method itself is implemented in a way that can provide O(n) space complexity in Python's Timsort algorithm worst-case scenario, it's generally considered in-place for most practical purposes as it's a part of the language's standard functionality. Hence, beyond what is needed to store the properties list, only a fixed amount of additional space is used for variables such as ans and mx.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings