Skip to content

768. Max Chunks To Make Sorted II 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int maxChunksToSorted(vector<int>& arr) {
    const int n = arr.size();
    int ans = 0;
    vector<int> maxL(n);  // l[i] := max(arr[0..i])
    vector<int> minR(n);  // r[i] := min(arr[i..n))

    for (int i = 0; i < n; ++i)
      maxL[i] = i == 0 ? arr[i] : max(arr[i], maxL[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      minR[i] = i == n - 1 ? arr[i] : min(arr[i], minR[i + 1]);

    for (int i = 0; i + 1 < n; ++i)
      if (maxL[i] <= minR[i + 1])
        ++ans;

    return ans + 1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int maxChunksToSorted(int[] arr) {
    final int n = arr.length;
    int ans = 0;
    int[] maxL = new int[n]; // l[i] := max(arr[0..i])
    int[] minR = new int[n]; // r[i] := min(arr[i..n))

    for (int i = 0; i < n; ++i)
      maxL[i] = i == 0 ? arr[i] : Math.max(arr[i], maxL[i - 1]);

    for (int i = n - 1; i >= 0; --i)
      minR[i] = i == n - 1 ? arr[i] : Math.min(arr[i], minR[i + 1]);

    for (int i = 0; i + 1 < n; ++i)
      if (maxL[i] <= minR[i + 1])
        ++ans;

    return ans + 1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maxChunksToSorted(self, arr: list[int]) -> int:
    n = len(arr)
    ans = 0
    mx = -math.inf
    mn = [arr[-1]] * n

    for i in reversed(range(n - 1)):
      mn[i] = min(mn[i + 1], arr[i])

    for i in range(n - 1):
      mx = max(mx, arr[i])
      if mx <= mn[i + 1]:
        ans += 1

    return ans + 1