class RearrangeInputToTarget {

	public static void rearrange(int[] input, int[] target) {
		assert (input.length == target.length);

		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		buildIndex(input, map);
		int zeroIndex = com.github.kowshik.bigo.common.ArrayUtils.findIndex(input, 0);
		int numMoves = 0;

		while (numMoves < input.length) {
			// zero has reached its final location. So we displace it
			// temporarily so that we can continue putting other elements in
			// their final locations.
			if (target[zeroIndex] == 0) {
				int outOfOrderIndex = findFirstOutOfOrderIndex(input, target);
				if (outOfOrderIndex == -1) {
					// All elements including '0' are in their final locations.
					return;
				}

				map.put(input[outOfOrderIndex], zeroIndex);
				// We need to update the index because we are going to modify
				// the original location of the value in input[outOfOrderIndex].
				com.github.kowshik.bigo.common.ArrayUtils.swap(input, zeroIndex, outOfOrderIndex);
				zeroIndex = outOfOrderIndex;

			} else {
				// Swap zero with what should actually be in zero's location
				// in the target array.
				int nextZeroIndex = map.get(target[zeroIndex]);
				com.github.kowshik.bigo.common.ArrayUtils.swap(input, zeroIndex, nextZeroIndex);
				zeroIndex = nextZeroIndex;
				numMoves++;
			}
		}

	}

}