LC 1996

Solution to LeetCode 1996 The Number of Weak Characters in the Game.

LeetCode 1996

The Number of Weak Characters in the Game (Median). [link]

1] Sort the ‘attack’ in descending order and the ‘defense’ in ascending order. Along the array, there are smaller ‘attack’. If there are also smaller ‘defense’, then count += 1. Note that for each group of same ‘attack’, ‘defense’ is ascending - this avoid counting same ‘attack’ different ‘defense’.

Time complexity O(N log N) (O(N log N) for sorting and O(N) for iterating the array). Space complexity O(logN) for sorting.

class Solution(object):
    def numberOfWeakCharacters(self, properties):
        """
        :type properties: List[List[int]]
        :rtype: int
        """
        # descending attack, ascending defense
        properties.sort(key = lambda x: (-x[0], x[1]))
        
        count, MAX = 0, 0
        
        for _, defense in properties:
            # the attack must be smaller, check whether defense is smaller too
            if MAX > defense: 
                count += 1
            else:
                MAX = max(MAX, defense)
                
        return count

2] Use a stack storing ‘defense’ in descending order. Sort the ‘properties’ by ‘attack’ in ascending order and ‘defense’ in descending order. Along the array, there are larger ‘attack’. If there are also larger ‘defense’, then count += 1. Note that for each group of same ‘attack’, ‘defense’ is descending - this avoid counting same ‘attack’ different ‘defense’.

Time complexity O(N log N) (Sorting takes O(N log N). Iteration takes O(N)). Space complexity O(N) for stack to store numbers.

class Solution(object):
    def numberOfWeakCharacters(self, properties):
        """
        :type properties: List[List[int]]
        :rtype: int
        """
        # ascending attack, descending defense
        properties.sort(key = lambda x: (x[0], -x[1]))
        
        count = 0
        stack = [] # descending order
        
        for _, defense in properties:
            while stack and stack[-1] < defense:
                stack.pop()
                count += 1
            stack.append(defense)
        return count