bolts_and_nots_no_duplicates.java

import java.util.Arrays;
import java.util.Random;

public class Playground {

	public static Random r;
	
	public static int SIZE = 100000;
	public static int[] BASE = new int[SIZE];
	
	public static void main(String[] args) {
		r = new Random();
		
		for (int i = 0; i < SIZE; i++) {
			BASE[i] = i + 1;
		}
		
		int[] a = shuffle(BASE);
		int[] b = shuffle(BASE);

		matchRec(a, b, 0, SIZE - 1);
		System.out.println(didMatch(a, b));
	}
	
	// start: inclusive, end: inclusive
	public static void matchRec(int[] a, int[] b, int start, int end) {
		if (start >= end) {
			return;
		}
		
		int aPivot = generateRandomIndex(start, end);
		int matchedBIndex = -1;
		
		int low = start;
		int high = end;
		
		while (low < high) {
			while (low <= end && b[low] <= a[aPivot]) {
				if (a[aPivot] == b[low]) {
					matchedBIndex = low;
				}
				low++;
			}
			
			while (start <= high && a[aPivot] <= b[high]) {
				if (a[aPivot] == b[high]) {
					matchedBIndex = high;
				}
				high--;
			}
			
			if (high < low) {
				break;
			}
			swap(b, low, high);
		}
		if (low < matchedBIndex) {
			swap(b, low, matchedBIndex);
			matchedBIndex = low;
		} else if (matchedBIndex < high) {
			swap(b, matchedBIndex, high);
			matchedBIndex = high;
		}
		
		low = start;
		high = end;
		
		while (low < high) {
			while (low <= end && a[low] <= b[matchedBIndex]) {
				low++;
			}
			
			while (start <= high && b[matchedBIndex] <= a[high]) {
				high--;
			}
			
			if (high < low) {
				break;
			}
			swap(a, low, high);
		}
		if (low < aPivot) {
			swap(a, low, aPivot);
			aPivot = low;
		} else if (aPivot < high) {
			swap(a, high, aPivot);
			aPivot = high;
		}
		
		matchRec(a, b, start, aPivot - 1);
		matchRec(a, b, aPivot + 1, end);		
	}
	
	public static void printAB(int[] a, int[] b) {
		for (int i = 0; i < SIZE; i++) {
			System.out.printf("%d ", a[i]);
		}
		System.out.println();
		for (int i = 0; i < SIZE; i++) {
			System.out.printf("%d ", b[i]);
		}
		System.out.println();
	}
	
	public static boolean didMatch(int[] a, int[] b) {
		for (int i = 0; i < SIZE; i++) {
			if (a[i] != b[i]) {
				return false;
			}
		}
		return true;
	}
	
	public static int generateRandomIndex(int start, int end) {
		return r.nextInt(end- start + 1) + start;
	}
	
	public static int[] shuffle(int[] a) {
		int[] b = Arrays.copyOfRange(a, 0, SIZE);
		
		for (int i = 0; i < SIZE; i++) {
			int x = r.nextInt(SIZE);
			int y = r.nextInt(SIZE);
			swap(b, x, y);
		}
		return b;
	}
	
	public static void swap(int[] nums, int a, int b) {
		int temp = nums[a];
		nums[a] = nums[b];
		nums[b] = temp;
	}
}