Outclassed Heroes

Medium

Every hero in a game has two stats: attack and defense. You get an array heroes where heroes[i] = [attack, defense] describes hero i. A hero is outclassed if some other hero has both a strictly higher attack and a strictly higher defense. Being ahead on just one stat is not enough. Return the number of outclassed heroes.

Example 1

heroes=[[4, 7], [2, 3], [5, 2], [3, 6]] → 2

Hero [4, 7] beats both [2, 3] and [3, 6] on both stats. [5, 2] has the highest attack, and nobody has more defense than [4, 7]. So the answer is 2.

Example 2

heroes=[[3, 3], [3, 5], [2, 4]] → 1

[2, 4] loses to [3, 5]. The two heroes with attack 3 do not outclass each other: both stats must be strictly higher.

Constraints

2 ≤ len(heroes) ≤ 10⁵
len(heroes[i]) == 2
1 ≤ attack, defense ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Greedy Array Sorting Monotonic Stack

Similar problems

Fix the Middle of the Line Medium Most Pieces Sorted Separately Medium Sorting Batches With Repeats Hard Convoys at the Finish Medium Tree of Leaf Products Medium

Input

heroes=[[4, 7], [2, 3], [5, 2], [3, 6]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 101 tests on the server, hidden ones included.