LeetCode: 1996. The Number of Weak Characters in the Game

I found this problem is pretty similar to 'Russian Doll' prob (https://leetcode.com/problems/russian-doll-envelopes/).

Thought process for this problem is:

0> Sort the properties.

1> Let's just assume that attack strictly increases (e.g. 3, 4, 5, ...):
then what we should do is to count how many defense values have larger values on their right side.
And that's exactly what monotonicly desc stack does.

2> Now handle the cases with the same attacks (e.g. (3, 3), (3, 4)):
our logic would return 1 in [(3, 3), (3, 4)]
we can easily tweak the logic by changing the order of the array to [(3, 4), (3, 3)].
with the order, our logic would return 0.

 

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        properties.sort(key=lambda x: (x[0], -x[1]))
        ret = 0
        # monotonicly desc stack
        stack = []
        for a, d in properties:
            while stack and stack[-1] < d:
                stack.pop()
                ret += 1
            stack.append(d)
        return ret