Leetcode # 769. ⭐ Max Chunks To Make Sorted

Problem

https://leetcode.com/problems/max-chunks-to-make-sorted

把 arr 分成數個 chunk, [sorted(chunk) for chunk in chunks] == sorted(arr)

Solution: PrefixMax and SuffixMin Arrays

prefix := arr[0 : i]
suffix := arr[i : len(arr) – 1]

max(prefix) < min(suffix) ⇔ ∀ a ∈ prefix, ∀ b ∈ suffix, a < b

Time Complexity: O(len(arr))
Space Complexity: O(len(arr))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    prefix_max = [0] * len(arr)
    suffix_min = [len(arr) - 1] * len(arr)
    max_n, min_n = 0, len(arr) - 1
    for i in range(len(arr)):
      prefix_max[i] = (max_n := max(max_n, arr[i]))
    for i in range(len(arr) - 1, -1, -1):
      suffix_min[i] = (min_n := min(min_n, arr[i]))
    
    chunks_n = 1
    for i in range(1, len(arr)):
      if suffix_min[i] > prefix_max[i - 1]:
        chunks_n += 1

    return chunks_

Solution: Prefix Sums

sum(sorted(array)) == sum(array)

Time Complexity: O(len(arr))
Space Complexity: O(len(arr))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    prefix_sums = [arr[0]] * len(arr)
    sorted_sums = [0] * len(arr)
    chunks_n = 1 if arr[0] == 0 else 0
    for i in range(1, len(arr)):
      prefix_sums[i] = arr[i] + prefix_sums[i - 1]
      sorted_sums[i] = i      + sorted_sums[i - 1]
      if prefix_sums[i] == sorted_sums[i]:
        chunks_n += 1
    return chunks_n

Refined Solution

由於我們計算完 prefix_sums[i] 和 sorted_sums[i] 後
就用不到 prefix_sums[:i] 和 sorted_sums[:i] 了
所以我們可以只保留 prefix_sums[i] 和 sorted_sums[i] 以減少 space complexity

Time Complexity: O(len(arr))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    prefix_sum = arr[0]
    sorted_sum = 0
    chunks_n = 1 if arr[0] == 0 else 0
    for i in range(1, len(arr)):
      prefix_sum += arr[i]
      sorted_sum += i
      if prefix_sum == sorted_sum:
        chunks_n += 1
    return chunks_n

Solution: Monotonic Increasing Stack

chunk_i + [e], if e < max(chunk_i) ⇒ e must merge with one or more existing chunks

ex: arr = [1, 2, 0, 3]

1. [1]
2. [1], [2]
3. [1], [0, 2]
   [1] + [2] ⇒ [1, 2] ⇒[0, 1, 2]
4. [0, 1, 2, 3]

Time Complexity: O(len(arr) ** 2)
Space Complexity: O(len(arr))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    chunks = [[arr[0]]]
    for n in arr[1:]:
      if n > chunks[-1][-1]:
        chunks.append([n])
        continue

      while len(chunks) > 1 and n < chunks[-2][-1]:
        final_c = chunks.pop()
        second_to_last_c = chunks.pop()
        chunks.append(second_to_last_c + final_c)
      insort(chunks[-1], n)

    return len(chunks)

Refined Solution

由於我們只關心 max(chunk_i)
stack 的每一個元素，代表一個 chunk，亦是該 chunk 的最大值

Time Complexity: O(len(arr))
Space Complexity: O(len(arr))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    stack = [arr[0]]
    for n in arr[1:]:
      if n > stack[-1]:
        stack.append(n)
        continue

      final = stack.pop()
      while stack and n < stack[-1]:
        stack.pop()
      stack.append(final)

    return len(stack)

Solution: Maximum Element

思路接近 Solution: Prefix Sums
當 arr[i:j + 1] 中最大的元素是 j
亦即小於 j 的元素都在 arr[:j + 1]
而大於 j 的元素都在 arr[j + 1:]

Time Complexity: O(len(arr))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def maxChunksToSorted(self, arr: List[int]) -> int:
    max_n = arr[0]
    chunks_n = 1 if arr[0] == 0 else 0
    for i in range(1, len(arr)):
      max_n = max(max_n, arr[i])
      if max_n == i:
        chunks_n += 1
    return chunks_n

Last Updated on 2024/12/22 by A1go