One test case is failing. Please help me find the error.
Also, can we make it more space-efficient?
Problem in Alpha score
hello @abhir26
checking ur code.
this is O(n) space approach using merge sort.
In this problem, we need to find out for every number at index m in the given array the sum of all the numbers which appears at an index i where i < m and array[i] < array[m]. And add all these sums to the final answer
To solve this problem in a best-optimized way need to think something better than O(n*n). Here we will apply the concept of merge sort problem.
In merge sort, we divide the array into subarrays recursively until there are just 2 elements in a subarray. We then arrange the subarray in sorted order and merge it with other subarrays.
Consider 2 subarrays arr[l…mid-1] and arr[mid…r] in the merge function which are sorted seperately and are ready to merge
i varies from l to mid-1
j varies from mid to r
i<j always
Let sum be the variable which holds the sum of all the numbers previously seen on the stairs which are smaller than the present number.
if(arr[i]<arr[j])
arr[i] comes before arr[j] in the input array and arr[i] is less than arr[j]. So we have to add arr[i] to sum.
Since arr[i]<arr[j], arr[i]<(arr[j+1], arr[j+2],….,arr[r]) because the subarrays to be merged are sorted.
So on the whole (r-j+1) times of arr[i] is added to the sum.