<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:
        
        # [6, 3], [3, 6]. [5, 5]

        # [2, 2], [3, 3]

        # [2, 3], [3, 4], [4, 4]

        # o(n) search for player with highest attack and highest defense 
        # maxAttack = [0, 0]
        # maxDefense = [0, 0]

        # for character in properties:
        #     if character[0] == maxAttack[0] and character[1] > maxAttack[1]:
        #         maxAttack = character 
        #     elif character[0] > maxAttack[0]:
        #         maxAttack = character
            
        #     if character[1] == maxDefense[1] and character[0] > maxDefense[0]:
        #         maxDefense = character 
        #     if character[1] > maxDefense[1]:
        #         maxDefense = character

        # print(maxAttack, maxDefense)

      
        # # another linear search to counting how many characters have less than highest attack adn less than highest defense
        # res = 0
        # for character in properties:
        #     if (character[0] < maxAttack[0] and character[1] < maxAttack[1])  or (character[1] < maxDefense[1] and character[0] < maxDefense[0]):
        #         res += 1

        # return res


        maxAttack = 0

        for character in properties:
            maxAttack = max(maxAttack, character[0])

        maxDefense = [0 for _ in range(maxAttack + 2)]

        for attack, defense in properties:
            maxDefense[attack] = max(maxDefense[attack], defense)

        for i in range(len(maxDefense) - 2, -1, -1):
            maxDefense[i] = max(maxDefense[i], maxDefense[i + 1])

        res = 0
        for attack, defense in properties:
            if maxDefense[attack + 1] > defense:
                res += 1

        print(maxDefense)
        return res
1008