The Number of Weak Characters in the Game

Medium

Asked by:

29 views

Topics:

ArraysGreedy Algorithms

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⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the attack and defense values of a character?
Can the input array be empty or contain null values?
If multiple characters have the same attack value, how should their defense values be compared when determining weakness?
If no characters are weak, should I return 0?
Are the attack and defense values guaranteed to be integers?

Brute Force Solution

Approach

We want to find out how many characters are weak based on the attack and defense values of other characters. The brute force strategy involves checking each character against every other character to see if it's weak.

Here's how the algorithm would work step-by-step:

Take the first character in the list.
Compare this character's attack and defense with the attack and defense of every other character in the list.
If you find another character whose attack and defense are both greater than the first character's, then the first character is weak. Count it.
Repeat this process for every character in the list.
After checking every character against all the others, the final count will tell you how many weak characters there are in total.

Code Implementation

def number_of_weak_characters(character_properties):
    weak_character_count = 0

    # Iterate through each character to determine if it's weak
    for i in range(len(character_properties)):
        is_weak = False
        for j in range(len(character_properties)):
            # Skip comparing the character to itself
            if i == j:
                continue

            # Determine if another character is stronger
            if character_properties[j][0] > character_properties[i][0] and \
               character_properties[j][1] > character_properties[i][1]:

                # Found a stronger character, mark as weak
                is_weak = True
                break

        # Increment count if character is weak
        if is_weak:
            weak_character_count += 1

    return weak_character_count

Big(O) Analysis

Time Complexity

O(n²) – The provided solution iterates through each character in the list of size n. For each character, it compares its attack and defense values with the attack and defense values of every other character in the list, resulting in another iteration of size n. This nested iteration leads to n comparisons for each of the n characters. Therefore, the total number of operations is proportional to n * n, which simplifies to O(n²).

Space Complexity

O(1) – The brute force strategy described involves iterating through the list of characters and comparing each character's attack and defense values with every other character. No auxiliary data structures like lists, hash maps, or trees are created to store temporary data. The algorithm only uses a few constant space variables for loop indices and comparison results. Therefore, the space complexity remains constant irrespective of the number of characters, N, in the input list.

Optimal Solution

Approach

To efficiently find weak characters, we first organize all characters based on their attack strength. Then, by iterating through them, we can determine weakness based solely on defense without redundant checks.

Here's how the algorithm would work step-by-step:

First, sort all the characters based on their attack strength. Characters with stronger attacks should come earlier in the sorted order.
If there are characters with the same attack strength, sort them further based on their defense strength, but this time in decreasing order. This puts the stronger defenders earlier in the sequence among those with identical attack.
Now, go through the sorted list from the end to the beginning. Keep track of the highest defense you've seen so far as you move backwards.
For each character, check if its defense is lower than the highest defense you've seen so far. If it is, then that character is considered weak, because there's a character with a higher defense and a higher or equal attack.
Count all the characters that are weak according to the previous step. The final count is the number of weak characters.

Code Implementation

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

    weak_character_count = 0
    maximum_defense_so_far = 0

    # Iterate backwards to track max defense
    for attack, defense in reversed(properties):

        # If current defense is less than the max, it's a weak character
        if defense < maximum_defense_so_far:
            weak_character_count += 1

        # Update the maximum defense
        maximum_defense_so_far = max(maximum_defense_so_far, defense)

    return weak_character_count

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is the sorting of the characters array, which takes O(n log n) time using efficient sorting algorithms like merge sort or quicksort. The subsequent iteration through the sorted array to find weak characters takes O(n) time. Since O(n log n) grows faster than O(n), the overall time complexity is determined by the sorting step. Therefore, the time complexity of the algorithm is O(n log n).

Space Complexity

O(1) – The algorithm sorts the input array in place, so it doesn't create a new array of size N. It only uses a constant amount of extra space for variables like the 'highest defense seen so far' and the 'count of weak characters'. Therefore, the space complexity remains constant, regardless of the number of characters, N.

Edge Cases

Case	How to Handle
Empty properties array	Return 0 immediately as there are no characters to compare.
Single character in properties array	Return 0 immediately as a weak character needs another character for comparison.
Properties array with all characters having identical attack and defense	No character will be weak because no other character has strictly greater attack and defense; return 0.
Large properties array leading to potential time-out issues	Sorting the array by attack and iterating to find weak characters will handle it with O(n log n) time complexity.
Integer overflow if attack or defense values are very large	Use appropriate data types (e.g., long) to prevent integer overflow during comparisons.
Properties array with attack values in descending order, defense values in ascending order	The last element would be weak by definition, and we account for this during comparisons.
Attack or defense values can be zero	The comparison logic (strictly greater) handles zero values correctly.
Duplicate characters with identical attack and defense	The algorithm only counts the number of weak characters according to given critera.

Empty properties array

How to Handle:

Return 0 immediately as there are no characters to compare.

Single character in properties array

How to Handle:

Return 0 immediately as a weak character needs another character for comparison.

Properties array with all characters having identical attack and defense

How to Handle:

No character will be weak because no other character has strictly greater attack and defense; return 0.

Large properties array leading to potential time-out issues

How to Handle:

Sorting the array by attack and iterating to find weak characters will handle it with O(n log n) time complexity.

Integer overflow if attack or defense values are very large

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during comparisons.

Properties array with attack values in descending order, defense values in ascending order

How to Handle:

The last element would be weak by definition, and we account for this during comparisons.

Attack or defense values can be zero

How to Handle:

The comparison logic (strictly greater) handles zero values correctly.

Duplicate characters with identical attack and defense

How to Handle:

The algorithm only counts the number of weak characters according to given critera.