Keep Distance for Identical elements

Analysis:

Think that you have an array with 2k length, so 2k spot to fill. You fill it 2 element at a time, with 2 identical elements with the rule described in the question. So it becomes a DFS(k level, every level use whats left over from previous level within 1-k, each level should also try out all remaining elements).

So we can use an k size array to store 1-k element, "swap" style dfs so that we dont have to use a Set to keep track of whats used and what not.

Complexity:

Time: O(N!)

Space:O(N)

Code:

package IdenticalNumberFill;

public class Solution {
    public int[] keepDistance(int k){ //solution starts here
        int[] returnArr = new int[2 * k];
        int[] rk = new int[k];
        for(int i = 1; i <= k; i++){
            rk[i-1] = i;
        }

        if(!dfs(returnArr, rk, 0)){
            return null;
        }

        return returnArr;
    }

    private boolean dfs(int[] ra, int[] rk, int level){
        if(level == rk.length){
            return true;
        }

        int emptyIndex = findFirstEmptyIndex(level, ra);

        for(int i = level; i < rk.length; i++){
            swap(level, i, rk);
            int otherIndex = emptyIndex + rk[level] + 1;

            if(otherIndex < ra.length && ra[otherIndex] == 0){
                ra[emptyIndex] = rk[level];
                ra[otherIndex] = rk[level];
                if(dfs(ra, rk, level + 1)){
                    return true;
                }
                ra[emptyIndex] = 0;
                ra[otherIndex] = 0;        
            }
            swap(level, i, rk);
        }
        return false;
    }

    private void swap(int a, int b, int[] rk){
        if(a == b){
            return;
        }
        int temp = rk[a];
        rk[a] = rk[b];
        rk[b] = temp;
    }

    private int findFirstEmptyIndex(int level, int[] ra){
        if(level == 0){
            return 0;
        }

        for(int i = level; i <= ra.length; i++){
            if(ra[i] == 0){
                return i;
            }
        }
        return 0;
    }
}