Table of Contents

## 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]]`

.

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

. - So, we split data into groups:
`[9], [5, 9, 10], [4, 7]`

for the second parameter and process group by group. - 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`

. - 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; } };

## Complexity Analysis of The Number of Weak Characters in the Game LeetCode Solution:

**Time Complexity:**The time complexity of the above code is**O(nlogn)**.**Space Complexity:**The space complexity of the above code is**O(n)**.