(Search in Rotated Sorted Array)

Suppose a sorted array is rotated at some pivot unknown to you beforehand (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.

Thoughts:
This is a modified version of binary search. Each time we half the array, and determine which part is sorted (there must be at least one of them). We then check if the target falls in the sorted part, we then apply the original version of binary search to it. Otherwise we recursively or iteratively go to the other half.

Code (Java):

public class Solution {
    public int search(int[] A, int target) {
        int low = 0;
        int high = A.length - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(target == A[mid])
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else { // right part sorted
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
}

Code (C++):

class Solution {
public:
    int search(int A[], int n, int target) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(A[mid] == target)
                return mid;
            if(A[low] <= A[mid]) { // left part sorted
                if(A[low] <= target && target < A[mid])
                    high = mid - 1;
                else
                    low = mid + 1;
            } else {
                if(A[mid] < target && target <= A[high])
                    low = mid + 1;
                else
                    high = mid - 1;
            }
        }
        return -1;
    }
};

Finding the 1st missing positive int in an array (First Missing Positive)

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Thoughts:
The idea is simple. What is the most desired array we want to see? Something like [1,2,3] then we know 4 is missing, or [1, 8, 3, 4] then we know 2 is missing. In other word, “all the numbers are in their correct positions”. What are correct positions? For any i, A[i] = i+1. So our goal is to rearrange those numbers (in place) to their correct positions. We then need to decide how to arrange them. Let’s take the [3, 4, -1, 1] as an example. The 1st number, 3, we know it should stay in position 2. So we swap A[0] = 3 with A[2]. We then get [-1, 4, 3, 1]. We can’t do anything about -1 so we leave it there. The 2nd number, 4, we know it should sit in A[3]. So we swap A[1] = 4 with A[3]. We then get [-1, 1, 3, 4]. Now 1 should stay in A[0], so we keep swapping and we get [1, -1, 3, 4]. Notice now every positive number is staying in their correct position (A[0]=1, A[2]=3 and A[3]=4). We then need one more scan to find out 2 is missing.

Code (Java):

import java.util.HashSet;
public class Solution {
    public int firstMissingPositive(int[] A) {
        for(int i = 0; i < A.length; ++i) {
            while(A[i] != i + 1) {
                if(A[i] <= 0 || A[i] > A.length || A[i] == A[A[i]-1])
                    break;
                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        
        for(int i = 0; i < A.length; ++i)
            if(A[i] != i + 1)
                return i + 1;
        return A.length + 1;
    }
}

Code (C++):

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for(int i = 0; i < n; ++i) {
            while(A[i] != i + 1) {
                if(A[i] <= 0 || A[i] > n || A[i] == A[A[i]-1])
                    break;
                int temp = A[i];
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        for(int i = 0; i < n; ++i)  
            if(A[i] != i+  1)
                return i + 1;
        return n + 1;
    }
};

Find largest 1M numbers in 1B numbers

Describe an algorithm to find the largest 1 million numbers in 1 billion numbers. Assume that the computer memory can hold all one billion numbers.

Thoughts:
We can certainly sort those numbers and return the last 1 million of them. That takes O(n\log n).
If we think about it, we actually do not need to sort them. After all, we just need the largest 1 million numbers, in whatever orders. Therefore we can sort of “partially” sort the numbers and try to find the parts that we need. To do this, we get inspiration from Quicksort, where we get two partitions around pivot during each run:

[elements < pivot][elements >= pivot]

For simplicity, Let us denote the number of elements in the right part as m.
If m is exactly equal to 1 million, we have found the largest 1 million numbers!
If m is larger than 1 million, we need to keep looking for the 1 million numbers, but in the left part of the array this time. We can do this in a recursive way.
If m is less than 1 million, we first remember those m numbers and then we search for the largest (1 million – m) numbers in the left part of the array. Again, recursion here.
Using the random pivot choosing approach, this algorithm takes O(n) time complexity and it does not need any additional space since we can do the partition in place.

Codes:

	public static int quickPartition(int[] array, int low, int high) {
		if (high <= low)
			return -1;

		// randomly choose a pivot
		int index = new Random().nextInt(high - low + 1) + low;
		int pivot = array[index];

		// swap the pivot to the front
		int num = array[index];
		array[index] = array[low];
		array[low] = num;

		// partition as in Quicksort
		int L = low + 1;
		int R = high;

		while (R >= L) {
			while (R >= L && array[L] < pivot)
				L++;
			while (R >= L && array[R] >= pivot)
				R--;
			if (R >= L) {
				int temp = array[L];
				array[L] = array[R];
				array[R] = temp;
				L++;
				R--;
			}
		}

		// swap the pivot back to appropriate position.
		num = array[R];
		array[R] = array[low];
		array[low] = num;

		return R;
	}

	public static List<Integer> largestM(int[] numbers, int M, int low, int high) {
		// RIndex = index of pivot
		int RIndex = quickPartition(numbers, low, high);
		// mFound = # of the largest numbers
		int mFound = high + 1 - RIndex;

		List<Integer> results = new LinkedList<Integer>();

		if (mFound == M) { // Done!
			int i = RIndex;
			for (; i <= high; ++i)
				results.add(numbers[i]);
			return results;

		} else if (mFound > M) { // Keep looking
			// check if those mFound elements are actually the same
			boolean duplicates = true;
			for (int i = RIndex; i <= high; ++i) {
				if (numbers[i] != numbers[RIndex])
					duplicates = false;
			}

			if (!duplicates)
				return largestM(numbers, M, RIndex, high);
			else {
				// if they are the same, just return M duplicates of them
				for (int k = 0; k < M; ++k)
					results.add(numbers[RIndex]);
				return results;
			}
		} else { // Has found some, keep looking for the rest
			int i = RIndex;
			for (; i < numbers.length; ++i)
				results.add(numbers[i]);

			results.addAll(largestM(numbers, M - mFound, low, RIndex - 1));
			return results;
		}

	}

Find an element in a matrix whose rows and columns are sorted

Given a matrix in which each row and each column is sorted, write a method to find an element in it.

My initial thoughts:
We are kind-of doing a 2D binary search here. Each time we find the center of the matrix. If that is the element we are looking for, then return it. Notice that the center divide the matrix into four parts: upper-left, upper-right, bottom-left and bottom-right. If the element we are looking for is less than the center, then it cannot be in the bottom-right part, where every elements are even greater than the center. If the element we are searching is greater than the center, then it cannot be in the upper-left part. Hence, each time we approximately eliminate \frac{1}{4} of the entire matrix. Therefore we have the recursion: T(n)=3T(n/4)+O(1), whose solution is O(n)=n^{0.75}.

My initial codes:

	public static Pair<Integer> findInMatrix(int[][] data, int rowLow,
			int rowHigh, int colLow, int colHigh, int element) {
		if (rowLow > rowHigh || colLow > colHigh)
			return null;
		new LinkedList<Pair<Integer>>();
		int rowMid = (rowLow + rowHigh) / 2;
		int colMid = (colLow + colHigh) / 2;
		int mid = data[rowMid][colMid];
		if (mid == element)
			return new Pair<Integer>(rowMid, colMid);
		else if (element < mid) {
			Pair<Integer> topLeft = findInMatrix(data, rowLow, rowMid - 1,
					colLow, colMid - 1, element);
			if (topLeft == null) {
				Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
						colMid, colHigh, element);
				if (topRight == null) {
					Pair<Integer> bottomLeft = findInMatrix(data, rowMid,
							rowHigh, colLow, colMid - 1, element);
					return bottomLeft;
				} else
					return topRight;
			} else
				return topLeft;
		} else { // element > mid
			Pair<Integer> topRight = findInMatrix(data, rowLow, rowMid - 1,
					colMid + 1, colHigh, element);
			if (topRight == null) {
				Pair<Integer> bottomLeft = findInMatrix(data, rowMid + 1,
						rowHigh, colLow, colMid, element);
				if (bottomLeft == null) {
					Pair<Integer> bottomRight = findInMatrix(data, rowMid,
							rowHigh, colMid + 1, colHigh, element);
					return bottomRight;
				} else
					return bottomLeft;
			} else
				return topRight;
		}
	}

Solution:
This algorithm works by elimination. Every move to the left (–col) eliminates all the elements below the current cell in that column. Likewise, every move down eliminates all the elements to the left of the cell in that row.

	public static Pair<Integer> FindElem(int[][] mat, int elem, int M, int N) {
		int row = 0;
		int col = N - 1;
		while (row < M && col >= 0) {
			if (mat[row][col] == elem) {
				return new Pair<Integer>(row, col);
			} else if (mat[row][col] > elem) {
				col--;
			} else {
				row++;
			}
		}
		return null;
	}

Comments: Brilliant. Time complexity O(m+n).

Searching in a sorted array of strings with empty strings

Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

My initial thoughts:
The worst we can do is O(n) where we just do a linear search. I tried to do better in the sense that we do a binary search, however if we encounter “”, we have to exam both sides. In this way, worst case we still do a O(n) search but in average, it’s better off.

My initial codes:

	public static int findLocation(String[] array, int i, int j, String str) {
		int mid;
		while (i <= j) {
			mid = (i + j) / 2;
			if (array[mid].equals("")) {
				int leftIndex = findLocation(array, i, mid - 1, str);
				if (leftIndex == -1)
					return findLocation(array, mid + 1, j, str);
				else
					return leftIndex;
			} else {
				if (str.compareTo(array[mid]) == 0)
					return mid;
				if (str.compareTo(array[mid]) < 0)
					j = mid - 1;
				if (str.compareTo(array[mid]) > 0)
					i = mid + 1;
			}
		}
		return -1;
	}

Solution:

	public static int search(String[] strings, String str, int first, int last) {
		while (first <= last) {
			// Ensure there is something at the end
			while (first <= last && strings[last] == "") {
				--last;
			}
			if (last < first) {
				return -1; // this block was empty, so fail
			}
			int mid = (last + first) >> 1;
			while (strings[mid] == "") {
				++mid; // will always find one
			}
			int r = strings[mid].compareTo(str);
			if (r == 0)
				return mid;
			if (r < 0) {
				first = mid + 1;
			} else {
				last = mid - 1;
			}
		}
		return -1;
	}

	public static int search(String[] strings, String str) {
		if (strings == null || str == null)
			return -1;
		if (str == "") {
			for (int i = 0; i < strings.length; i++) {
				if (strings[i] == "")
					return i;
			}
			return -1;
		}
		return search(strings, str, 0, strings.length - 1);
	}

Comments:

  1. Worst case time complexity is still O(n) since in the worst case, you need to remove all the “”s.
  2. Covers the cases where the target we are looking for is indeed, empty string. Also some error conditions have been handled.

Search for an element in a rotated array

Given a sorted array of n integers that has been rotated an unknown number of times, give an O(logn) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)

My initial thoughts:
Using the idea of binary search, we can find the breakpoint (e.g. 1 in the input) of the array in O(\log n). Then we divide the original array into two sorted sub-arrays. We can then do regular binary search for both of them in O(\log n). So altogether we still have O(\log n) running time.

My initial codes:

	public static int find(int[] array, int search) {
		int i = 0;
		int j = array.length - 1;
		int mid;
		do {
			mid = (i + j) / 2;
			if (array[mid] < array[mid - 1])
				break;
			else {
				i = mid + 1;
			}
		} while (i <= j);

		int leftIndex = binarySearch(array, 0, 
				mid - 1, search);
		if (leftIndex != -1)
			return leftIndex;
		else
			return binarySearch(array, mid, 
					array.length - 1, search);
	}

	private static int binarySearch(int[] array, 
			int i, int j, int search) {
		int mid;
		do {
			mid = (i + j) / 2;
			if (array[mid] == search)
				return mid;
			else if (array[mid] < search) {
				i = mid + 1;
			} else {
				j = mid - 1;
			}
		} while (i <= j);
		return -1;
	}

Solution:

	public static int search(int a[], int l, int u, int x) {
		while (l <= u) {
			int m = (l + u) / 2;
			if (x == a[m]) {
				return m;
			} else if (a[l] <= a[m]) { // sorted sub-array
				// regular binary search
				if (x > a[m]) {
					l = m + 1;
				} else if (x >= a[l]) { // x might fall
					// before the smallest element
					u = m - 1;
				} else {
					l = m + 1;
				}
			} 
			// implicit condition: a[l] > a[m]
			else if (x < a[m]) // left part
				u = m - 1;
			else if (x <= a[u]) // right part
				l = m + 1;
			else
				u = m - 1;
		}
		return -1;
	}

Comments:
Need to consider all the possible relations of a[l], a[m], a[u] and x.