CODEWITHSUNDEEP
arraysalgorithmsortinglanguage-agnostictuples
iamogbz
iamogbz

Reputation: 99

Minimum number of "swaps" needed to sort two arrays

This is a challenge question I've been having problems solving optimally (my attempt with failure analysis).

Given two arrays of equal length A = [1,8,12,11], B = [7,3,10,15], sort them in ascending order by only performing swaps.

A swap means replacing element at index i in A with the corresponding B element and vice versa.

The above example can resolve to A = [1,3,12,15], B = [7,8,10,11] or A = [1,3,10,11], B = [7,8,12,15] both with 2 swaps. However there are cases where solutions have different number of swaps, here the minimum is chosen and if it is not possible, return -1

How would I go about solving this perfectly in O(N)?

Upvotes: 2

Views: 1482

Answers (1)

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

Reputation: 23955

Let f(i, swap) 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. Then:

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
)

Upvotes: 6

Related Questions