768. Max chuncks make sorted II

768_solution1_stack.c

#include <stdlib.h>

int maxChunksToSorted(int *arr, int arrSize) {
  int *st = malloc(arrSize * sizeof(int));
  int top = 0;

  for (int i = 0; i < arrSize; i++) {
    int n = arr[i];
    if (top == 0 || n >= st[top - 1]) {
      st[top++] = n;
    } else {
      int mx = st[top - 1];
      top--;
      while (top > 0 && n < st[top - 1])
        top--;
      st[top++] = mx;
    }
  }

  free(st);
  return top;
}

// ---- Alternative Compact Version ----
// int maxChunksToSorted(int *arr, int arrSize) {
//   int *st = malloc(arrSize * sizeof(int)); // max of each chunk, non-decreasing
//   int top = 0;
//   for (int i = 0; i < arrSize; i++) {
//     int curMax = arr[i];
//     while (top > 0 && st[top - 1] > arr[i]) {
//       if (st[top - 1] > curMax)
//         curMax = st[top - 1];
//       top--;
//     }
//     st[top++] = curMax;
//   }
//   free(st);
//   return top;
// }

768_solution2_maxprefix_minsuffix.c

#include <limits.h>
#include <stdlib.h>

int maxChunksToSorted(int *arr, int arrSize) {
  int *sufMin = malloc((arrSize + 1) * sizeof(int));
  sufMin[arrSize] = INT_MAX;
  for (int i = arrSize - 1; i >= 0; i--)
    sufMin[i] = arr[i] < sufMin[i + 1] ? arr[i] : sufMin[i + 1];

  int chunks = 0, prefMax = INT_MIN;
  for (int i = 0; i < arrSize; i++) {
    if (arr[i] > prefMax)
      prefMax = arr[i];
    if (prefMax <= sufMin[i + 1])
      chunks++; // valid cut after i (i = n-1 always counts)
  }

  free(sufMin);
  return chunks;
}

768_solution1_stack.cpp

#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

class Solution {
public:
  int maxChunksToSorted(vector<int> &arr) {
    stack<int> st;

    for (int n : arr) {
      if (st.empty() || n >= st.top()) {
        st.push(n);
      } else {
        int mx = st.top();
        st.pop();
        while (!st.empty() && n < st.top())
          st.pop();
        st.push(mx);
      }
    }

    return st.size();
  }
};

// ---- Alternative Compact Version ----
// class Solution {
// public:
//   int maxChunksToSorted(vector<int> &arr) {
//     stack<int> st;
//     for (int x : arr) {
//       int curMax = x;
//       while (!st.empty() && st.top() > x) {
//         curMax = max(curMax, st.top());
//         st.pop();
//       }
//       st.push(curMax);
//     }
//     return st.size();
//   }
// };

768_solution2_maxprefix_minsuffix.cpp

#include <algorithm>
#include <climits>
#include <vector>
using namespace std;

class Solution {
public:
  int maxChunksToSorted(vector<int> &arr) {
    int n = arr.size();
    vector<int> sufMin(n + 1, INT_MAX);
    for (int i = n - 1; i >= 0; --i)
      sufMin[i] = min(sufMin[i + 1], arr[i]);

    int chunks = 0, prefMax = INT_MIN;
    for (int i = 0; i < n; ++i) {
      prefMax = max(prefMax, arr[i]);
      if (prefMax <= sufMin[i + 1])
        ++chunks; // valid cut after i (i = n-1 always counts)
    }
    return chunks;
  }
};

768_solution1_stack.go

package main

func maxChunksToSorted(arr []int) int {
    st := []int{}

    for _, n := range arr {
        if len(st) == 0 || n >= st[len(st)-1] {
            st = append(st, n)
        } else {
            mx := st[len(st)-1]
            st = st[:len(st)-1]
            for len(st) > 0 && n < st[len(st)-1] {
                st = st[:len(st)-1]
            }
            st = append(st, mx)
        }
    }

    return len(st)
}

// ---- Alternative Compact Version ----
// func maxChunksToSorted(arr []int) int {
//  st := []int{} // max of each chunk, non-decreasing
//  for _, x := range arr {
//      curMax := x
//      for len(st) > 0 && st[len(st)-1] > x {
//          curMax = max(curMax, st[len(st)-1])
//          st = st[:len(st)-1]
//      }
//      st = append(st, curMax)
//  }
//  return len(st)
// }

768_solution2_maxprefix_minsuffix.go

package main

import "math"

func maxChunksToSorted(arr []int) int {
    n := len(arr)
    sufMin := make([]int, n+1)
    sufMin[n] = math.MaxInt
    for i := n - 1; i >= 0; i-- {
        sufMin[i] = min(sufMin[i+1], arr[i])
    }

    chunks, prefMax := 0, math.MinInt
    for i := 0; i < n; i++ {
        prefMax = max(prefMax, arr[i])
        if prefMax <= sufMin[i+1] {
            chunks++ // valid cut after i (i = n-1 always counts)
        }
    }
    return chunks
}

