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

Question

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

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

@user3386109 Could you please optimize the below posted solution if possible. Also, I feel kind of silly for not solving this in the test ; ) — Eeshan
– Eeshan, Commented May 21, 2022 at 10:04

Eeshan · Accepted Answer · 2022-05-21 14:31:12Z

1

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.

edited May 21, 2022 at 14:31

answered May 21, 2022 at 10:02

Eeshan

995 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user3386109 Over a year ago

Well done, you solved it! Note that python does have a min Heap module called heapq that you could use, but a heap won't change the O(nlogn) complexity or O(n) space requirements. The actual complexity is O(n^2) because of the way linsert works. So that's where you would need to focus your efforts if you want improved performance. For general tips from python experts, try posting your code on code review.

Eeshan Over a year ago

@user3386109 Cool, will look into code review

Collectives™ on Stack Overflow

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

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related