#769

Max Chunks To Make Sorted

specialist · 655 · lc medium +30 · verified · 64.1% accepted · 3,648 likes · top 67%

Description

You are given an integer array arr of length n that is a permutation of [0, n - 1]. Split arr into the greatest possible number of contiguous partitions such that sorting each partition individually and concatenating them produces the sorted array. Return that maximum number of partitions.

Example 1:

Input: arr = [4,3,2,1,0]

Output: 1

Explanation:

Splitting into two or more chunks will not return the required result.

For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.

Example 2:

Input: arr = [1,0,2,3,4]

Output: 4

Explanation:

We can split into two chunks, such as [1, 0], [2, 3, 4].

However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

Code

1

2

3

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

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