diff options
author | Jack Sangdahl <[email protected]> | 2025-06-08 23:52:09 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-06-08 23:52:09 -0600 |
commit | 27229aa885c8e82f4118905da553565136d6a71f (patch) | |
tree | 23f3c619cc58e1346aa2555a9267d3aa2a5d5267 | |
parent | d3382a11112d2dfe31b2d156c73d07d1ee213a97 (diff) | |
download | leetcode-27229aa885c8e82f4118905da553565136d6a71f.tar.gz leetcode-27229aa885c8e82f4118905da553565136d6a71f.zip |
1649. create sorted array through instructions
-rw-r--r-- | create_sorted_arr_instr.c | 51 | ||||
-rw-r--r-- | create_sorted_arr_instr.py | 48 |
2 files changed, 99 insertions, 0 deletions
diff --git a/create_sorted_arr_instr.c b/create_sorted_arr_instr.c new file mode 100644 index 0000000..2a3624d --- /dev/null +++ b/create_sorted_arr_instr.c @@ -0,0 +1,51 @@ +// 1649. Create Sorted Array through Instructions +#include "leetcode.h" + +/* + * given an integer array 'instructions', you are asked to create a sorted array + * from the elements in 'instructions'. you start with an empty container + * 'nums'. for each element from left to right in 'instructions', insert it into + * 'nums'. the cost of each insertion is the minimum of the following: the + * number of elements currently in 'nums' that are strictly less than + * 'instructions[i]', the number of elements currently in 'nums' that are + * strictly greater than 'instructions[i]'. return the total cost to insert all + * elements from 'instructions' into 'nums'. since the answer may be large, + * return it modulo 10^9 + 7 + */ + +static int arr[10001]; + +void update(int x) { + while (x < 10001) { + arr[x]++; + x += x & -x; + } +} + +int get(int x) { + int res = 0; + while (x > 0) { + res += arr[x]; + x -= x & -x; + } + return res; +} + +int createSortedArray(int *instructions, int instructionsSize) { + memset(arr, 0, sizeof(arr)); + int ans = 0, mod = 1e9 + 7; + for (int i = 0; i < instructionsSize; i++) { + ans = + (ans + fmin(get(instructions[i] - 1), i - get(instructions[i]))) % mod; + update(instructions[i]); + } + return ans; +} + +int main() { + int i1[] = {1, 5, 6, 2}, i2[] = {1, 2, 3, 6, 5, 4}, + i3[] = {1, 2, 3, 3, 2, 4, 2, 1, 2}; + printf("%d\n", createSortedArray(i1, ARRAY_SIZE(i1))); // expect: 1 + printf("%d\n", createSortedArray(i2, ARRAY_SIZE(i2))); // expect: 3 + printf("%d\n", createSortedArray(i3, ARRAY_SIZE(i3))); // expect: 4 +} diff --git a/create_sorted_arr_instr.py b/create_sorted_arr_instr.py new file mode 100644 index 0000000..b354c73 --- /dev/null +++ b/create_sorted_arr_instr.py @@ -0,0 +1,48 @@ +# 1649. Create Sorted Array through Instructions + +""" +given an integer array 'instructions', you are asked to create a sorted array +from the elements in 'instructions'. you start with an empty container +'nums'. for each element from left to right in 'instructions', insert it into +'nums'. the cost of each insertion is the minimum of the following: the +number of elements currently in 'nums' that are strictly less than +'instructions[i]', the number of elements currently in 'nums' that are +strictly greater than 'instructions[i]'. return the total cost to insert all +elements from 'instructions' into 'nums'. since the answer may be large, +return it modulo 10^9 + 7 +""" + + +class Solution(object): + def createSortedArray(self, instructions): + """ + :type instructions: List[int] + :rtype: int + """ + m = max(instructions) + arr = [0] * (m + 1) + + def update(x): + while x <= m: + arr[x] += 1 + x += x & -x + + def get(x): + res = 0 + while x > 0: + res += arr[x] + x -= x & -x + return res + + ans = 0 + for i, j in enumerate(instructions): + ans += min(get(j - 1), i - get(j)) + update(j) + return ans % (10**9 + 7) + + +if __name__ == "__main__": + obj = Solution() + print(obj.createSortedArray(instructions=[1, 5, 6, 2])) + print(obj.createSortedArray(instructions=[1, 2, 3, 6, 5, 4])) + print(obj.createSortedArray(instructions=[1, 3, 3, 3, 2, 4, 2, 1, 2])) |