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.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. The Number of Weak Characters in the Game solution in C++
  4. The Number of Weak Characters in the Game solution in Java
  5. The Number of Weak Characters in the Game solution in Python
  6. 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.

See also  878. Nth Magical Number LeetCode Solution

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

Additional Resources

See also  2447. Number of Subarrays With GCD Equal to K LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.