0911-0920

911. Online Election $\star\star$

912. Sort an Array $\star\star$

913. Cat and Mouse $\star\star\star$

914. X of a Kind in a Deck of Cards $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  bool hasGroupsSizeX(vector<int>& deck) {
    unordered_map<int, int> numCounts;
    for (int d : deck) ++numCounts[d];

    int gcd = 0;
    for (auto& [_, value] : numCounts) gcd = __gcd(gcd, value);

    return gcd >= 2;
  }
};

915. Partition Array into Disjoint Intervals $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int partitionDisjoint(vector<int>& A) {
    const int n = A.size();

    vector<int> min(n);
    min[n - 1] = A[n - 1];
    int max = INT_MIN;

    for (int i = n - 2; i >= 0; --i) min[i] = std::min(min[i + 1], A[i]);

    for (int i = 0; i < n; ++i) {
      max = std::max(max, A[i]);
      if (max <= min[i + 1]) return i + 1;
    }

    throw;
  }
};

916. Word Subsets $\star\star$

917. Reverse Only Letters $\star$

918. Maximum Sum Circular Subarray $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int maxSubarraySumCircular(vector<int>& A) {
    int totalSum = 0;
    int currMaxSum = 0;
    int currMinSum = 0;
    int maxSum = INT_MIN;
    int minSum = INT_MAX;

    for (int a : A) {
      totalSum += a;
      currMaxSum = max(currMaxSum + a, a);
      currMinSum = min(currMinSum + a, a);
      maxSum = max(maxSum, currMaxSum);
      minSum = min(minSum, currMinSum);
    }

    return maxSum < 0 ? maxSum : max(maxSum, totalSum - minSum);
  }
};

919. Complete Binary Tree Inserter $\star\star$

920. Number of Music Playlists $\star\star\star$