Max Chunks To Make Sorted

MediumArrayStackGreedySortingMonotonic Stack

Solution

export function maxChunksToSorted(arr: number[]): number {
  let answer = 0;
  let [prefixSum, targetSum] = [0, 0];
  arr.forEach((num, i) => {
    prefixSum += num;
    targetSum += i;
    if (prefixSum === targetSum) {
      answer += 1;
    }
  });
  return answer;
}

Complexity

  • Time: O(n)O(n)
  • Space: O(1)O(1)