4Sum

	public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
		if (num == null || num.length < 4)
			return new ArrayList<ArrayList<Integer>>();
		Arrays.sort(num);

		return genericSumSorted(num, target, 0, num.length, 4);
	}

	public ArrayList<ArrayList<Integer>> genericSumSorted(int[] num,
			int target, int offSet, int len, int numToSum) {
		int loopMax = len - numToSum + 1;
		ArrayList<ArrayList<Integer>> rv = new ArrayList<ArrayList<Integer>>();

		if (numToSum == 1) {
			for (int i = offSet; i < loopMax; i++) {
				if (num[i] == target) {
					ArrayList<Integer> newSet = new ArrayList<Integer>();
					newSet.add(num[i]);
					rv.add(newSet);
					break;
				}
			}
		} else {
			int lastValue = num[offSet] - 1;
			for (int i = offSet; i < loopMax; i++) {
				if (num[i] == lastValue)
					continue;
				lastValue = num[i];
				int newTarget = target - num[i];

				ArrayList<ArrayList<Integer>> sub = genericSumSorted(num,
						newTarget, i + 1, len, numToSum - 1);
				for (ArrayList<Integer> subDetail : sub) {
					subDetail.add(0, lastValue);
					rv.add(subDetail);
				}
			}
		}
		return rv;
	}

3Sum Closest

	public int threeSumClosest(int[] num, int target) {
		if (num == null)
			return target;

		int len = num.length;
		if (len < 3) {
			int sum = 0;
			for (int i = 0; i < len; i++)
				sum += num[i];
			return sum;
		}

		Arrays.sort(num);
		return findClosestSumSorted(num, target, 0, len, 3);
	}

	public int findClosestSumSorted(int[] num, int target, int offSet, int len,
			int numToSum) {
		int loopMax = len - numToSum + 1;
		if (numToSum == 1) {
			int prevBestValue = num[offSet];
			int prevDiff = Math.abs(target - num[offSet]);
			for (int i = offSet + 1; i < loopMax; i++) {
				int currentDiff = Math.abs(target - num[i]);
				if (currentDiff < prevDiff) {
					prevBestValue = num[i];
					prevDiff = currentDiff;
				} else if (currentDiff > prevDiff)
					break;
			}
			return prevBestValue;
		} else {
			int prevBestValue = 0, prevDiff = Integer.MAX_VALUE;
			int lastValue = num[offSet] - 1;
			for (int i = offSet; i < loopMax; i++) {
				if (lastValue == num[i])
					continue;

				lastValue = num[i];
				int newTarget = target - num[i];
				int findValue = findClosestSumSorted(num, newTarget, i + 1,
						len, numToSum - 1);
				int currentDiff = Math.abs(newTarget - findValue);
				if (currentDiff < prevDiff) {
					prevBestValue = num[i] + findValue;
					prevDiff = currentDiff;
				} else if (currentDiff > prevDiff)
					break;
			}
			return prevBestValue;
		}
	}

3Sum

	public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
		if (num == null || num.length < 3)
			return new ArrayList<ArrayList<Integer>>();
		Arrays.sort(num);
		return genericSumSorted(num, 0, 0, num.length, 3);
	}

	public ArrayList<ArrayList<Integer>> genericSumSorted(int[] num,
			int target, int offSet, int len, int numToSum) {
		int loopMax = len - numToSum + 1;
		ArrayList<ArrayList<Integer>> rv = new ArrayList<ArrayList<Integer>>();

		if (numToSum == 1) {
			for (int i = offSet; i < loopMax; i++) {
				if (num[i] == target) {
					ArrayList<Integer> newSet = new ArrayList<Integer>();
					newSet.add(num[i]);
					rv.add(newSet);
					break;
				}
			}
		} else {
			int lastValue = num[offSet] - 1;
			for (int i = offSet; i < loopMax; i++) {
				if (num[i] == lastValue)
					continue;
				lastValue = num[i];
				int newTarget = target - num[i];

				ArrayList<ArrayList<Integer>> sub = genericSumSorted(num,
						newTarget, i + 1, len, numToSum - 1);
				for (ArrayList<Integer> subDetail : sub) {
					subDetail.add(0, lastValue);
					rv.add(subDetail);
				}
			}
		}
		return rv;
	}

