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. Solution: public class Solution { public int firstMissingPositive(int[] nums) { for(int i=0; i<nums.length; i++) while(nums[i]>0 && nums[i]<=nums.length && nums[nums[i]-1]!=nums[i]) swap(nums, nums[i]-1, i); for(int i=0; i<nums.length; i++) if(nums[i]!=i+1) return i+1; return nums.length+1; } public void swap(int[] nums, int i,

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once.

You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope. What is the maximum number of envelopes can you Russian doll? (put one inside other) Example: Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O(n2) complexity. Follow up: Could you improve it to O(n log n) time complexity?

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 return [ [5,4,11,2], [5,8,4,5] ] Solution: /** * Definition for a binary tree node. * public class TreeNode { * int

Given an array of strings, group anagrams together. For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Return: [ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ] Note: All inputs will be in lower-case. Solution: public class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> ans = new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for(String s : strs){ char[] chs = s.toCharArray(); Arrays.sort(chs); String key = String.valueOf(chs); if(map.containsKey(key)){ map.get(key).add(s); } else {

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Note: Do not modify the linked list. Follow up: Can you solve it without using extra space? Solution: /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. For example: Given nums = [1, 2, 1, 3, 2, 5], return [3, 5]. Note: The order of the result is not important. So in the above example, [5, 3] is also correct. Your algorithm should run in linear runtime complexity.

Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Solution: public class Solution { public int singleNumber(int[] nums) { int count2=0, count1=0, mask=0; for(int n : nums){ count2 ^= count1 & n; count1 ^= n; mask = ~(count2 & count1); count2 &= mask; count1 &=

Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Solution: public class Solution { public int singleNumber(int[] nums) { int count = 0; for(int n : nums) count ^= n; return count; } }