Each of 2 arrays A, B can swap maximum once so that A[i] <= B[i]

Viewed 19

I can't think of a solution with this question about 2 arrays:

  • Given 2 arrays A and B have the same size (let's say N)
  • Each array can swap 2 elements maximum once to satisfy: A[i] <= B[i] with 0<=i<N
  • Print "Yes", "No" if there is a solution

Example:

1: Yes 
7 5 3 2 
5 4 8 7 
-> 
(3) 5 (7) 2 
 5 (7) 8 (4)

Here is something i tried to do:

def swapPositions(list, pos1, pos2):
     
    list[pos1], list[pos2] = list[pos2], list[pos1]
    return list

def isSatisfy(n, a, b):
    #add wrong positions
    pos = []
    for i in range(0,n):
        if (a[i] > b[i]): 
            pos.append(i)

        if (len(pos) > 2): 
            return False
    
    if (len(pos) == 0):
        return True
    elif (len(pos) == 1):
        #try swap in a first
        for i in range(0, n):
            if (i == pos[0]): continue
            if (a[i] >= b[pos[0]] and a[pos[0]] >= b[i]):
                return True
        
        #fail
        #swap min to wrong pos in a
        min = -1
        for i in range(0,n):
            if (i == pos[0]): continue
            if (a[i] <= a[pos[0]] and a[pos[0]] <= b[i]):
                min = i
        if (i!=-1): swapPositions(a,pos[0],min)
        #swap in b
        for i in range(0, n):
            if (i == pos[0]): continue
            if (b[i] >= a[pos[0]] and b[pos[0]] >= a[i]):
                return True
        return False
    elif (len(pos) == 2):
        #swap once each array
        d1 = 99
        min1 = -1
        for i in range(0,n):
            if (i==pos[0] or i==pos[1]): continue
            if (a[i]<=b[pos[0]] and a[pos[0]]<=b[i]):
                if (d1 > abs(a[i]-b[i])):
                    min1 = i
                    d1 = abs(a[i]-b[i])

        if (min1 == -1):
            return False
        
        swapPositions(a, pos[0], min1)

        for i in range(0,n):
            if (i==pos[1]): continue
            if (b[i] >= a[pos[1]] and b[pos[1]] >= a[i]):
                return True
        return False
0 Answers
Related