Longest Common Prefix

 public String longestCommonPrefix(String[] strs) {
  if (strs == null)
   return null;

  int len = strs.length;
  if (len == 0)
   return "";

  int shortStrIdx = 0;
  int shortStrLen = strs[0].length();
  for (int i = 1; i < len; i++) {
   int strLen = strs[i].length();
   if (strLen < shortStrLen) {
    shortStrIdx = i;
    shortStrLen = strLen;
   } else if (strLen == shortStrLen) {
    for (int j = 0; j < strLen; j++) {
     if (strs[shortStrIdx].charAt(j) != strs[i].charAt(j)) {
      shortStrLen = j;
      break;
     }
    }
    if (shortStrLen == 0)
     return "";
   }
  }

  for (int i = 0; i < len; i++) {
   if (i == shortStrIdx)
    continue;

   for (int j = 0; j < shortStrLen; j++) {
    if (strs[shortStrIdx].charAt(j) != strs[i].charAt(j)) {
     shortStrLen = j;
     break;
    }
    if (shortStrLen == 0)
     return "";
   }
  }

  return strs[shortStrIdx].substring(0, shortStrLen);
 }

Roman to Integer

 public int romanToInt(String s) {
  int rv = 0;
  int len = s.length();

  int currentDigit = 0;
  int prevValue = 0;
  for (int i = 0; i < len; i++) {
   char c = s.charAt(i);

   int currentValue = 0;
   switch (c) {
   case 'M':
    currentValue = 1000;
    break;
   case 'D':
    currentValue = 500;
    break;
   case 'C':
    currentValue = 100;
    break;
   case 'L':
    currentValue = 50;
    break;
   case 'X':
    currentValue = 10;
    break;
   case 'V':
    currentValue = 5;
    break;
   case 'I':
    currentValue = 1;
    break;
   }

   if (prevValue == 0) {
    currentDigit += currentValue;
    prevValue = currentValue;
   } else if (currentValue == prevValue) {
    currentDigit += currentValue;
   } else if (currentValue > prevValue) {
    rv += currentValue - currentDigit;
    prevValue = 0;
    currentDigit = 0;
   } else {
    rv += currentDigit;
    prevValue = currentValue;
    currentDigit = currentValue;
   }
  }

  rv += currentDigit;
  return rv;
 }

