4.4 Keep distance for identical elements

Given an integer k, arrange the sequence of integers [1, 1, 2, 2, 3, 3, ...., k - 1, k - 1, k, k], such that the output integer array satisfy this condition: Between each two i's, they are exactly i integers (for example: between the two 1s, there is one number, between the two 2's there are two numbers).

Assumption: k > 0

Corner case: if no such sequence, return null

Input: int k {1,1,2,2,3,3}

Output: int[]

Solution 1:

1. Use a array to check if the number has been used

2. if not used, change to false, call recursion

3. if used, check array[k - current number - 1] if it's current number.

4. k * 2 levels in the recursion tree, each level consider one position

5. states: one less element to consider after each level

public int[] keepDistance(int k) {
  int[] array = new int[2 * k];
  for (int i = 0; i < k; i++) {
    array[i * 2] = i + 1;
    array[i * 2 + 1] = i + 1;
  }
  boolean[] used = new boolean[k + 1]; //true if i is used once
  return helper(array, 0, used) ? array : null;
}

private boolean helper(int[] array, int index, boolean[] used) {
  //base case
  if (index == array.length) {
   return true;
  }

  for (int i = index; i < array.length; i++) {
    int cur = array[i];
    if (!used[cur] || (index > cur && array[index - cur - 1] == cur)) {
      swap(array, index, i);
      used[cur] = !used[cur];
      if (helper(array, index + 1, used) {
        return true;
      }
      swap(array, index, i);
      used[cur] = !used[cur];
    }
  }
  return false;
}

private void swap() {...}

Solution 2:

1. k levels, each level places one pair of numbers

2. states: depending on how many valid positions are left, reduce k after each level. At most 2k positions to consider

e.g. k = 3

index 0 1 2 3 4 5(2k - 1)

array x x x x x x

i i+4 →

public int[] keepDistance(int k) {
  int[] array = new int[2 * k];
  return helper(array, k) ? array : null;
}

private boolean helper(int[] array, int k) {
  //base case
  if (k == 0) {
    return true;
  }
  for (int i = 0; i < array.length - k - 1; i++) {
    if (array[i] == 0 && array[i + k + 1] == 0) {
      array[i] = k;
      array[i + k + 1] = k;
      if (helper(array, k - 1)) {
        return true;
      }
      array[i] = 0;	//reset position
      array[i + k + 1] = 0;
    }
  }
  return false;
}