CODEWITHSUNDEEP
algorithmsortingdata-structures
Eeshan
Eeshan

Reputation: 99

Given an array, sort it according to conditions on other values in the same array

This is a problem involving application of Data Structures and Algorithms. I was unable to solve it in a Geeks for Geeks Practice Test.

Problem:
There are 2 arrays of non whole numbers, A and B. A consists of people's heights. B of the numbers corresponding to each person in A, such that for every person i in A, exactly B[i] number of people with height >= A[i] should stand in-front of person i in A, after sorting A according to this condition.

We are supposed to arrange A in the given way.

Constraints:
1 <= N (number of people) <= 1000
1 <= A[i] <= 10000

Examples

  1. A = [3 2 1]
    B = [0 1 1]
    out = [3 1 2]
  2. A = [5 3 2 6 1 4]
    B = [0 1 2 0 3 2]
    out = [5 3 2 1 6 4]

Upvotes: 0

Views: 42

Answers (1)

Eeshan
Eeshan

Reputation: 99

def linsert(ans,elt,ind):
    for i in range(len(ans)):
        if ans[i] == None:
            ind -= 1
            if ind == 0:
                break
    return i
def arrange(a,b,n):
    ans = [None for i in range(n)]
    for i in range(n):
        a[i] = (a[i],i)
    a.sort(key = lambda x : x[0])
    for i in range(n):
        elt = a[i][0]
        ind = b[a[i][1]]
        ind = linsert(ans,elt,ind)
        ans[ind] = elt
    return ans

In the above code, the function arrange needs to be called for the final sorted arrangement.
We start with the smallest element, as pointed by @user3386109. We place it at posoition b[j] in an empty array ans, where j is index of the smallest number in a. We do this repeatedly, until all numbers are processed. In practice, this is done by first sorting A, then inserting at b[i] if it is empty, else looping over ans to find all empty locations where a number greater or equal can be placed, and then placing our number. Please feel free to optimize this if possible. Please feel free to translate this to other languages. If I were using C++, simply due to convinience, I would have simply used a min Heap of pair<int,int>(elt,i), where i is the position in the original unsorted array. Then, I would have popped the heap until it were empty, and placed elements in the same way I have above.

Due to the sorting in the solution, the cost is O(nlogn). Memory required is O(n), for the answer and indices both.

Upvotes: 1

Related Questions