Nearest permutation to given array

  • A+
Category:Languages

Question

I have two arrays of integers A[] and B[]. Array B[] is fixed, I need to to find the permutation of A[] which is lexiographically smaller than B[] and the permutation is nearest to B[]. Here what I mean is:

for i in (0 <= i < n) abs(B[i]-A[i]) is minimum and A[] should be smaller than B[] lexiographically.

For Example:

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

So,possible nearest permutation of A[] to B[] is

A[]={7,3,1,6,5} 

My Approach

Try all permutation of A[] and then compare that with B[]. But the time complexity would be (n! * n)

So is there any way to optimize this?

EDIT

n can be as large as 10^5

For better understanding Nearest permutation to given array

 


First, build an ordered map of the counts of the distinct elements of A.

Then, iterate forward through array indices (0 to n−1), "withdrawing" elements from this map. At each point, there are three possibilities:

  • If i < n-1, and it's possible to choose A[i] == B[i], do so and continue iterating forward.
  • Otherwise, if it's possible to choose A[i] < B[i], choose the greatest possible value for A[i] < B[i]. Then proceed by choosing the largest available values for all subsequent array indices. (At this point you no longer need to worry about maintaining A[i] <= B[i], because we're already after an index where A[i] < B[i].) Return the result.
  • Otherwise, we need to backtrack to the last index where it was possible to choose A[i] < B[i], then use the approach in the previous bullet-point.
    • Note that, despite the need for backtracking, the very worst case here is three passes: one forward pass using the logic in the first bullet-point, one backward pass in backtracking to find the last index where A[i] < B[i] was possible, and then a final forward pass using the logic in the second bullet-point.

Because of the overhead of maintaining the ordered map, this requires O(n log m) time and O(m) extra space, where n is the total number of elements of A and m is the number of distinct elements. (Since m ≤ n, we can also express this as O(n log n) time and O(n) extra space.)


Note that if there's no solution, then the backtracking step will reach all the way to i == -1. You'll probably want to raise an exception if that happens.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: