diff options
author | Jack Sangdahl <[email protected]> | 2024-12-19 11:57:39 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-19 11:57:39 -0700 |
commit | 77714a237b951c7faf0d28e135401246c1805346 (patch) | |
tree | 7e5947c20dcaf1897bc7b8c13833b4e804060a69 | |
parent | 949ec4e9fd7c2636cb0f13ae4ed67752d868b99d (diff) | |
download | leetcode-77714a237b951c7faf0d28e135401246c1805346.tar.gz leetcode-77714a237b951c7faf0d28e135401246c1805346.zip |
769. max chunks to make sorted
-rw-r--r-- | max_chunks_make_sorted.c | 27 | ||||
-rw-r--r-- | max_chunks_make_sorted.py | 25 |
2 files changed, 52 insertions, 0 deletions
diff --git a/max_chunks_make_sorted.c b/max_chunks_make_sorted.c new file mode 100644 index 0000000..ec73bc5 --- /dev/null +++ b/max_chunks_make_sorted.c @@ -0,0 +1,27 @@ +// 769. Max Chunks To Make Sorted +#include "leetcode.h" + +/* + * you are given an integer array 'arr' of length 'n' that represents a + * permutation of the integers in the range '[0, n - 1]'. we split 'arr' into + * some number of chunks (ie. partitions), and individually sort each chunk. + * after concatenating them, the result should equal the sorted array. return + * the largest number of chunks we can make to sort the array. + */ + +int maxChunksToSorted(int *arr, int arrSize) { + int cnt = 0, sum = 0, ans = 0; + for (int i = 0; i < arrSize; i++) { + sum += i; + cnt += arr[i]; + if (sum == cnt) + ans++; + } + return ans; +} + +int main() { + int a1[] = {4, 3, 2, 1, 0}, a2[] = {1, 0, 2, 3, 4}; + printf("%d\n", maxChunksToSorted(a1, ARRAY_SIZE(a1))); // expect: 1 + printf("%d\n", maxChunksToSorted(a2, ARRAY_SIZE(a2))); // expect: 4 +} diff --git a/max_chunks_make_sorted.py b/max_chunks_make_sorted.py new file mode 100644 index 0000000..224199d --- /dev/null +++ b/max_chunks_make_sorted.py @@ -0,0 +1,25 @@ +# 769. Max Chunks To Make Sorted +from itertools import accumulate + +""" +you are given an integer array 'arr' of length 'n' that represents a +permutation of the integers in the range '[0, n - 1]'. we split 'arr' into +some number of chunks (ie. partitions), and individually sort each chunk. +after concatenating them, the result should equal the sorted array. return +the largest number of chunks we can make to sort the array. +""" + + +class Solution(object): + def maxChunksToSorted(self, arr): + """ + :type arr: List[int] + :rtype: int + """ + return sum(i == j for i, j in enumerate(accumulate(arr, max))) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxChunksToSorted(arr=[4, 3, 2, 1, 0])) + print(obj.maxChunksToSorted(arr=[1, 0, 2, 3, 4])) |