CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
adarsh
adarsh

Reputation: 142

Relative sorting with minimum possible swaps

Problem Statement: There are two arrays given A and B. We need to print the number of minimum swaps b/w i'th elements such that the both array will become strictly increasing.

if arrays are already strictly increasing then print 0. if arrays are not possible to become strictly increasing then print -1.

only ith element A can be swapped with ith element of B.

There is a possibility that the elements may occur more than once.

eg:
Input:

t=7
A=1 2 3 8 9 7 8
B=1 2 3 4 5 10 11

output
2

By swaping 7 and 8 with 10 & 11. OR by swaping 8 and 9 with 4 & 5.

My code Python3:


t=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

count=0
for i in range(1,t):
    if(A[i]-A[i-1]<=0):
        if(A[i]<B[i]):
            if(B[i-1]<A[i]):
                A[i],B[i]=B[i],A[i]
                count=count+1
for i in range(1,t):
    if(B[i]-B[i-1]<=0):
        if(B[i]<A[i]):
            if(A[i-1]<B[i]):
                A[i],B[i]=B[i],A[i]
                count=count+1   
ans=False
for i in range(1,t):
    if(A[i]-A[i-1]<=0):
        ans=True
        break
    if(B[i]-B[i-1]<=0):
        ans=True
        break   
if(ans):
    print(-1)
else:
    print(count)

My code Explanation: I am checking 1st whether in Array A it is strictly increasing or not. If no: then checking is ith element of B is greater than the current if yes it is greater than ith element of A then one more check if (i-1)th element of B is smaller or not if smaller than swap the element of A.

similar method will be applied to B.

Last check A & B are strictly increasing after swapping. if yes print count else print -1.

Any test case where My code will fail or is it a correct approach? Any other approach to solve this problem?

Upvotes: 2

Views: 262

Answers (2)

Huy Nguyen
Huy Nguyen

Reputation: 2061

Actually, your code should be refactor with a few method. It will be easily to read. I recommend few simple method: 

checkIncrement(list, index) : boolean return true if value at index > index -1 
swap(list1,list2,index) : swap value
getWrapCount(list1,list2) : return number swap

getWrapCount method: pseudo-code

    size= min_size(list1,list2);
    swapCount=0    
    for index: 1-> size
            if !checkIncrement(list1,index) or !checkIncrement(list2,index)
                swap(list1,list2,index);
                if !checkIncrement(list1,index) or !checkIncrement(list2,index) return -1;//not possible to become strictly increasing then  -1.
                swapCount++;
return (swapCount,size-swapCount);

The complexity will be O(N) in worst case and O(1) in best case.

Upvotes: 2

גלעד ברקן
גלעד ברקן

Reputation: 23955

Your code will fail for

A = [4, 2, 3]
B = [1, 5, 6]

returning 2 when the correct minimum number of swaps is 1.

We can form a recurrence f(i, swap) to represent the minimum number of swaps achievable up to index i where swap is a boolean representing if the elements at index i are to be swapped:

f(i, false) = min(
  f(i - 1, false) if A[i] > A[i-1] and B[i] > B[i-1] else Infinity,

  f(i - 1, true) if A[i] > B[i-1] and B[i] > A[i-1] else Infinity
)

f(i, true) = min(
  1 + f(i - 1, false) if B[i] > A[i-1] and A[i] > B[i-1] else Infinity,

  1 + f(i - 1, true) if B[i] > B[i-1] and A[i] > A[i-1] else Infinity
)

(Time complexity O(n).)

Upvotes: 1

Related Questions