<p>You are playing a game that contains multiple characters, and each of the characters has <strong>two</strong> main properties: <strong>attack</strong> and <strong>defense</strong>. You are given a 2D integer array <code>properties</code> where <code>properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>]</code> represents the properties of the <code>i<sup>th</sup></code> character in the game.</p>

<p>A character is said to be <strong>weak</strong> if any other character has <strong>both</strong> attack and defense levels <strong>strictly greater</strong> than this character&#39;s attack and defense levels. More formally, a character <code>i</code> is said to be <strong>weak</strong> if there exists another character <code>j</code> where <code>attack<sub>j</sub> &gt; attack<sub>i</sub></code> and <code>defense<sub>j</sub> &gt; defense<sub>i</sub></code>.</p>

<p>Return <em>the number of <strong>weak</strong> characters</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> properties = [[5,5],[6,3],[3,6]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> No character has strictly greater attack and defense than the other.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> properties = [[2,2],[3,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The first character is weak because the second character has a strictly greater attack and defense.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> properties = [[1,5],[10,4],[4,3]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The third character is weak because the second character has a strictly greater attack and defense.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= properties.length &lt;= 10<sup>5</sup></code></li>
	<li><code>properties[i].length == 2</code></li>
	<li><code>1 &lt;= attack<sub>i</sub>, defense<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        # properties.sort(key= lambda p: (p[0], -1*p[1]))
        # result = 0
        # prev = -1
        # attack_groups = []
        # for p in properties:
        #     if prev == p[0]:
        #         attack_groups[-1].append(p[1])
        #     else:
        #         attack_groups.append([p[1]])
        #         prev = p[0]
        # if len(attack_groups) < 2:
        #     return 0

        # # stack = attack_groups[0].copy()
        # # for i in range(1, len(attack_groups)):

        # #     while stack:
        # #         if abs(attack_groups[i][0]) > abs(stack[-1]):
        # #             stack.pop()
        # #             result+=1
        # #         else:
        # #             break

        # #     stack.extend(attack_groups[i])
            
        # # no stack solution, go from highest attack and highest defense, go down
        # print(attack_groups)
        # max_def = attack_groups[-1][0]
        # for i in range(len(attack_groups)-2, -1, -1):
        #     for j in range(len(attack_groups[i])-1, -1, -1):
        #         if max_def > attack_groups[i][j]:
        #             result+=1
        #         max_def = max(max_def, attack_groups[i][j])
        # return result


        # linear greedy
        # 1. find max def for every attack  
        max_attack = max(x[0] for x in properties)
        max_defs = [0] * (max_attack+2)
        for p in properties:
            max_defs[p[0]] = max(max_defs[p[0]], p[1])
        
        max_so_far = 0
        for i in range(len(max_defs)-1, 0, -1):
            max_so_far = max_defs[i] = max(max_so_far, max_defs[i])
        
        # print(max_defs)
        res = 0
        for p in properties:
            if p[0] == max_attack:
                continue
            if max_defs[p[0]+1] > p[1]:
                res +=1
        return res





            

            
666