aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-06-17 23:46:46 -0600
committerJack Sangdahl <[email protected]>2025-06-17 23:46:46 -0600
commitf2349693f5c352357a135454fde298f109b2198a (patch)
tree877906bd9e09f2787dc1eb749f460d882d95b247
parent403a31eb22ad406e0d49a72b867a057121828cc2 (diff)
downloadleetcode-f2349693f5c352357a135454fde298f109b2198a.tar.gz
leetcode-f2349693f5c352357a135454fde298f109b2198a.zip
2966. divide array into arrays with max difference
-rw-r--r--divide_array_max_diff.c69
-rw-r--r--divide_array_max_diff.py17
2 files changed, 63 insertions, 23 deletions
diff --git a/divide_array_max_diff.c b/divide_array_max_diff.c
index 72e8648..8c510b3 100644
--- a/divide_array_max_diff.c
+++ b/divide_array_max_diff.c
@@ -11,25 +11,66 @@
* return any of them
*/
-int cmp(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); }
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
int **divideArray(int *nums, int numsSize, int k, int *returnSize,
int **returnColumnSizes) {
- int num_arr = numsSize / 3;
- int **ans = (int **)calloc(num_arr, sizeof(int *));
- *returnColumnSizes = (int *)calloc(num_arr, sizeof(int));
- *returnSize = 0;
qsort(nums, numsSize, sizeof(int), cmp);
- for (int i = 0; i < num_arr; i++) {
- ans[i] = (int *)calloc(3, sizeof(int));
- (*returnColumnSizes)[i] = 3;
- for (int j = 0; j < 3; j++) {
- int idx = i * 3 + j;
- if (j && nums[idx] - nums[i * 3] > k)
- return ans;
- ans[i][j] = nums[idx];
+ int **ans = (int **)malloc((numsSize / 3) * sizeof(int *)), rs = 0;
+ for (int i = 2; i < numsSize; i += 3) {
+ if (nums[i] - nums[i - 2] > k) {
+ *returnSize = 0;
+ return NULL;
}
+ ans[rs] = (int *)malloc(3 * sizeof(int));
+ ans[rs][0] = nums[i - 2];
+ ans[rs][1] = nums[i - 1];
+ ans[rs][2] = nums[i];
+ rs++;
}
- *returnSize = num_arr;
+ *returnSize = rs;
+ *returnColumnSizes = (int *)malloc(rs * sizeof(int));
+ for (int i = 0; i < rs; i++)
+ (*returnColumnSizes)[i] = 3;
return ans;
}
+
+int main() {
+ int n1[] = {1, 3, 4, 8, 7, 9, 3, 5, 1}, rs1, *rcs1;
+ int n2[] = {2, 4, 2, 2, 5, 2}, rs2, *rcs2;
+ int n3[] = {4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11}, rs3,
+ *rcs3;
+ int **da1 = divideArray(n1, ARRAY_SIZE(n1), 2, &rs1, &rcs1);
+ int **da2 = divideArray(n2, ARRAY_SIZE(n2), 2, &rs2, &rcs2);
+ int **da3 = divideArray(n3, ARRAY_SIZE(n3), 14, &rs3, &rcs3);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++)
+ printf("%d ", da1[i][j]); // expect: [[1,1,3],[3,4,5],[7,8,9]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++)
+ printf("%d ", da2[i][j]); // expect: null
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ for (int j = 0; j < rcs3[i]; j++)
+ printf(
+ "%d ",
+ da3[i][j]); // expect:
+ // [[2,2,12],[4,8,5],[5,9,7],[7,8,5],[5,9,10],[11,12,2]]
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(da1[i]), free(rcs1);
+ free(da1);
+ for (int i = 0; i < rs2; i++)
+ free(da2[i]), free(rcs2);
+ free(da1);
+ for (int i = 0; i < rs3; i++)
+ free(da3[i]), free(rcs3);
+ free(da1);
+}
diff --git a/divide_array_max_diff.py b/divide_array_max_diff.py
index 41a2a22..3bdf682 100644
--- a/divide_array_max_diff.py
+++ b/divide_array_max_diff.py
@@ -18,18 +18,12 @@ class Solution(object):
:type k: int
:rtype: List[List[int]]
"""
- size = len(nums)
- if size % 3 != 0:
- return []
nums.sort()
ans = []
- group_idx = 0
- for i in range(0, size, 3):
- if i + 2 < size and nums[i + 2] - nums[i] <= k:
- ans.append([nums[i], nums[i + 1], nums[i + 2]])
- group_idx += 1
- else:
+ for i in range(2, len(nums), 3):
+ if nums[i] - nums[i - 2] > k:
return []
+ ans.append([nums[i - 2], nums[i - 1], nums[i]])
return ans
@@ -37,3 +31,8 @@ if __name__ == "__main__":
obj = Solution()
print(obj.divideArray(nums=[1, 3, 4, 8, 7, 9, 3, 5, 1], k=2))
print(obj.divideArray(nums=[1, 3, 3, 2, 7, 3], k=3))
+ print(
+ obj.divideArray(
+ nums=[4, 2, 9, 8, 2, 12, 7, 12, 10, 5, 8, 5, 5, 7, 9, 2, 5, 11], k=14
+ )
+ )