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 &gt; attacki and defensej &gt; defensei.

Return the number of weak characters.

&nbsp;
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.


&nbsp;
Constraints:


	2 &lt;= properties.length &lt;= 105
	properties[i].length == 2
	1 &lt;= attacki, defensei &lt;= 105


class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:

        properties.sort(key=lambda x: (-x[0],x[1]))

        ans = 0
        curr_max = 0

        for _, d in properties:
            if d < curr_max:
                ans += 1
            else:
                curr_max = d
        return ans
class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        int[] maxH = new int[100002];
        int count = 0;
        for(int[] point:properties){
            maxH[point[0]] = Math.max(point[1],maxH[point[0]]);
        }
        for(int i=100000;i>=0;i--){
            maxH[i] = Math.max(maxH[i+1],maxH[i]);
        }

        for(int[] point:properties){
            if(point[1]<maxH[point[0]+1])
                count++;
        }
        return count;
    }
}
class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] != b[0]) return a[0] > b[0];
        return a[1] < b[1];
    }
    
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        sort(properties.begin(), properties.end(), cmp);

        int res = 0, mx = INT_MIN;
        for (auto p : properties) {
            if (mx > p[1]) res++;
            else mx = p[1];
        }
        return res;
    }
};
 var numberOfWeakCharacters = function(properties) {
    // sort strongest to weakest
    properties.sort((a, b) => {
        if (b[0] - a[0]) {
            return b[0] - a[0];
        }
        return b[1] - a[1];
    });

    // map all the unique index 0 values to a (descending)
    // sorted array
    const uniqueZeroIndexToOneIndex = new Map();
    for (const [a, b] of properties) {
        if (!uniqueZeroIndexToOneIndex.has(a)) {
            uniqueZeroIndexToOneIndex.set(a, []);
        }
        uniqueZeroIndexToOneIndex.get(a).push(b);
    }

    // get all the unique index 0 values
    const nums = [...uniqueZeroIndexToOneIndex.keys()];

    let maxValue = -1;
    let numWeakCharacters = 0;
    for (let i = 0; i < nums.length; i++) {
        // skip key in case if we deleted the key
        if (!uniqueZeroIndexToOneIndex.has(nums[i])) continue;

        const maxValOfI = uniqueZeroIndexToOneIndex.get(nums[i])[0];
        if (maxValOfI <= maxValue) continue;
        maxValue = maxValOfI;

        for (let j = i + 1; j < nums.length; j++) {
            // skip key in case if we deleted the key
            if (!uniqueZeroIndexToOneIndex.has(nums[j])) continue;

            // valuesOfJ will be sorted in descending order
            const valuesOfJ = uniqueZeroIndexToOneIndex.get(nums[j])

            // pop off all the weak values and add to numWeakCharacters
            for (let k = valuesOfJ.length - 1; k >= 0; k--) {
                if (maxValue > valuesOfJ[k]) {
                    valuesOfJ.pop();
                    numWeakCharacters++;
                } else {
                    // we won't be able to find any more weak characters
                    // in valuesOfJ
                    break;
                }
            }
            if (valuesOfJ.length === 0) {
                // delete the key if all the values were weak characters
                uniqueZeroIndexToOneIndex.delete(nums[j]);
            } else {
                // if there is a stronger character updated it so we can
                // eliminate more characters
                maxValue = Math.max(valuesOfJ[0], maxValue);
            }
        }
    }
    return numWeakCharacters;
};
The Number of Weak Characters in the Game