1996. The Number of Weak Characters in the Game LeetCode Solution

In this guide, you will get 1996. The Number of Weak Characters in the Game LeetCode Solution with the best time and space complexity. The solution to The Number of Weak Characters in the Game problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
The Number of Weak Characters in the Game solution in C++
The Number of Weak Characters in the Game solution in Java
The Number of Weak Characters in the Game solution in Python
Additional Resources

1996. The Number of Weak Characters in the Game LeetCode Solution image

Problem Statement of The Number of Weak Characters in the Game

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] = [attacki, defensei] represents the properties of the ith 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 attackj > attacki and defensej > defensei.
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 <= 105
properties[i].length == 2
1 <= attacki, defensei <= 105

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

1996. The Number of Weak Characters in the Game LeetCode Solution in C++

class Solution {
 public:
  int numberOfWeakCharacters(vector<vector<int>>& properties) {
    // Sort properties by `attack` in descending order, then by `defense` in
    // ascending order.
    ranges::sort(properties, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });

    int ans = 0;
    int maxDefense = 0;

    for (const vector<int>& property : properties) {
      const int defense = property[1];
      if (defense < maxDefense)
        ++ans;
      maxDefense = max(maxDefense, defense);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1996. The Number of Weak Characters in the Game LeetCode Solution in Java

class Solution {
  public int numberOfWeakCharacters(int[][] properties) {
    // Sort properties by `attack` in descending order, then by `defense` in
    // ascending order.
    Arrays.sort(properties,
                (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]));

    int ans = 0;
    int maxDefense = 0;

    for (int[] property : properties) {
      final int defense = property[1];
      if (defense < maxDefense)
        ++ans;
      maxDefense = Math.max(maxDefense, defense);
    }

    return ans;
  }
}
// code provided by PROGIEZ

1996. The Number of Weak Characters in the Game LeetCode Solution in Python

class Solution:
  def numberOfWeakCharacters(self, properties: list[list[int]]) -> int:
    ans = 0
    maxDefense = 0

    # Sort properties by `attack` in descending order, then by `defense` in
    # ascending order.
    for _, defense in sorted(properties, key=lambda x: (-x[0], x[1])):
      if defense < maxDefense:
        ans += 1
      maxDefense = max(maxDefense, defense)

    return ans
 # code by PROGIEZ