Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

768. Max Chunks To Make Sorted II

Time: $O(n)$

Space: $O(n)$

			


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;
  }
};




			


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;
  }
}




			


class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    n = len(arr)
    ans = 0
    maxi = -math.inf
    mini = [arr[-1]] * n

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

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

    return ans + 1