aboutsummaryrefslogtreecommitdiff
path: root/make_array_empty.c
diff options
context:
space:
mode:
Diffstat (limited to 'make_array_empty.c')
-rw-r--r--make_array_empty.c43
1 files changed, 43 insertions, 0 deletions
diff --git a/make_array_empty.c b/make_array_empty.c
new file mode 100644
index 0000000..e0628d0
--- /dev/null
+++ b/make_array_empty.c
@@ -0,0 +1,43 @@
+// 2659. Make Array Empty
+#include "leetcode.h"
+
+/*
+ * given an integer array 'nums' containing distinct numbers and you can perform
+ * the following operations until the array is emtpy. if the first element has
+ * the smallest value, remove it. otherwise, put the first element at the end of
+ * the array. return an integer denoting the number of operations it takes to
+ * make 'nums' empty.
+ */
+
+typedef struct {
+ int val;
+ int idx;
+} pair;
+
+int cmp(const void *a, const void *b) {
+ return ((pair *)a)->val - ((pair *)b)->val;
+}
+
+long long countOperationsToEmptyArray(int *nums, int numsSize) {
+ pair p[numsSize];
+ for (int i = 0; i < numsSize; i++) {
+ p[i].val = nums[i];
+ p[i].idx = i;
+ }
+ qsort(p, numsSize, sizeof(pair), cmp);
+ long long ans = numsSize;
+ for (int i = 1; i < numsSize; i++)
+ if (p[i].idx < p[i - 1].idx)
+ ans += numsSize - i;
+ return ans;
+}
+
+int main() {
+ int n1[] = {3, 4, -1}, n2[] = {1, 2, 4, 3}, n3[] = {1, 2, 3};
+ printf("%lld\n", countOperationsToEmptyArray(n1, ARRAY_SIZE(n1))); // expect:
+ // 5
+ printf("%lld\n", countOperationsToEmptyArray(n2, ARRAY_SIZE(n2))); // expect:
+ // 5
+ printf("%lld\n", countOperationsToEmptyArray(n3, ARRAY_SIZE(n3))); // expect:
+ // 3
+}