diff options
Diffstat (limited to 'make_array_empty.c')
-rw-r--r-- | make_array_empty.c | 43 |
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 +} |