Skip to content

1686. Stone Game VI 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int stoneGameVI(vector<int>& aliceValues, vector<int>& bobValues) {
    const int n = aliceValues.size();
    vector<vector<int>> values;
    int a = 0;
    int b = 0;

    for (int i = 0; i < n; ++i)
      values.push_back({aliceValues[i], bobValues[i]});

    ranges::sort(values, ranges::greater{},
                 [](const vector<int>& value) { return value[0] + value[1]; });

    for (int i = 0; i < n; ++i)
      if (i % 2 == 0)
        a += values[i][0];
      else
        b += values[i][1];

    return a > b ? 1 : a < b ? -1 : 0;
  }
};

 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 stoneGameVI(int[] aliceValues, int[] bobValues) {
    final int n = aliceValues.length;
    int[][] values = new int[n][];

    for (int i = 0; i < n; ++i)
      values[i] = new int[] {aliceValues[i], bobValues[i]};

    Arrays.sort(values, (a, b) -> Integer.compare(b[0] + b[1], a[0] + a[1]));

    int a = 0;
    int b = 0;

    for (int i = 0; i < n; ++i)
      if (i % 2 == 0)
        a += values[i][0];
      else
        b += values[i][1];

    return Integer.compare(a, b);
  }
}