We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Number of Weak Characters in the Game

Number: 2123

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of characters represented by their attack and defense properties, determine the number of characters that are "weak." A character is weak if there exists another character with both a strictly greater attack and a strictly greater defense property.

Key Insights

  • Sort the characters in descending order by attack. For characters with the same attack value, sort them in ascending order by defense.
  • Iterate through the sorted list while tracking the maximum defense seen so far.
  • A character is weak if its defense is less than the current maximum defense.
  • Sorting by attack in descending order ensures that when comparing, no future character has a higher attack.
  • Sorting by defense in ascending order (for equal attack values) prevents incorrectly marking characters as weak when their attack values are the same.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) for the space used by the sorting algorithm (depending on the language implementation) and additional variables.

Solution

The solution leverages a greedy sorting approach:

  1. Sort the characters such that characters with higher attack come first, and if attacks are equal, order them by increasing defense.
  2. Initialize a variable, maxDefense, to 0. This variable keeps track of the highest defense value encountered while iterating.
  3. Iterate through the sorted array and for each character:
    • If the current character's defense is less than maxDefense, it is weak because a character with a higher attack (due to sorting) and a higher defense exists.
    • Otherwise, update maxDefense with the current character's defense. This process ensures each character is checked exactly once following the sorted order, thus meeting the required performance constraints.

Code Solutions

# Python solution with line-by-line comments
def numberOfWeakCharacters(properties):
    # Sort properties by descending attack and ascending defense for equal attacks
    properties.sort(key=lambda x: (-x[0], x[1]))
    
    max_defense = 0  # Track max defense seen so far
    weak_count = 0   # Count of weak characters
    
    # Iterate over each character in the sorted list
    for attack, defense in properties:
        # If current defense is less than the maximum defense seen, it's a weak character
        if defense < max_defense:
            weak_count += 1
        else:
            # Otherwise, update max_defense if current defense is higher
            max_defense = defense
    
    return weak_count

# Example usage:
properties = [[1,5],[10,4],[4,3]]
print(numberOfWeakCharacters(properties))  # Expected output: 1
← Back to All Questions