1996. The Number of Weak Characters in the Game

The Number of Weak Characters in the Game

Problem Description

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.

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

We are gonna code with and without Stack. 

Approach A) With Stack

var numberOfWeakCharacters = function(properties) {
    properties.sort(([attack1, defense1], [attack2, defense2]) => {
        if(attack1 !== attack2) return attack1 - attack2;
        return defense2 - defense1;
    });

    const stack = [];
    for(const [,defense] of properties) {
        while(stack.length > 0 && stack[stack.length - 1] < defense) {
            stack.pop();
        }

        stack.push(defense);
    }

    return properties.length - stack.length;
};

Runtime: 670 ms, faster than 20.35% of JavaScript online submissions for The Number of Weak Characters in the Game.
Memory Usage: 89.6 MB, less than 19.76% of JavaScript online submissions for The Number of Weak Characters in the Game.




Approach B) Without Stack

var numberOfWeakCharacters = function(properties) {
    let len = properties.length;
    let count = 0;
    properties.sort((a, b) => b[0] - a[0] || a[1] - b[1])
    let max = 0;
          for (let i = 0; i < len; i++) {
              if (properties[i][1] < max) {
                  count++;
             }
             max = Math.max(max, properties[i][1]);
         }
         return count;
};

Runtime: 780 ms, faster than 11.35% of JavaScript online submissions for The Number of Weak Characters in the Game.
Memory Usage: 93.1 MB, less than 17.76% of JavaScript online submissions for The Number of Weak Characters in the Game.

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/stack-javascript-part-1-15f9e6ebecd5

Conclusion

That’s all folks! In this post, we solved LeetCode problem #1996. The Number of Weak Characters in the Game

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!