- A+

**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.

- 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

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.