Integer to Roman

 public String intToRoman(int num) {

  String[][] romanStr = {
    { "", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX" },
    { "", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC" },
    { "", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM" },
    { "", "M", "MM", "MMM" } };

  int counter = 0;
  StringBuffer sb = new StringBuffer();

  while (num > 0) {
   int digit = (num % 10);
   num /= 10;
   sb.insert(0, romanStr[counter++][digit]);
  }

  return sb.toString();
 }

Container With Most Water

 public int maxArea(int[] height) {
  int rv = 0;
  int iLen = height.length - 1;

  for (int i = 0; i < iLen; i++) {
   int heightMax = 0;
   int iHeight = height[i];
   for (int j = iLen; j > i; j--) {
    if (height[j] > heightMax)
     heightMax = height[j];
    else
     continue;

    int minHeight = (iHeight > heightMax) ? heightMax : iHeight;
    int area = (j - i) * minHeight;

    if (area > rv)
     rv = area;
   }
  }
  return rv;
 }

Regular Expression Matching

 public static boolean isMatch(String s, String p) {
  int sLen = s.length();
  int pLen = p.length();

  int sIdx = 0;
  for (int i = 0; i < pLen; i++) {
   char pc = p.charAt(i);
   if (i < pLen - 1 && p.charAt(i + 1) == '*') {
    if (isMatch(s.substring(sIdx), p.substring(i + 2)))
     return true;
    for (int j = 0; j < sLen - sIdx; j++) {
     if (pc == '.' || pc == s.charAt(sIdx + j)) {
      if (isMatch(s.substring(sIdx + j + 1),
        p.substring(i + 2)))
       return true;
     } else {
      sIdx += j;
      break;
     }
    }
    i++;
   } else {
    if (sIdx >= sLen)
     return false;

    if (pc == '.' || pc == s.charAt(sIdx))
     sIdx++;
    else
     return false;
   }
  }
  return (sIdx == sLen);
 }

Palindrome Number

 public boolean isPalindrome(int x) {
  StringBuffer sb = new StringBuffer();

  sb.append(x);
  int len = sb.length();
  int ps = 0;
  int pe = len - 1;

  while (sb.charAt(ps++) == sb.charAt(pe--)) {
   if (ps >= pe)
    return true;
  }

  return false;
 }

String to Integer (atoi)

 public int atoi(String str) {
  long rv = 0;
  boolean readStart = false;
  boolean negativeSign = false;
  int len = str.length();

  for (int i = 0; i < len; i++) {
   char c = str.charAt(i);

   if (c >= '0' && c <= '9') {
    readStart = true;
    rv *= 10;
    rv += (c - '0');
   } else if (readStart)
    break;
   else if (c == '-') {
    negativeSign = true;
    readStart = true;
   } else if (c == '+')
    readStart = true;
   else if (c >= 'a' && c <= 'z')
    break;
  }

  if (negativeSign)
   rv *= -1;

  if (rv > Integer.MAX_VALUE)
   return Integer.MAX_VALUE;
  else if (rv < Integer.MIN_VALUE)
   return Integer.MIN_VALUE;

  return (int) rv;
 }

Reverse Integer

 public int reverse(int x) {
  boolean negativeSign = false;
  if (x < 0) {
   negativeSign = true;
   x *= -1;
  }

  int rv = 0;
  while (x > 0) {
   rv *= 10;
   rv += (x % 10);
   x /= 10;
  }

  if (negativeSign)
   rv *= -1;
  return rv;
 }

ZigZag Conversion

 public String convert(String s, int nRows) {
  if (nRows == 1)
   return s;

  StringBuffer[] sbs = new StringBuffer[nRows];
  for (int i = 0; i < nRows; i++) {
   sbs[i] = new StringBuffer();
  }

  int len = s.length();
  int cursor = 0;
  int cursorMax = nRows - 1;
  boolean inc = true;

  for (int i = 0; i < len; i++) {
   sbs[cursor].append(s.charAt(i));

   if (inc)
    cursor++;
   else
    cursor--;

   if (cursor == 0) {
    inc = true;
   } else if (cursor == cursorMax) {
    inc = false;
   }
  }

  StringBuffer sb = new StringBuffer();
  for (int i = 0; i < nRows; i++) {
   sb.append(sbs[i]);
  }
  return sb.toString();
 }

Longest Palindromic Substring

 public String longestPalindrome(String s) {
  int len = s.length();
  if (len < 2)
   return s;

  int iLen = len - 1;
  int sIdx = 0;
  int eIdx = 0;
  int cLen = 0;

  for (int i = 0; i < iLen; i++) {
   for (int j = len - 1; j > i; j--) {
    int ss = i;
    int ee = j;
    boolean check = true;

    while (true) {
     if (s.charAt(ss++) != s.charAt(ee--)) {
      check = false;
      break;
     }

     if (ss >= ee)
      break;
    }

    if (check) {
     if (j - i > cLen) {
      cLen = j - i;
      sIdx = i;
      eIdx = j;
     }
     break;
    }
   }

   if (len - i < cLen)
    break;
  }

  return s.substring(sIdx, eIdx + 1);
 }

Add Two Numbers

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  ListNode rv = new ListNode(0);
  ListNode tx = rv;

  ListNode t1 = l1;
  ListNode t2 = l2;

  boolean carrier = false;
  while (true) {
   int val = carrier ? 1 : 0;

   if (t1 != null) {
    val += t1.val;
    t1 = t1.next;
   }

   if (t2 != null) {
    val += t2.val;
    t2 = t2.next;
   }

   tx.val = (val % 10);
   carrier = (val > 9);

   if (t1 == null && t2 == null && !carrier)
    break;

   tx.next = new ListNode(0);
   tx = tx.next;
  }

  return rv;
 }

Longest Substring Without Repeating Characters

 public int lengthOfLongestSubstring(String s) {
  int len = s.length();
  if (len == 0)
   return 0;

  int maxLen = 1;
  int iLen = len - 1;
  for (int i = 0; i < iLen; i++) {
   int cLen = 1;
   int[] idxArr = new int[128];
   idxArr[s.charAt(i)] = 1;

   for (int j = i + 1; j < len; j++) {
    int idx = s.charAt(j);
    if (idxArr[idx] == 0) {
     idxArr[idx] = 1;
     cLen++;
    } else {
     break;
    }
   }

   if (cLen > maxLen)
    maxLen = cLen;
  }

  return maxLen;
 }

Median of Two Sorted Arrays

 public double findMedianSortedArrays(int A[], int B[]) {
  int aLen = A.length;
  int bLen = B.length;
  int tLen = aLen + bLen;
  int[] arr = new int[tLen];
  int idx = 0, aIdx = 0, bIdx = 0;

  for (; aIdx < aLen && bIdx < bLen;) {
   if (A[aIdx] <= B[bIdx]) {
    arr[idx++] = A[aIdx++];
   } else {
    arr[idx++] = B[bIdx++];
   }
  }

  if (aIdx < aLen) {
   for (; aIdx < aLen;)
    arr[idx++] = A[aIdx++];
  }

  if (bIdx < bLen) {
   for (; bIdx < bLen;)
    arr[idx++] = B[bIdx++];
  }

  if ((tLen & 1) == 1) {
   return arr[tLen / 2];
  } else {
   return ((double) (arr[tLen / 2 - 1] + arr[tLen / 2])) / 2;
  }
 }

Two Sum

 public int[] twoSum(int[] numbers, int target) {
  int[] rv = null;

  int len = numbers.length;
  int iLen = len - 1;

  for (int i = 0; i < iLen; i++) {
   int tx = target - numbers[i];
   for (int j = i + 1; j < len; j++) {
    if (tx == numbers[j]) {
     rv = new int[2];
     rv[0] = i + 1;
     rv[1] = j + 1;
     break;
    }
   }

   if (rv != null)
    break;
  }

  return rv;
 }