Problem statement

https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/

Solution

This problem is comination of greedy and sort strategies. Let us consider the following example: [[6, 9], [7, 5], [7, 9], [7, 10], [10, 4], [10, 7]].

  1. 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 is the maximum value for the second parameter. In the beginning it is -1. When we done with last group, it becomes equal to 7, then it is equal to 10 and then again 10.
  4. Each time we check condition q < max_y. We already sure that for the first parameter we have < inequality, by this we check if we are good for the second one.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def numberOfWeakCharacters(self, X):
        X = sorted(X)
        n = len(X)
        ans, d, max_y = 0, defaultdict(list), -1
 
        for a, b in X:
            d[a] += [b]
            
        for t in sorted(list(d.keys()))[::-1]:
            for q in d[t]:
                if q < max_y: ans += 1
            for q in d[t]:
                max_y = max(max_y, q)
                
        return ans