The Number Of Weak Characters In The Game - Leetcode Solution

Problem Statement:

You are playing a game that contains n characters, each with two attributes: attack and defense. In this game, a character is considered weak if any other character has both strictly greater attack and defense. More formally, a character i is weak if there exists another character j satisfying all of these conditions:

j != i attack_j > attack_i defense_j > defense_i Return the number of weak characters.

Example:

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

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.

Approach:

The problem asks us to find the number of weak characters in the given game, which means we have to compare each character with all other characters and check if any other character has strictly greater attack and defense than the current character.

To solve the problem, we will iterate through each character and compare it with all other characters. If any character satisfies the condition, we will increment our count.

Algorithm:

1. Initialize a counter variable count to 0.
2. Iterate the properties list using the i index and compare it with all other characters.
3. Iterate the properties list using the j index.
4. If the attack and defense values of the current character j are greater than the attack and defense values of the character i, then increment the count and break out of the inner loop.
5. Return the count.

Code:

Here is the Python code to solve the problem:

class Solution: def numberOfWeakCharacters(self, properties: List[List[int]]) -> int: n = len(properties) count = 0 for i in range(n): for j in range(n): if i != j and properties[j][0] > properties[i][0] and properties[j][1] > properties[i][1]: count += 1 break return count

Time Complexity:

The time complexity of the above algorithm is O(n^2), where n is the number of characters in the game.

Space Complexity:

The space complexity of the above algorithm is O(1), as we don't use any extra space other than the variables needed for comparison and counting.

1