[Python] nlogn, faster than 97%, with detailed explanations and comments
The idea is to build on Max Chunks to Make Sorted I, where the problem is easier with no repeats and all indexes present.\n\nThe solution to MCMS-I is simple on
The idea is to build on Max Chunks to Make Sorted I, where the problem is easier with no repeats and all indexes present.\n\nThe solution to MCMS-I is simple once you realize that each number represent an index, and in order for the array to be sorted at the end, each number should be in a chunk that includes its index (so that the sort operation will place it back at its correct position before the concatenation).\n\nFor instance, consider the example array [1, 0, 2, 3, 4]. In order for number 1 to be at the correct position (i.e. index 1) at the end of the operation, the chunk that includes number 1 should also includes index 1. That is, [1, 0] at the minimum. In the senario, number 0 is therefore also placed in this chunk, which also contains index 0 so we don\'t need to expand the chunk further. For number 2, we can simply use a chunk of size 1 because it is already place correctly, and so on, so forth until the end.\n\nConsider the second example array [4, 3, 2, 1, 0]. This time number 4 should be include in a chunk with index 4, that is at the minimum [4, 3, 2, 1, 0]. All other number are also include in this chunk, leaving solution equals 1.\n\nWe can solve this problem efficiently in O(N) with the following code:\n\n```python\ndef max_chunk_to_make_sorted_I(arr):\n\t"""\n\tWe define a target, which will be the index to include in the current chunk. \n\tWhile we parse the array, we either:\n\t\t- update the target because the current number is outside the range of the current chunk\n\t\t- close current chunk and start fresh at the next index\n\t"""\n        \n    target = 0 \n    ret = 0\n    for idx, num in enumerate(arr):\n\t\tif num > target:\n\t\t\t# in this case, this means that the current number represent an index outside the range of the chunk\n\t\t\t# we update the range of the chunk to be greater than (or equal to at least) this number\n\t\t\ttarget = num\n        elif idx == target:\n\t\t\t# in this case we have reached the range of the chunk, without needing to expand it further\n\t\t\t# we "close" the chunk by counting +1 and move the target to the next index\n\t\t\tret += 1\n            target = idx + 1\n\t\telse:\n\t\t\t# in this case, nothing happens.\n\t\t\t# We don\'t need to expand the range of the chunk, but we haven\'t reached it yet so we can\'t close it\n\t\t\tpass\n\t\t\n\treturn ret  # we return the number of closed chunks\n```\n\nMCMS-II is more complicated because now, numbers don\'t necessarily represent indexes. We can not use the above strategy anymore. This is not a problem however because we can simply arg-sort the array and fall back to the previous case.\n\nConsider the example array [2,1,3,4,4]. The argsort operation will give us [1, 0, 2, 3, 4] because number 2 is the second smallest (i.e. index 1 because python is zero-indexed), number 1 is the smallest (i.e. index 0) and so on so forth.\n\nWe can now solve the problem with the previous code! The sorting operation is O(N logN) and solve operation is still O(N), resulting in total O(N logN)\n\n```python\ndef max_chunk_to_make_sorted_II(arr):\n\t"""\n\tWe argsort the array and solve the problem as with MCMS-I\n\t"""\n\t# we use built-in function \'enumerate\' which returns each number with its index, and sort with consideration on the number\n\tarr = sorted(enumerate(arr), key=lambda x: x[1])\n\t\n\t# we only care about the indexes\n\tarr = [idx for idx, num in arr]\n\t\n\t# we solve using the previous code!\n\treturn max_chunk_to_make_sorted_I(arr)\n```\n\nPlease let me know if this was useful to you, or if you need precision!\nCheers!\n\n![image](https://assets.leetcode.com/users/kaijuml/image_1588665695.png)\n\n\n
[]