Java solution, left max and right min.
Algorithm: Iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chunck.\nUse two ar
Algorithm: Iterate through the array, each time all elements to the left are smaller (or equal) to all elements to the right, there is a new chunck.\nUse two arrays to store the left max and right min to achieve O(n) time complexity. Space complexity is O(n) too.\nThis algorithm can be used to solve ver1 too.\n```\nclass Solution {\n    public int maxChunksToSorted(int[] arr) {\n        int n = arr.length;\n        int[] maxOfLeft = new int[n];\n        int[] minOfRight = new int[n];\n\n        maxOfLeft[0] = arr[0];\n        for (int i = 1; i < n; i++) {\n            maxOfLeft[i] = Math.max(maxOfLeft[i-1], arr[i]);\n        }\n\n        minOfRight[n - 1] = arr[n - 1];\n        for (int i = n - 2; i >= 0; i--) {\n            minOfRight[i] = Math.min(minOfRight[i + 1], arr[i]);\n        }\n\n        int res = 0;\n        for (int i = 0; i < n - 1; i++) {\n            if (maxOfLeft[i] <= minOfRight[i + 1]) res++;\n        }\n\n        return res + 1;\n    }\n}\n```
[]