# 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`

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.