The Number of Weak Characters in the Game LeetCode Solution

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

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