768_solution1_stack.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> st = new ArrayDeque<>();

        for (int n : arr) {
            if (st.isEmpty() || n >= st.peek()) {
                st.push(n);
            } else {
                int mx = st.pop();
                while (!st.isEmpty() && n < st.peek())
                    st.pop();
                st.push(mx);
            }
        }

        return st.size();
    }
}

// ---- Alternative Compact Version ----
// class Solution {
//     public int maxChunksToSorted(int[] arr) {
//         int[] st = new int[arr.length]; // max of each chunk, non-decreasing
//         int top = 0;
//         for (int x : arr) {
//             int curMax = x;
//             while (top > 0 && st[top - 1] > x)
//                 curMax = Math.max(curMax, st[--top]);
//             st[top++] = curMax;
//         }
//         return top;
//     }
// }

768_solution2_maxprefix_minsuffix.java

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] sufMin = new int[n + 1];
        sufMin[n] = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--)
            sufMin[i] = Math.min(sufMin[i + 1], arr[i]);

        int chunks = 0, prefMax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            prefMax = Math.max(prefMax, arr[i]);
            if (prefMax <= sufMin[i + 1])
                chunks++; // valid cut after i (i = n-1 always counts)
        }
        return chunks;
    }
}

768_solution1_stack.js

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const st = [];

  for (const n of arr) {
    if (st.length === 0 || n >= st[st.length - 1]) {
      st.push(n);
    } else {
      const mx = st.pop();
      while (st.length && n < st[st.length - 1]) st.pop();
      st.push(mx);
    }
  }

  return st.length;
};

// ---- Alternative Compact Version ----
// var maxChunksToSorted = function (arr) {
//   const st = []; // max of each chunk, non-decreasing
//   for (const x of arr) {
//     let curMax = x;
//     while (st.length && st[st.length - 1] > x) curMax = Math.max(curMax, st.pop());
//     st.push(curMax);
//   }
//   return st.length;
// };

768_solution2_maxprefix_minsuffix.js

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const n = arr.length;
  const sufMin = new Array(n + 1).fill(Infinity);
  for (let i = n - 1; i >= 0; i--) sufMin[i] = Math.min(sufMin[i + 1], arr[i]);

  let chunks = 0;
  let prefMax = -Infinity;
  for (let i = 0; i < n; i++) {
    prefMax = Math.max(prefMax, arr[i]);
    if (prefMax <= sufMin[i + 1]) chunks++; // valid cut after i (i = n-1 always counts)
  }
  return chunks;
};

768_solution1_stack.py

from typing import List


class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        st = []

        for n in arr:
            if not st or n >= st[-1]:
                st.append(n)
            else:
                mx = st.pop()
                while st and n < st[-1]:
                    st.pop()
                st.append(mx)

        return len(st)

# ---- Alternative Compact Version ----
# class Solution:
#     def maxChunksToSorted(self, arr: List[int]) -> int:
#         st = []  # max of each chunk, non-decreasing
#         for x in arr:
#             cur_max = x
#             while st and st[-1] > x:
#                 cur_max = max(cur_max, st.pop())
#             st.append(cur_max)
#         return len(st)

768_solution2_maxprefix_minsuffix.py

from typing import List


class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        suf_min = [float("inf")] * (n + 1)
        for i in range(n - 1, -1, -1):
            suf_min[i] = min(suf_min[i + 1], arr[i])

        chunks, pref_max = 0, float("-inf")
        for i in range(n):
            pref_max = max(pref_max, arr[i])
            if pref_max <= suf_min[i + 1]:
                chunks += 1  # valid cut after i (i = n-1 always counts)
        return chunks

768_solution1_stack.rs

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let mut st: Vec<i32> = Vec::new();

        for n in arr {
            match st.last() {
                Some(&top) if n < top => {
                    let mx = st.pop().unwrap();
                    while st.last().is_some_and(|&t| n < t) {
                        st.pop();
                    }
                    st.push(mx);
                }
                _ => st.push(n),
            }
        }

        st.len() as i32
    }
}

// ---- Alternative Compact Version ----
// impl Solution {
//     pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
//         let mut st: Vec<i32> = Vec::new(); // max of each chunk, non-decreasing
//         for x in arr {
//             let mut cur_max = x;
//             while let Some(&top) = st.last() {
//                 if top <= x {
//                     break;
//                 }
//                 cur_max = cur_max.max(top);
//                 st.pop();
//             }
//             st.push(cur_max);
//         }
//         st.len() as i32
//     }
// }

768_solution2_maxprefix_minsuffix.rs

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut suf_min = vec![i32::MAX; n + 1];
        for i in (0..n).rev() {
            suf_min[i] = suf_min[i + 1].min(arr[i]);
        }

        let mut chunks = 0;
        let mut pref_max = i32::MIN;
        for i in 0..n {
            pref_max = pref_max.max(arr[i]);
            if pref_max <= suf_min[i + 1] {
                chunks += 1; // valid cut after i (i = n-1 always counts)
            }
        }
        chunks
    }
}