aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-19 11:57:39 -0700
committerJack Sangdahl <[email protected]>2024-12-19 11:57:39 -0700
commit77714a237b951c7faf0d28e135401246c1805346 (patch)
tree7e5947c20dcaf1897bc7b8c13833b4e804060a69
parent949ec4e9fd7c2636cb0f13ae4ed67752d868b99d (diff)
downloadleetcode-77714a237b951c7faf0d28e135401246c1805346.tar.gz
leetcode-77714a237b951c7faf0d28e135401246c1805346.zip
769. max chunks to make sorted
-rw-r--r--max_chunks_make_sorted.c27
-rw-r--r--max_chunks_make_sorted.py25
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]))