

1001-1010

1001. Grid Illumination $\star\star\star$

1002. Find Common Characters $\star$

class Solution {
 public:
  vector<string> commonChars(vector<string>& A) {
    vector<string> ans;
    vector<int> commonCount(26, INT_MAX);

    for (string& a : A) {
      vector<int> count(26);
      for (char c : a) ++count[c - 'a'];
      for (int i = 0; i < 26; ++i)
        commonCount[i] = min(commonCount[i], count[i]);
    }

    for (char c = 'a'; c <= 'z'; ++c)
      for (int i = 0; i < commonCount[c - 'a']; ++i)
        ans.push_back(string(1, c));

    return ans;
  }
};

1003. Check If Word Is Valid After Substitutions $\star\star$

class Solution {
 public:
  bool isValid(string S) {
    vector<char> stack;

    for (char c : S) {
      if (c == 'c') {
        int n = stack.size();
        if (n < 2 || stack[n - 2] != 'a' || stack[n - 1] != 'b') return false;
        stack.pop_back();
        stack.pop_back();
      } else {
        stack.push_back(c);
      }
    }

    return stack.empty();
  }
};

1004. Max Consecutive Ones III $\star\star$

class Solution {
 public:
  int longestOnes(vector<int>& A, int K) {
    int i = 0;

    for (int a : A) {
      if (a == 0) --K;
      if (K < 0) {
        if (A[i] == 0) ++K;
        ++i;
      }
    }

    return A.size() - i;
  }
};

1005. Maximize Sum Of Array After K Negations $\star$

class Solution {
 public:
  int largestSumAfterKNegations(vector<int>& A, int K) {
    sort(A.begin(), A.end());

    for (int i = 0; i < A.size(); ++i) {
      if (A[i] > 0 || K == 0) break;
      A[i] = -A[i];
      --K;
    }

    return accumulate(A.begin(), A.end(), 0) -
           (K % 2) * *min_element(A.begin(), A.end()) * 2;
  }
};

1006. Clumsy Factorial $\star\star$

class Solution {
 public:
  int clumsy(int N) {
    if (N <= 2) return N;
    if (N <= 4) return N + 3;
    if ((N - 4) % 4 == 0) return N + 1;
    if ((N - 4) % 4 <= 2) return N + 2;
    return N - 1;
  }
};

1007. Minimum Domino Rotations For Equal Row $\star\star$

class Solution {
 public:
  int minDominoRotations(vector<int>& A, vector<int>& B) {
    const int n = A.size();

    vector<int> countA(7);
    vector<int> countB(7);
    vector<int> countBoth(7);

    for (int i = 0; i < n; ++i) {
      ++countA[A[i]];
      ++countB[B[i]];
      if (A[i] == B[i]) ++countBoth[A[i]];
    }

    for (int i = 1; i <= 6; ++i)
      if (countA[i] + countB[i] - countBoth[i] == n)
        return n - max(countA[i], countB[i]);

    return -1;
  }
};

1008. Construct Binary Search Tree from Preorder Traversal $\star\star$

1009. Complement of Base 10 Integer $\star$

1010. Pairs of Songs With Total Durations Divisible by 60 $\star$

class Solution {
 public:
  int numPairsDivisibleBy60(vector<int>& time) {
    int ans = 0;
    vector<int> count(60);

    for (int t : time) {
      t %= 60;
      ans += t == 0 ? count[0] : count[60 - t];
      ++count[t];
    }

    return ans;
  }
};