# The Number of Weak Characters in the Game LeetCode Solution

Difficulty Level Medium
tiktokViews 1788

## Problem Statement:

The Number of Weak Characters in the Game LeetCode Solution : 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.

## Examples:

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.`

## Approach:

### Idea:

We can solve the problem with the help of sorting. Firstly, we will sort the array based on decreasing `attack` value. For those elements having equal attack values, we will sort them based on increasing `defense` value. Then we will iterate over the entire array and will keep track of the max defense value `maxDefense`. We will mark all those elements as weak which will have a defense value less than `maxDefense`.

This problem is the combination of greedy and sort strategies. Let us consider the following example: `[[6, 9], [7, 5], [7, 9], [7, 10], [10, 4], [10, 7]]`.

1. The first step is to sort data, in this way we can be sure that for the first value we always have `<= value`. However we are not happy with `=`, we want to take only `<`.
2. So, we split data into groups: `[9], [5, 9, 10], [4, 7]` for the second parameter and process group by group.
3. We keep current `max_y` as the maximum value for the second parameter. In the beginning, it is `-1`. When we are done with the last group, it becomes equal to `7,` then it is equal to `10` and then again `10`.
4. Each time we check the condition `q < max_y`. We are already sure that for the first parameter we have `<` inequality, by this, we check if we are good for the second one.

### Code:

The Number of Weak Characters in the Game C++ Solution:

```class Solution {
public:
static bool comp(vector<int> &e1,vector<int> &e2){
if(e1[0]==e2[0]){
return e1[1]<e2[1];
}
return e1[0]>e2[0];

}
int numberOfWeakCharacters(vector<vector<int>>& properties) {
sort(properties.begin(),properties.end(),comp);
int ans = 0;
int defenseMax = 0;
for(auto it:properties){
if(it[1]<defenseMax)
ans++;
else
defenseMax = it[1];
}
return ans;
}
};```

Translate »