aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-25 01:07:53 -0700
committerJack Sangdahl <[email protected]>2025-01-25 01:07:53 -0700
commit3c86d5ce6885144cf5db34e182066407191aea66 (patch)
treedc489050e17d7f9d4915fcb48eabbcc0ca8aa4a0
parent74ac72e6213f2824302802013d14ab5bcf629fa4 (diff)
downloadleetcode-3c86d5ce6885144cf5db34e182066407191aea66.tar.gz
leetcode-3c86d5ce6885144cf5db34e182066407191aea66.zip
2948. make lexicographically smallest array by swapping elements
-rw-r--r--make_lex_small_arr.c64
-rw-r--r--make_lex_small_arr.py36
2 files changed, 100 insertions, 0 deletions
diff --git a/make_lex_small_arr.c b/make_lex_small_arr.c
new file mode 100644
index 0000000..1633124
--- /dev/null
+++ b/make_lex_small_arr.c
@@ -0,0 +1,64 @@
+// 2948. Make Lexicographically Smallest Array by Swapping Elements
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed array of positive integers 'nums' and a positive
+ * integer 'limit'. in one operation, you can choose any two indices 'i' and 'j'
+ * and swap 'nums[i]' and 'nums[j]' if '|nums[i] - nums[j]| <= limit'. return
+ * the lexicographically smallest array that can be obtained by performingthe
+ * operation any number of times.
+ */
+
+int cmp1(const void *a, const void *b) {
+ int *aa = (int *)a;
+ int *bb = (int *)b;
+ return aa[0] - bb[0];
+}
+
+int cmp2(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int *lexicographicallySmallestArray(int *nums, int numsSize, int limit,
+ int *returnSize) {
+ int *ans = (int *)malloc(numsSize * sizeof(int));
+ *returnSize = numsSize;
+ int cpy[numsSize][2];
+ for (int i = 0; i < numsSize; i++) {
+ cpy[i][0] = nums[i];
+ cpy[i][1] = i;
+ }
+ qsort(cpy, numsSize, sizeof(cpy[0]), cmp1);
+ int indices[numsSize];
+ for (int i = 0; i < numsSize;) {
+ int size = 0, prev = cpy[i][0];
+ while (i < numsSize && cpy[i][0] <= (prev + limit)) {
+ indices[size++] = cpy[i][1];
+ prev = cpy[i][0];
+ i++;
+ }
+ qsort(indices, size, sizeof(int), cmp2);
+ for (int j = 0, k = i - size; j < size; j++, k++)
+ ans[indices[j]] = cpy[k][0];
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 5, 3, 9, 8}, rs1;
+ int n2[] = {1, 7, 6, 18, 2, 1}, rs2;
+ int n3[] = {1, 7, 28, 19, 10}, rs3;
+ int *lsa1 = lexicographicallySmallestArray(n1, ARRAY_SIZE(n1), 2, &rs1);
+ int *lsa2 = lexicographicallySmallestArray(n2, ARRAY_SIZE(n2), 3, &rs2);
+ int *lsa3 = lexicographicallySmallestArray(n3, ARRAY_SIZE(n3), 3, &rs3);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", lsa1[i]); // expect: 1 3 5 8 9
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", lsa2[i]); // expect: 1 6 7 18 1 2
+ printf("\n");
+ for (int i = 0; i < rs3; i++)
+ printf("%d ", lsa3[i]); // expect: 1 7 28 19 10
+ printf("\n");
+ free(lsa1);
+ free(lsa2);
+ free(lsa3);
+}
diff --git a/make_lex_small_arr.py b/make_lex_small_arr.py
new file mode 100644
index 0000000..565469d
--- /dev/null
+++ b/make_lex_small_arr.py
@@ -0,0 +1,36 @@
+# 2948. Make Lexicographically Smallest Array by Swapping Elements
+
+"""
+you are given a 0-indexed array of positive integers 'nums' and a positive
+integer 'limit'. in one operation, you can choose any two indices 'i' and 'j'
+and swap 'nums[i]' and 'nums[j]' if '|nums[i] - nums[j]| <= limit'. return
+the lexicographically smallest array that can be obtained by performingthe
+operation any number of times.
+"""
+
+
+class Solution(object):
+ def lexicographicallySmallestArray(self, nums, limit):
+ """
+ :type nums: List[int]
+ :type limit: int
+ :rtype: List[int]
+ """
+ n, indices = len(nums), []
+ cpy, ans = sorted([(nums[i], i) for i in range(n)]), [0] * n
+ for i in range(n):
+ if i == 0 or cpy[i][0] - cpy[i - 1][0] > limit:
+ indices.append([])
+ indices[-1].append(cpy[i][1])
+ for i in indices:
+ curr = sorted(i)
+ for j in range(len(i)):
+ ans[curr[j]] = nums[i[j]]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.lexicographicallySmallestArray(nums=[1, 5, 3, 9, 8], limit=2))
+ print(obj.lexicographicallySmallestArray(nums=[1, 7, 6, 18, 2, 1], limit=3))
+ print(obj.lexicographicallySmallestArray(nums=[1, 7, 28, 19, 10], limit=3))