Minimum swaps required to organize all elements within K

Question

I recently came across this coding interview question, and can't seem to find an answer to it. Here's the question.

Given an integer array, write a function that returns the minimum swaps required to organize the array so that adjacent elements all have an absolute difference less than or equal to K. Swaps can be of any two array elements, not necessarily adjacent.

For example,

public static void main(String[] argv) {
    int[] arr1 = new int[]{10, 40, 30, 20};
    int K = 20;
    getMinimumSwap(arr1, K); // should return 1
}

The reason why it should return 1 is because by swapping 40 and 30, the array would satisfy the given statement that all adjacent elements should be within 20 of one another.

I did try to google for answers, and I thought I found some answer in other algorithm-helper sites, but was unable to get the answers for my questions. The failed test case had an array of 3, 7, 2, 8, 6, 4, 5, 1 and K = 3 which should return 2.

The only constraint I can remember is that the length of the input array is 1 <= n <= 8.

Answer 1

I would tackle this as a graph searching problem.

Problem definition

To tackle this as a graph search problem, we first need to define the states of our system. In out case, the states will be the sequence of the numbers.

Solution proposal

After defining the states, every graph search problem can do the job, but since you want the least amount of swaps, we will use BFS.

The following was implemented in python for convenience but can be done in java as well.

First we will write a help function which given a sequence of numbers, returns all the possible 1-swaps of that sequence:

def get_swaps(sequence):
    swapps = collections.deque([])
    ii = 0
    jj = 1
    done = False
    while not done:
        temp_seq = sequence.copy()
        temp     = sequence[jj]
        temp_seq[jj] = sequence[ii]
        temp_seq[ii] = temp
        swapps.append(temp_seq)
        if jj < len(sequence)-1:
            jj += 1
        elif ii < len(sequence)-2:
            ii += 1
            jj = ii + 1
        else:
            done = True
    return swapps

Please note that this is not written optimally but it does the trick.

Now we can implement a BFS algorithm as follows (read more on BFS and DFS here)

def findSwap(sequence, k):
    state_queue = collections.deque([]) # Pending states which have not been explored yet
    visited     = set()
    state    = (sequence, 0)  # Starting state, starting sequence and 0 swapps
    min_diff = max([abs(sequence[1:][ii] - sequence[:-1][ii]) for ii in range(len(sequence)-1)])
    found    = True
    while min_diff > k:
        curr_seq   = state[0]
        curr_count = state[1]
        # Getting all swaps possible
        swaps = get_swaps(curr_seq)
        # Adding to the queue and to visited set all the unvisited states
        for next_state in swaps:
            None if tuple(next_state) in visited else state_queue.append((next_state, curr_count+1)), visited.add(tuple(next_state))
        # popping next state from the queue
        try:
            state = state_queue.popleft()
            curr_seq = state[0]
            min_diff = max([abs(curr_seq[1:][ii] - curr_seq[:-1][ii]) for ii in range(len(curr_seq) - 1)])
        except IndexError:
            found = False
            break
    if found:
        return state[1]
    else:
        return -1

Explanation

In each states we:

1. Generate the possible next states which are the 1-swap permutations.
2. For each next-state candidate, we check if we already visited that state and if we did not visit the state, we add the next state to the state queue.

After finishing the check for all possible next states, we pop the next state from the queue and check the max difference. If the max diff is lees then k we are done. If the queue is empty, we searched through all the state space and did not find a solution, and in this case we will return -1.

Note that in addition to the states we carry the number of swaps done from the original state to this state in the tuple.

When setting your test array we get:

a = [3,7,2,8,6,4,5,1]
print(findSwap(a, 3))  # 2, as expected