<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>

"""
input: 2d array properties, properties[i] = [attack_i, defense_i]
output: number of weak characters

character is weak iff both attack and defense are less than anothers
 - defense_i < defense_j, attack_i >= attack_j
 - defense_i >= defense_j, attack_i < defense_j

Brute force: compare character to every other O(n^2)

[[5,5],[6,3],[3,6]] -> [[3,6],[5,5],[6,2],[6,3]]

sort characters in ascending order of attack, then descending order of defense
iterating from back to front (starting at highest attack level group)
keep track of max defense
if any characters have smaller defense, is a weak character

keep track of max defense for each attack level group
if higher attack level has higher defense, then the lower attack levels defense threshold should be the same
"""

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        # keep track of max defense for each attack level group
        max_attack = 0

        for character in properties:
            attack, _ = character
            max_attack = max(max_attack, attack)

        attack_levels = [0] * (max_attack + 1)

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

        # if higher attack level has higher defense, then the lower attack levels defense threshold should be the same
        for i in range(max_attack - 1, -1, -1):
            attack_levels[i] = max(attack_levels[i], attack_levels[i + 1])

        # count weak characters
        weak = 0

        for character in properties:
            attack, defense = character
            if attack < max_attack and attack_levels[attack + 1] > defense:
                weak += 1

        return weak
810