You have an array like ar[]= {1,3,2,4,5,4,2}.
You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Algorithm :
1)Conside original array a[]
2)Construct a sorted list with the array elements(O(nlogn))
3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search.
-position in the sorted list returns the number of elements in the less than the current element on right side.
-after remove the current element from the sorted list.
PS: list is preferred datastructure because there are so many insertion and deletion operations.
You need to create another array ar_low[] such that ar_low[i] = number of elements lower than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}
Algorithm :
1)Conside original array a[]
2)Construct a sorted list with the array elements(O(nlogn))
3)Traverse across all elements of the original array 'a' and find it's position(right occurence) in the sorted list using binary search.
-position in the sorted list returns the number of elements in the less than the current element on right side.
-after remove the current element from the sorted list.
PS: list is preferred datastructure because there are so many insertion and deletion operations.
public static int[] createLowArray(int[] a) {
if (a == null || a.length == 0)
return null;
int length = a.length;
int[] minArray = new int[length];
// constructing a list from the array elements
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < a.length; i++) {
list.add(a[i]);
}
// sort the array 1 2 2 3 4 4 5
Collections.sort(list);
// traverse across all elements of the array and do the binary search in
// the sorted list for it's position
// after getting position(right occurrence),remove the element from the sorted list
for (int i = 0; i < length; i++) {
int pos = Collections.binarySearch(list, a[i]);
// getting the right occurrence of the element position
// we can iterate through elements to modify binary search to return
// right occurrence
while (pos < list.size()-1 && list.get(pos + 1) == list.get(pos)) {
pos++;
}
minArray[i] = pos;
list.remove(pos);// remove the element from the sorted list
}
return minArray;
}
Note : Position count starts from 0.
ex: {1,2,3,4} ...position of '1' is zero............
In the below approach,we are checking element position in the modified list(after deletion operation in the previous iteration).
given array is : ar[]= {1,3,2,4,5,4,2}.
construct a list with array elements and sort it.Now list contains :1,2,2,3,4,4,5
Now traverse through array elements from i=0 to n-1(start to end)
store result in result[] array.
list is 1-2-2-3-4-4-5
for i=0, a[0]=1,search for a[0] position in the list(right occurrence).a[0]=1 position in list is '0'
add '0' to result.===>result[0]=0;
remove the element a[0] from the list.now list contains 2-2-3-4-4-5
for i=1,a[1]=3,search for a[1] position in the list(right occurence).a[1]=3 position in list is '2'
add '2' to result====>result[1]=2
remove the element a[1] from the list.now list contains 2-2-4-4-5
for i=2,a[2]=2,search for a[2] position in the list(right occurence).a[2]=2 position in list is '1'
add '1' to result====>result[2]=1
remove the element a[2] from the list.now list contains 2-4-4-5
for i=3,a[3]=4,search for a[3] position in the list(right occurence).a[3]=4 position in list is '2'
add '2' to result====>result[3]=2
remove the element a[3] from the list.now list contains 2-4-5
for i=4,a[4]=5,search for a[4] position in the list(right occurence).a[4]=5 position in list is '2'
add '2' to result====>result[4]=2
remove the element a[4] from the list.now list contains 2-4
for i=5,a[5]=4,search for a[5] position in the list(right occurence).a[5]=4 position in list is '1'
add '1' to result====>result[5]=1
remove the element a[5] from the list.now list contains 2
for i=6,a[6]=2,search for a[6] position in the list(right occurence).a[6]=2 position in list is '0'
add '0' to result====>result[6]=0
remove the element a[6] from the list.now list is empty.
resultant array contains :
from all conditions :
add '0' to result.===>result[0]=0;
add '2' to result====>result[1]=2
add '1' to result====>result[2]=1
add '1' to result====>result[3]=2
add '2' to result====>result[4]=2
add '1' to result====>result[5]=1
add '0' to result====>result[6]=0
expected result {0,2,1,2,2,1,0}
actual result ==>{0,2,1,2,2,1,0}
If we use java arraylist,it will find the element position in O(logn) time complexity using binarysearch.
Arraylist implements RandomAccess marker interface which facilitate it to find in O(long)
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access).
But problem of using arrayList is,when ever an element is removed from the list,all subsequent has to be moved.
If the given array is already sorted,it will reach worst case O(n*n).Because we need to move all elements as we find element to be removed at starting position.
Simple approach : Start with two loops,for each element count the number of minimum elements which are less than the element
Simple approach : Start with two loops,for each element count the number of minimum elements which are less than the element
