CODEWITHSUNDEEP
algorithmdata-structurescomputer-science
Elimination
Elimination

Reputation: 2723

sort two arrays in O(n) (time and space)

Given two (possibly unsorted) arrays, A and B and the operation swap(A, B, i) which swaps the elements A[i] and B[i], you need to return the minimal number of swaps so the two arrays are strictly increasing (or -1 if impossible)

I came up pretty fast with a greedy solution (I can attach the code if you want) but apparently it doesn't yield the correct answer in some cases (which I'm unaware of).

Why is the greedy approach not good enough? What could be an alternative approach to reach the minimum number of swaps?

EDIT:
Here's my code

def solution(A, B):
    n = len(A)
    swaps = 0
    for i in range(1, n):

        if A[i] > A[i - 1] and B[i] > B[i - 1]:
            continue

        if A[i] < A[i - 1] and B[i] < B[i - 1]:
            return -1
        elif A[i] < A[i - 1]:
            if B[i - 1] < A[i]:
                A[i], B[i] = B[i], A[i]
                swaps += 1
            else:
                return -1
        else:
            # B[i] < B[i - 1]
            if A[i - 1] < B[i]:
                A[i], B[i] = B[i], A[i]
                swaps += 1
            else:
                return -1


    return swaps

# test
assert(solution([5, 3, 7, 7, 10], [1, 6, 6, 9, 9]))

Upvotes: 0

Views: 59

Answers (1)

amrender singh
amrender singh

Reputation: 8239

You can use DP to achieve this:

One approach can be: For each pair of A[i] and B[i], we can choose to swap or not. So we define two dp arrays, keep[i] means if we don't swap A[i] and B[i], what's the min number of swaps. swap[i] is the min number of swaps if we swap A[i] and B[i].

  • A[i] > A[i -1] && B[i] > B[i - 1], if we choose to keep, we should keep the previous i - 1 elements. So keep[i] = keep[i - 1] If we choose to swap, in order to maintain the sequencing order, we must swap the previous i - 1 th element. So swap[i] = swap[i - 1] + 1;

  • A[i] > B[i - 1] && B[i] > A[i - 1] If we choose to keep, keep[i] = Math.min(keep[i], swap[i - 1]) If we choose to swap, swap[i] = Math.min(swap[i], keep[i - 1] + 1)

  • For case such as A[i] < B[i - 1], return -1

Time complexity : O(n)

Upvotes: 2

Related Questions