The number of weak characters in the game

Array Stack Greedy Sorting Monotonic Stack

44.5% acceptance

Feb 25, 2026

3096

100

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attacki, defensei] represents the properties of the ith character in the game. A character is said to be weak if any other character has both attack and defense levels strictly greater than this character's attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attackj > attacki and defensej > defensei. Return the number of weak characters.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_weak_characters(properties: Vec<Vec<i32>>) -> i32 {
    let mut props = properties;
    // Sort by attack descending, then by defense ascending
    // This way, when we scan left to right, characters with same attack
    // won't incorrectly count each other as weak
    props.sort_by(|a, b| {
      if a[0] != b[0] {
        b[0].cmp(&a[0])
      } else {
        a[1].cmp(&b[1])
      }
    });
    
    let mut max_defense = 0;
    let mut count = 0;
    for p in &props {
      if p[1] < max_defense {
        count += 1;
      }
      max_defense = max_defense.max(p[1]);
    }
    count
  }
}