769. Max chuncks make sorted

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

769_solution2_prefix_suffix.c

#include <stdlib.h>

int maxChunksToSorted(int *arr, int arrSize) {
  int *prefixMax = malloc(arrSize * sizeof(int));
  int *suffixMin = malloc(arrSize * sizeof(int));

  prefixMax[0] = arr[0];
  for (int i = 1; i < arrSize; i++)
    prefixMax[i] = arr[i] > prefixMax[i - 1] ? arr[i] : prefixMax[i - 1];

  suffixMin[arrSize - 1] = arr[arrSize - 1];
  for (int i = arrSize - 2; i >= 0; i--)
    suffixMin[i] = arr[i] < suffixMin[i + 1] ? arr[i] : suffixMin[i + 1];

  int chunks = 1; // the last chunk always exists
  for (int i = 0; i < arrSize - 1; i++)
    if (prefixMax[i] <= suffixMin[i + 1])
      chunks++;

  free(prefixMax);
  free(suffixMin);
  return chunks;
}

769_solution1_stack.cpp

#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();
  }
};

769_solution2_prefix_suffix.cpp

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  int maxChunksToSorted(vector<int> &arr) {
    int n = arr.size();
    vector<int> prefixMax(n), suffixMin(n);

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

    suffixMin[n - 1] = arr[n - 1];
    for (int i = n - 2; i >= 0; --i)
      suffixMin[i] = min(suffixMin[i + 1], arr[i]);

    int chunks = 1; // the last chunk always exists
    for (int i = 0; i < n - 1; ++i)
      if (prefixMax[i] <= suffixMin[i + 1])
        ++chunks;

    return chunks;
  }
};

769_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)
}

769_solution2_prefix_suffix.go

package main

func maxChunksToSorted(arr []int) int {
    n := len(arr)
    prefixMax, suffixMin := make([]int, n), make([]int, n)

    prefixMax[0] = arr[0]
    for i := 1; i < n; i++ {
        prefixMax[i] = max(prefixMax[i-1], arr[i])
    }

    suffixMin[n-1] = arr[n-1]
    for i := n - 2; i >= 0; i-- {
        suffixMin[i] = min(suffixMin[i+1], arr[i])
    }

    chunks := 1 // the last chunk always exists
    for i := 0; i < n-1; i++ {
        if prefixMax[i] <= suffixMin[i+1] {
            chunks++
        }
    }

    return chunks
}

769_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();
    }
}

769_solution2_prefix_suffix.java

class Solution {
    public int maxChunksToSorted(int[] arr) {
        int n = arr.length;
        int[] prefixMax = new int[n], suffixMin = new int[n];

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

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

        int chunks = 1; // the last chunk always exists
        for (int i = 0; i < n - 1; i++)
            if (prefixMax[i] <= suffixMin[i + 1])
                chunks++;

        return chunks;
    }
}

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

769_solution2_prefix_suffix.js

/**
 * @param {number[]} arr
 * @return {number}
 */
var maxChunksToSorted = function (arr) {
  const n = arr.length;
  const prefixMax = new Array(n);
  const suffixMin = new Array(n);

  prefixMax[0] = arr[0];
  for (let i = 1; i < n; i++) prefixMax[i] = Math.max(prefixMax[i - 1], arr[i]);

  suffixMin[n - 1] = arr[n - 1];
  for (let i = n - 2; i >= 0; i--) suffixMin[i] = Math.min(suffixMin[i + 1], arr[i]);

  let chunks = 1; // the last chunk always exists
  for (let i = 0; i < n - 1; i++) if (prefixMax[i] <= suffixMin[i + 1]) chunks++;

  return chunks;
};

769_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)

769_solution2_prefix_suffix.py

from typing import List


class Solution:
    def maxChunksToSorted(self, arr: List[int]) -> int:
        n = len(arr)
        prefix_max, suffix_min = [0] * n, [0] * n

        prefix_max[0] = arr[0]
        for i in range(1, n):
            prefix_max[i] = max(prefix_max[i - 1], arr[i])

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

        chunks = 1  # the last chunk always exists
        for i in range(n - 1):
            if prefix_max[i] <= suffix_min[i + 1]:
                chunks += 1

        return chunks

769_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
    }
}

769_solution2_prefix_suffix.rs

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut prefix_max = vec![0; n];
        let mut suffix_min = vec![0; n];

        prefix_max[0] = arr[0];
        for i in 1..n {
            prefix_max[i] = prefix_max[i - 1].max(arr[i]);
        }

        suffix_min[n - 1] = arr[n - 1];
        for i in (0..n - 1).rev() {
            suffix_min[i] = suffix_min[i + 1].min(arr[i]);
        }

        let mut chunks = 1; // the last chunk always exists
        for i in 0..n - 1 {
            if prefix_max[i] <= suffix_min[i + 1] {
                chunks += 1;
            }
        }

        chunks
    }
}