How to find an order of list such that its elements are greater than the corresponding elements in second list. I have to maximize such number

user_8229265 0
Viewed 166

It fails one test case out of 11.

Given 2 lists, I have to find order in 1st list such that the corresponding elements in second list are of less magnitude.

So for example: If list 1 has elements [10, 40, 30] and list 2 has elements [20,5,50] Here only 40 in list 1 is greater than corresponding 5 in list 2. A correct order in list 1 to maximize such order would be [30,40,10], now 2 elements are greater than the corresponding elements in list 2.

Note that it should be strictly greater.

My approach:

  1. So what I did was create a list of tuples, such that each tuple represents a number from the list and the list it belongs to.
  2. And then I sorted this list based on the numbers in the tuples.
  3. Iterate through the list and every pair of tuples, if say element in list 1 is t1 and element in list 2 is t2, then if t1 occurs after t2 then we have a match (Since this t1 would be greater than t2, (I added a case when there will be equality, in this case it will treat is simply as t1 = t2 and continue looping).
  4. Update the index parameters and the count for a successful match.
    def main(t1,t2):
        tn = []

        # Make a list of tuples such that each tuple is of the form (number, list it belongs to)
        # so if a number belongs to t1, say 5. So the tuple will look like (5,t1)

        for i,j in zip(t1,t2):
                tn.append((i,'t1'))
                tn.append((j,'t2'))

        # Sort this tuple on the basis of numbers
        tn = sorted(tn, key = lambda a: a[0]) 
        wins = 0

        t1_ind = 0
        t2_ind = 0

       # Implementation of point 3 from here
        while True:
            if t1_ind > t2_ind: # The t1 index should always be greater than t2 index for a match
                if tn[t2_ind][1] == 't2':

                    # An edge case for equal numbers, these won't be greater even if t1 occurs after t2

                    if tn[t1_ind][1] == 't1' and tn[t1_ind][0] != tn[t2_ind][0]: 
                        # We have a successful match here and hence we update the win count
                        wins += 1
                        t2_ind += 1  # Move t2's index ahead as we have a match
                    t1_ind += 1  # In any case if we find t2 and do an analysis, t1's index should move ahead
                else:
                   # if we don't find t2 and t2_index, then move ahead
                    t2_ind += 1
            else:
            # Update index of t1, as t1's index is <= t2's index now
                t1_ind += 1
            if t1_ind >= len(tn) - 1:
                break

        return wins

Its throwing error and I can't figure out what is wrong. It is passing 10/11 test cases. There is nothing shown about that 1 edge case, apart from the fact that it took 4 seconds to run and fails

This goes in O( n Log n). If there is a better approach or optimization possible then I would like to know.

I found a similar post, but it's in C++ and there is no explanation so I can't make sense of the logic. Similar Problem In C++

Edit: Some extra points about my approach as some suggest that the approach is not directly intuitive.

For 2 lists, the algorithm is merging them and sorting them. After merging and sorting, for example, The order of elements is:

1 3 4 5 5 6....

So now, we store which element belongs to which list: (l1 for list 1 and l2 for list2)

l1 l2 l1 l1 l2 l1 ....

We now start iterating from left, and look for elements l1 occurring after l2, the numbers corresponding to l1 will definitely be greater than the number corresponding to least unmatched l2, we greedily make such pairs and increase the count for each match, marking each matched pair.

list optimization sorting algorithm python
1 Answers
Sort both lists A and B (O(nlogn))

Make indices Aidx = 0, Bidx = 0

While A[Aidx] <= B[Bidx] increment Aidx

When A[Aidx] becomes larger than B[Bidx] - increment "wins" and increment both indices

Repeat until A end  (O(n) stage)

Code

import random
A = [random.randrange(1, 100) for _ in range(random.randrange(3, 10))]
B = [random.randrange(1, 100) for _ in range(random.randrange(3, 10))]
A.sort()
B.sort()
wins = 0
ia = 0
ib = 0
while ia < len(A) and ib < len(B):
    while ia < len(A) and A[ia] <= B[ib]:
        ia += 1
    if ia < len(A):
        wins += 1
        ia += 1
        ib += 1
print(A)
print(B)
print(wins)

[4, 5, 22, 30, 43, 55, 78, 80]
[19, 54, 85, 95]
2

[16, 17, 23, 26, 29, 34, 48, 98]
[6, 43, 65]
3
user_8444160
Related