[Google Question] Max Partitions To Make Array Sorted

Problem: Given an array that is a permutation of [0, 1, ... n - 1], we split the array into some number of partitions, and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example:

Input: arr = [2,1,0,2,4,3]
Output: 2
Explanation:
We can split into two chunks, such as [2, 1, 0], [4, 3].

Approach: The intuition is if the array is sorted in ascending order then we can treat every element as one partition. For example [0, 1, 2] can be split into [0], [1], [2] and in case the array is sorted in descending order, we can have only one chunk which is the whole array. For example [2, 1, 0] . 

With the above knowledge, we can see if Max(arr[0]...arr[k]) is equal to k then we can increment the number of chunks by one. 

Implementation in C#:

    public int MaxChunksToSorted(int[] arr) 

    {

        int chunksRequired = 0;

        int max = 0;

        for (int i = 0; i < arr.Length; ++i)

        {

            max = Math.Max(max, arr[i]);

            if (max == i)

            {

                ++chunksRequired;

            }

        }

        return chunksRequired;

    }

Complexity: O(n)