0901-0910

901. Online Stock Span $\star\star$

902. Numbers At Most N Given Digit Set $\star\star\star$

903. Valid Permutations for DI Sequence $\star\star\star$

904. Fruit Into Baskets $\star\star$

905. Sort Array By Parity $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  vector<int> sortArrayByParity(vector<int>& A) {
    int l = 0;
    int r = A.size() - 1;

    while (l < r) {
      if (A[l] % 2 == 1 && A[r] % 2 == 0) swap(A[l], A[r]);
      if (A[l] % 2 == 0) ++l;
      if (A[r] % 2 == 1) --r;
    }

    return A;
  }
};

906. Super Palindromes $\star\star\star$

907. Sum of Subarray Minimums $\star\star$

 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
30
31
class Solution {
 public:
  int sumSubarrayMins(vector<int>& A) {
    const int n = A.size();
    const int kMod = 1e9 + 7;

    int ans = 0;
    vector<int> prev(n, -1);
    vector<int> next(n, n);
    stack<int> stack1;
    stack<int> stack2;

    for (int i = 0; i < n; ++i) {
      while (!stack1.empty() && A[stack1.top()] > A[i]) stack1.pop();
      prev[i] = stack1.empty() ? -1 : stack1.top();
      stack1.push(i);

      while (!stack2.empty() && A[stack2.top()] > A[i]) {
        int index = stack2.top();
        stack2.pop();
        next[index] = i;
      }
      stack2.push(i);
    }

    for (int i = 0; i < n; ++i)
      ans = (ans + A[i] * (i - prev[i]) * (next[i] - i)) % kMod;

    return ans;
  }
};

908. Smallest Range I $\star$

909. Snakes and Ladders $\star\star$

910. Smallest Range II $\star\star$