Java Solution beats 99.9% with detailed example and explanation
Problem Invariant: For an element, if all the numbers to its left are smaller or equal to all the numbers to its right, we can always insert a split point betwe
Problem Invariant: For an element, if all the numbers to its left are smaller or equal to all the numbers to its right, we can always insert a split point between the element and its next element which separate the array into two parts and after we sort the two parts individually, the concatenation of them will be a sorted array.\n\nExample:\n\nindex:      0 1 2 3 4\narr[i]        2 1 3 4 4\nmaxLeft   2 2 3 4 4\nminRight  1 1 3 4 4\n\nwhen i = 1, maxLeft[i] <= minRight[i + 1] (maxLeft[i] includes the i-th number itself but minRight[i +1] only counts the numbers to its right), then we can insert a split point between index 1 and 2. This will generate two parts [2,1] and [3,4,4]. When we sort the two parts individually, the concatenation of the sorted arrays will also be a sorted array. [1,2] + [3,4,4] => [1,2,3,4,4].\n\nWhen i = 2, 3. The same analysis apply to them.\n\nCode:\n```\n    public int maxChunksToSorted(int[] arr) {\n        int n;\n        if (arr == null || (n = arr.length) == 0) {\n            return 0;\n        }\n        int[] maxLeft = new int[n];\n        int[] minRight = new int[n];\n        \n        maxLeft[0] = arr[0];\n        for (int i = 1; i < n; i++) {\n            maxLeft[i] = Math.max(maxLeft[i - 1], arr[i]);\n        }\n        \n        minRight[n - 1] = arr[n - 1];\n        for (int i = n - 2; i >= 0; i--) {\n            minRight[i] = Math.min(minRight[i + 1], arr[i]);\n        }\n        \n        int numOfInsertion = 0;\n        for (int i = 0; i < n - 1; i++) {\n            if (maxLeft[i] <= minRight[i + 1]) {\n                numOfInsertion++;\n            }\n        }\n        return numOfInsertion + 1;\n    }\n```
[]