Skip to content

1996. The Number of Weak Characters in the Game 👍

Approach 1: Sort

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int numberOfWeakCharacters(vector<vector<int>>& properties) {
    // Sort properties by `attack` in descending order, then by `defense` in
    // ascending order.
    ranges::sort(properties, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
    });

    int ans = 0;
    int maxDefense = 0;

    for (const vector<int>& property : properties) {
      const int defense = property[1];
      if (defense < maxDefense)
        ++ans;
      maxDefense = max(maxDefense, defense);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int numberOfWeakCharacters(int[][] properties) {
    // Sort properties by `attack` in descending order, then by `defense` in
    // ascending order.
    Arrays.sort(properties,
                (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]));

    int ans = 0;
    int maxDefense = 0;

    for (int[] property : properties) {
      final int defense = property[1];
      if (defense < maxDefense)
        ++ans;
      maxDefense = Math.max(maxDefense, defense);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def numberOfWeakCharacters(self, properties: list[list[int]]) -> int:
    ans = 0
    maxDefense = 0

    # Sort properties by `attack` in descending order, then by `defense` in
    # ascending order.
    for _, defense in sorted(properties, key=lambda x: (-x[0], x[1])):
      if defense < maxDefense:
        ans += 1
      maxDefense = max(maxDefense, defense)

    return ans

Approach 2: Count

  • Time: $O(|\texttt{properties}| + \max(\texttt{properties}[i][0]))$
  • Space: $O(\max(\texttt{properties[i][0]}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  int numberOfWeakCharacters(vector<vector<int>>& properties) {
    int ans = 0;
    const int maxAttack = (*ranges::max_element(
        properties, ranges::less{},
        [](const vector<int>& property) { return property[0]; }))[0];
    // maxDefenses[i] := the maximum defense for the i-th attack
    vector<int> maxDefenses(maxAttack + 2);

    for (const vector<int>& property : properties) {
      const int attack = property[0];
      const int defense = property[1];
      maxDefenses[attack] = max(maxDefenses[attack], defense);
    }

    for (int i = maxAttack; i >= 1; --i)
      maxDefenses[i] = max(maxDefenses[i], maxDefenses[i + 1]);

    for (const vector<int>& property : properties) {
      const int attack = property[0];
      const int defense = property[1];
      if (maxDefenses[attack + 1] > defense)
        ++ans;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int numberOfWeakCharacters(int[][] properties) {
    int ans = 0;
    final int maxAttack = Arrays.stream(properties).mapToInt(p -> p[0]).max().getAsInt();
    // maxDefenses[i] := the maximum defense for the i-th attack
    int[] maxDefenses = new int[maxAttack + 2];

    for (int[] property : properties) {
      final int attack = property[0];
      final int defense = property[1];
      maxDefenses[attack] = Math.max(maxDefenses[attack], defense);
    }

    for (int i = maxAttack; i >= 1; --i)
      maxDefenses[i] = Math.max(maxDefenses[i], maxDefenses[i + 1]);

    for (int[] property : properties) {
      final int attack = property[0];
      final int defense = property[1];
      if (maxDefenses[attack + 1] > defense)
        ++ans;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def numberOfWeakCharacters(self, properties: list[list[int]]) -> int:
    ans = 0
    maxAttack = max(attack for attack, _ in properties)
    # maxDefenses[i] := the maximum defense for the i-th attack
    maxDefenses = [0] * (maxAttack + 2)

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

    for i in range(maxAttack, 0, -1):
      maxDefenses[i] = max(maxDefenses[i], maxDefenses[i + 1])

    for attack, defense in properties:
      if maxDefenses[attack + 1] > defense:
        ans += 1

    return ans