Suppose we have two arrays A[n] and b[n], the goal is to compare every element in A to elements in B. Then return a list result[n] that records the number of each element in A that is larger than the elements in B.
For example,
A = [38, 24, 43, 3], B = [9, 82, 10, 11]
Since 38 is larger than 9, 10 and 11, so result[0] is 3.
Then result is [3, 3, 3, 0].
It will be the best if you can provide some pseudocode.
Thank you.
You can perform the above algorithm in O(nlogn) complexity where n is the length of array A and array B as given in the question.
Algorithm
1. Sort both the arrays A and B, this will take O(nlogn) time complexity.
2. Take two pointers i and j, initialize both of them to 0. we will use i for array A and j for B.
3. Create a result array res of size n.
4. Start a while loop
while(i<n && j<n) {
if(A[i] > B[j]) {
j++;
} else {
res[i] = j+1;
i++;
}
}
5. while(i<n) {
res[i] = n;
}
This step is for the case where all elements in A are bigger than all elements in B.
At the end you will have res
array ready with the answer.
Overall time complexity - O(nlogn)
.
Hope this helps!
Both lists need to be sorted ascending for this to work.
Sorting costs O(log n). And big-O arithmetic means doing it twice is still O(n log n)
. I'm going to assume they are already sorted. The remaining work below doesn't affect the big-O cost.
Have an index to the B
array called indexB
, value zero (my pseudocode will use zero-based indexing). And indexA
for A
also starting at zero.
indexA=0
For each indexB from 0 to B.Length-1
While indexA < A.Length and the value at `A[indexA]` is less than or equal to the value at `B[indexB]`
Set the `result[indexA]` to be `indexB`
Increment `indexA`
Endwhile
Endfor
After that, all of the remaining items in the result
from indexA
onward are bigger than all the items in B
, so set the rest of them to B.Length
.