3. Longest Substring Without Repeating Characters
5. Longest Palindromic Substring
17. Letter Combinations of a Phone Number
19. Remove Nth Node From End of List
33. Search in Rotated Sorted Array
80. Remove Duplicates from Sorted Array II
81. Search in Rotated Sorted Array I
82. Remove Duplicates from Sorted List II
94. Binary Tree Inorder Traversal
95. Unique Binary Search Tree II
98. Validate Binary Search Tree
102. Binary Tree Level Order Traversal
103. Binary Tree Zigzag Level Order Traversal
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
109. Convert Sorted List to Binary Search Tree
114. Flatten Binary Tree to Linked List
116. Populating Next Right Pointers in Each Node
117. Populating Next Right Pointers in Each Node II
138. Copy List with Random Pointer
144. Binary Tree Preorder Traversal
150. Evaluate Reverse Polish Notation
151. Reverse Words in a String
153. Find Minimum in Rotated Sorted Array
166. Fraction to Recurring Decimal
173. Binary Search Tree Iterator
199. Binary Tree Right Side View
201. Bitwise AND of Numbers Range
208. Implement Trie (Prefix Tree)
209. Minimum Size Subarray Sum
211. Add and Search Word - Data structure design
215. Kth Largest Element in an Array
222. Count Complete Tree Nodes
230. Kth Smallest Element in a BST
236. Lowest Common Ancestor of a Binary Tree
238. Product of Array Except Self
241. Different Ways to Add Parentheses
287. Find the Duplicate Number
300. Longest Increasing Subsequence
304. Range Sum Query 2D - Immutable
307. Range Sum Query - Mutable
309. Best Time to Buy and Sell Stock with Cooldown
318. Maximum Product of Word Lengths
331. Verify Preorder Serialization of a Binary Tree
334. Increasing Triplet Subsequence
341. Flatten Nested List Iterator
357. Count Numbers with Unique Digits
373. Find K Pairs with Smallest Sums
375. Guess Number Higher or Lower II
378. Kth Smallest Element in a Sorted Matrix
380. Insert Delete GetRandom O(1)
388. Longest Absolute File Path
395. Longest Substring with At Least K Repeating Characters
406. Queue Reconstruction by Height
416. Partition Equal Subset Sum
417. Pacific Atlantic Water Flow
421. Maximum XOR of Two Numbers in an Array
2. Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Solution:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return null;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = 0;
if (l1 != null) {
sum += l1.val;
}
if (l2 != null) {
sum += l2.val;
}
sum += carry;
ListNode node = new ListNode(sum % 10);
cur.next = node;
cur = cur.next;
carry = sum / 10;
l1 = (l1 == null)? l1 : l1.next;
l2 = (l2 == null)? l2 : l2.next;
}
return dummy.next;
}
}
I used one while loop and the conditions l1 != null, l2 != null and carry != 0 have been compared more than once. To make it faster, you can break the while loop into four separate ones:
while (l1 != null && l2 != null) {
###
}
while (l1 != null) {
###
}
while (l2 != null) {
###
}
while (carry != 0) {
###
}
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Solution:
It is a sliding window problem and I use a HashSet to record the elements inside the window.
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null) {
throw new IllegalArgumentException("input is null");
}
int left = 0;
int right = 0;
int result = 0;
Set<Character> set = new HashSet<>();
while (right < s.length()) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
result = Math.max(result, right - left + 1);
right++;
}
return result;
}
}
Time complexity is O(n) and space complexity is O(n).
If the characters of the input string are lowercase letters/ASCII, then you can use an int array whose size is 26/256, which is faster than HashSet. If it requires to get a longest substring that allows the same character appears no more than k times, then you need use a HashMap whose key is character and value is the frequency of that character inside the window.
5. Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
Solution:
There are multiple methods:
Mehthod 1:
Brute force method: for every possible substring, check if palindrome. Time complexity is O(n3).
Method 2:
DP: Use a 2D boolean matrix whose element M[i][j] is true if substring from the ith to the jth is palindrome. Base case is M[i][i] is true for all possible i and M[i][i+1] is true if input[i] == input[i + 1]. The induction rule is: M[i][j] = true, if M[i + 1][j - 1] is true and input[i] == input[j].
Method 3:
If you understand the DP method, then you can see that when calculating M[2][5], we only need to know M[3][4], although M[4][5], M[5][6], ... , have been stored. This fact will inspire us to improve the space complexity: for each character in the string, expand to its left and right simultaneously to check if it is palindrome. Don't forget there are two palindrome case: even palindrome string and odd palindrome string.
waiting
Time complexity is O(n2) and space complexity is O(1). I think Method 3 is a reasonable solution and you are able to propose it independently.
Method 4:
Manacher algorithm
Method 5:
postfix method
6. ZigZag Conversion
The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
Solution:
Pure math problem. Don't waste time on it.
public class Solution {
public String convert(String s, int nRows) {
int length = s.length();
if (length <= nRows || nRows == 1) return s;
char[] chars = new char[length];
int step = 2 * (nRows - 1);
int count = 0;
for (int i = 0; i < nRows; i++){
int interval = step - 2 * i;
for (int j = i; j < length; j += step){
chars[count] = s.charAt(j);
count++;
if (interval < step && interval > 0
&& j + interval < length && count < length){
chars[count] = s.charAt(j + interval);
count++;
}
}
}
return new String(chars);
}
}
8. String to Integer(atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
public class Solution {
public int myAtoi(String str) {
if(str == null) {
return 0;
}
str = str.trim();
if (str.length() == 0) {
return 0;
}
int sign = 1;
int index = 0;
if (str.charAt(index) == '+') {
index++;
} else if (str.charAt(index) == '-') {
sign = -1;
index++;
}
long num = 0;
for (; index < str.length(); index++) {
if (str.charAt(index) < '0' || str.charAt(index) > '9')
break;
num = num * 10 + (str.charAt(index) - '0');
if (num > Integer.MAX_VALUE ) {
break;
}
}
if (num * sign >= Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
if (num * sign <= Integer.MIN_VALUE) {
return Integer.MIN_VALUE;
}
return (int)num * sign;
}
}
11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
Solution:
This is an interesting problem. Assuming fixed two index points i and j where i < j, its capacity is (j - i) * min(height(i), height(j)). Now from the two points, how are you going to find next possible larger capacity? The answer is to move i one step right if height(i) < height(j), otherwise move j one step left. Why? Because if height(i) < height(j),
- if move i one step right, although the width is decreased by one, but it is possible to find a height larger than
height(i)which is current heightmin(height(i), height(j)), - if move j one step left, the width is decrease by one too. If
height(j - 1) > height(i), it won't change the height of the new container which is stillheight(i); ifheight(j - 1) < height(i), the height of the new container is even smaller. So there is no way to get a larger container by moving index j.
Now the solution is pretty simple, from the two pointers left = 0 and right = length - 1, move them based on what we just discussed while left <= right.
public class Solution {
public int maxArea(int[] height) {
if (height == null) {
return 0;
}
int left = 0;
int right = height.length - 1;
int result = 0;
while (left <= right) {
result = Math.max(result, (right - left) * Math.min(height[left], height[right]));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return result;
}
}
12. Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
Solution:
15. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
Solution:
There are a series of 2Sum, 3Sum, 4Sum and kSum problems which definitely worthes me to write a summary in the future. Take notes can not only record my thoughts, but also make me improve my thoughts.
First of all it can easily expand to a + b + c = target.
The 3Sum solution is based on 2Sum problem which is #1 problem in LeetCode. The idea is that for every number, do the 2Sum in the remaining numbers set. There are a few things to pay attention:
2Sum problem has two solutions: one is sort first then use two pointers method(O(nlogn) time, O(1) space), the other one is use HashSet/HashMap(O(n) time, O(n) space).
In the 3Sum solution framework, the 2Sum solution which will be a private method to be called is the "sort-two-pointers" mehtod becuase its space complexity is O(1), and if use 2Sum's HashMap based method, it will be very complicated for array with duplicate numbers. Helpful discussion is here.
How to avoid duplicate triplets?
- for
input[i], the remaining set to do 2Sum is frominput[i + 1]toinput[input[length] - 1]because ifinput[i]is pre-selected in the potential triplet, then it needs to be excluded wheninput[i + 1]is pre-selected. For example, assuming input array is [1, 2, 3, 4, 5] which contains no duplicate numbers and target is 6,- If 1 is pre-selected, 2Sum(5) on [2, 3, 4, 5] will return 2 and 3, the triplet is [1, 2, 3].
- Next time when 2 is pre-selected, if do 2Sum(4) on [1, 3, 4, 5, 6] without excluding 1, it will return 1 and 3, the triplet is still [1, 2, 3]
- for input array with duplicate numbers, if
input[i]is pre-selected, then next time pre-selectedinput[i + 1]only ifinput[i] != input[i + 1], because the input array will be sorted first. Why we sort the array? Because we are going to use "sort-two-pointers" 2Sum solution as a helper function. - also need to avoid duplicate pairs in the 2Sum method.
- for
If you understand above content, the solution should be easy to understand.
public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// skip duplicate elements
if (i > 0 && nums[i - 1] == nums[i]) {
continue;
}
// twoSum from i + 1 to nums.length - 1
// target is -nums[i]
twoSum(nums, i + 1, nums.length -1, -nums[i], results);
}
return results;
}
private void twoSum(int[] nums, int left, int right, int target, List<List<Integer>> results) {
while (left < right) {
if (nums[left] + nums[right] == target) {
// one triplet found, put into results
List<Integer> result = new ArrayList<>();
result.add(-target);
result.add(nums[left]);
result.add(nums[right]);
results.add(result);
left++;
right--;
// skip duplicate pairs with same left
while (left < right && nums[left - 1] == nums[left]) {
left++;
}
// skip duplicate paris with same right
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (nums[left] + nums[right] < target) {
left++;
} else {
right--;
}
}
}
}
Time complexity is O(n2) because firstly sort takes O(nlogn), then 2Sum takes O(n) and it is called at most O(n) times. Space complexity is O(1).
One mistake I made:
private void twoSum(int[] nums, int left, int right, int target, List<List<Integer>> results) {
while (left < right) {
// left <= right is wrong, because it requies a pair
if (nums[left] + nums[right] == target) {
A simple follow up question: what if it is asked to return the index triplet rather than the value triplet? Still requires no duplicate triplets. Assuming input array is sorted, otherwise we need sort it, therefore it does not make sense to ask for index.
When pass the value, also pass its index:
// pass index i to the 2Sum method
private void twoSum(..., int target, int iIndex, ...) {
...
}
16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution:
Similar to Problem 15. 3Sum.
public class Solution {
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length <= 2) {
throw new IllegalArgumentException("input not valid");
}
Arrays.sort(nums);
int result = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(sum - target) < Math.abs(result - target)) {
result = sum;
}
if (sum == target) {
return result;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}
17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Solution:
DFS problem.
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.length() == 0) {
return result;
}
Map<Character, char[]> map = new HashMap<>();
map.put('0', new char[] {});
map.put('1', new char[] {});
map.put('2', new char[] {'a', 'b', 'c'});
map.put('3', new char[] {'d', 'e', 'f'});
map.put('4', new char[] {'g', 'h', 'i'});
map.put('5', new char[] {'j', 'k', 'l'});
map.put('6', new char[] {'m', 'n', 'o'});
map.put('7', new char[] {'p', 'q', 'r', 's'});
map.put('8', new char[] {'t', 'u', 'v'});
map.put('9', new char[] {'w', 'x', 'y', 'z'});
StringBuilder sb = new StringBuilder();
helper(digits, result, map, sb);
return result;
}
private void helper(String digits, List<String> result, Map<Character, char[]> map, StringBuilder sb) {
if (sb.length() == digits.length()) {
result.add(sb.toString());
return;
}
for (char c : map.get(digits.charAt(sb.length()))) {
sb.append(c);
helper(digits, result, map, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}
18. 4Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
Solution:
Based on 3Sum, and 3Sum is based on 2Sum. The trick in 3Sum to avoid duplication is also applied in 4Sum.
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length <= 3) {
return results;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length -2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right] + nums[j] + nums[i];
if (sum == target) {
List<Integer> result = new ArrayList<>();
result.add(nums[i]);
result.add(nums[j]);
result.add(nums[left]);
result.add(nums[right]);
results.add(result);
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return results;
}
}
Time complexity is O(n3) and space complexity is O(1).
19. Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
Solution:
It is a variant of slow-faster pointers method. Use a dummy node. Initially slow pointer is n + 1 steps far from the faster pointer. When faster pointer is null, the node needs to be delted is slow.next.
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Solution:
DFS problem.
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n <= 0) {
return result;
}
char[] list = new char[2 * n];
helper(n, 0, 0, result, list);
return result;
}
private void helper(int n, int left, int right, List<String> result, char[] list) {
if (left + right == 2 * n) {
result.add(new String(list));
return;
}
if (left < n) {
list[left + right] = '(';
helper(n, left + 1, right, result, list);
}
if (right < left && left <= n) {
list[left + right] = ')';
helper(n, left, right + 1, result, list);
}
}
}
Time complexity is O(2n) and space complexity is O(n).
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Solution:
If you know how to recursively reverse a LinkedList, then you should be able to solve this problem easily.
public class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHeadSub = swapPairs(head.next.next);
ListNode newHead = head.next;
head.next.next = head;
head.next = newHeadSub;
return newHead;
}
}
33. Search in Rotated Sorted Array
Suppose an array sorted in ascending order 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.
Solution:
It is a variant of binary search problem. After rotation there are two cases:
input[left] <= input[mid]
[0, 1, 2, 3, 4, 5, 6] -> [3, 4, 5, 6, 0, 1, 2] input[left] is 3, input[mid] is 6. if input[left] <= target < input[mid] : search left; otherwise, search right.input[mid] < input[left]
[0, 1, 2, 3, 4, 5, 6] -> [5, 6, 0, 1, 2, 3, 4] input[left] is 5, input[mid] is 1. if input[mid] < target <= input[right] : search right; otherwise, search left.
public class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}
34. Search for a Range
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
Solution:
It is a good practice to binary search problem.
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return new int[] {-1, -1};
}
int[] result = new int[2];
// find left boarder
int left = 0;
int right = nums.length - 1;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
if (nums[left] == target) {
result[0] = left;
} else if (nums[right] == target) {
result[0] = right;
} else {
result[0] = -1;
result[1] = -1;
return result;
}
// find right boarder
left = 0;
right = nums.length - 1;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid;
} else {
right = mid - 1;
}
}
if (nums[right] == target) {
result[1] = right;
} else if (nums[left] == target){
result[1] = left;
} else {
result[0] = -1;
result[1] = -1;
return result;
}
return result;
}
}
36. Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Solution:
Check matrix's row, column and submatrix, respectively.
public class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[] visited = new boolean[9];
// row
for(int i = 0; i<9; i++){
Arrays.fill(visited, false);
for(int j = 0; j<9; j++){
if(!process(visited, board[i][j]))
return false;
}
}
//col
for(int i = 0; i<9; i++){
Arrays.fill(visited, false);
for(int j = 0; j<9; j++){
if(!process(visited, board[j][i]))
return false;
}
}
// sub matrix
for(int i = 0; i<9; i+= 3){
for(int j = 0; j<9; j+= 3){
Arrays.fill(visited, false);
for(int k = 0; k<9; k++){
if(!process(visited, board[i + k/3][ j + k%3]))
return false;
}
}
}
return true;
}
private boolean process(boolean[] visited, char digit){
if(digit == '.'){
return true;
}
int num = digit - '0';
if ( num < 1 || num > 9 || visited[num-1]){
return false;
}
visited[num-1] = true;
return true;
}
}
39. Combination Sum
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is:
[
[7],
[2, 2, 3]
]
Solution:
It is a "99 cents" problem, which can be solved by DFS.
DFS method 1:
Each branch of the recursion tree represents picking one number from all possible candidates. For example, if input[i] is selected, then next level DFS will tryp from input[i], input[i + 1], ... , until last number. The height of the recursion tree is target/min of input array. To avoid duplicate combinations, during DFS, do not go back.
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
dfs(candidates, 0, target, new ArrayList<Integer>(), results);
return results;
}
private void dfs(int[] candidates, int index, int target, List<Integer> result, List<List<Integer>> results) {
if (target == 0) {
results.add(new ArrayList(result));
return;
} else if (target < 0) {
return;
}
for (int i = index; i < candidates.length; i++) {
result.add(candidates[i]);
dfs(candidates, i, target - candidates[i], result, results);
result.remove(result.size() - 1);
}
}
}
Time complexity is O(mn), where m is the number of candidates, and n is the height of the recursion tree target/min of input array. Space complexity is O(n) where n is the height of the recursion tree.
DFS method 2:
An optimized method is that, each recursion level represents one candidate number, and the branchs stand for putting this number once, twice, ... , until the sum is larger than the target. So if there are k candidates numbers, the height of the recursion tree is k.
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
dfs(candidates, 0, target, new ArrayList<Integer>(), results);
return results;
}
private void dfs(int[] candidates, int level, int target, List<Integer> result, List<List<Integer>> results) {
if (target == 0) {
results.add(new ArrayList(result));
return;
} else if (level == candidates.length) {
return;
}
for (int i = 0; i <= target / candidates[level]; i++) {
for (int j = 0; j < i; j++) {
result.add(candidates[level]);
}
dfs(candidates, level + 1, target - i * candidates[level], result, results);
for (int j = 0; j < i; j++) {
result.remove(result.size() - 1);
}
}
}
}
The time complexity is O(nm) where n is the maximum dfs branchs(target/min of input array), and m is size of input array. Space complexity is O(m) where m is the size of input array.
Now comparing these two methods, if target is 1 million, size of input array is 100, and the min of input array is 1, which one is beter? The answer is method 2.
40. Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Solution:
In this problem, the candidates numbers can be duplicate, and each number can only by used once. I would say, this is a "all subset" problem, rather than a follow up of Problem 39. Combination Sum. Why?
Initially, I thought, the solution can be based on method 1 of Problem 39. Combination Sum. Each level still represents picking one candidate, the difference is that if input[i] is selected, then at next level, dfs will try input[i + 1], input[i + 2], ....
for (int i = level; i < candidates.length; i++) {
result.add(candidates[i]);
dfs(candidates, i + 1, target - candidates[i], result, results);
result.remove(result.size() - 1);
}
In the above unsuccessful solution, the next level DFS starts from i + 1 while in method 1 of Problem 39, it starts from i. But this solution is wrong, because the input can contain duplicate numbers. For example, the input array is [1, 2, 1, 5] and target is 8, then the answer should be [1, 2, 5], but my solution can give [1a, 2, 5] and [2, 1b, 5] where 1a and 1b represent different 1 in the input array. In other words, my solution above only works for the case that the input array has no duplicate numbers. So this problem, Problem 40. Combination Sum II is a follow up of this problem rather than the Problem 39: the input array has no duplicate number and each number can only be used one, find all subset equal to the target.
How to de-duplicate the solution if the input array has duplications? The idea here is that if 1a has been put at the position i, then avoid to put 1b, 1c to the same position i in the future(1a, 1b, 1c represent different 1s). How to implement this idea?
The solution: sort the input array first, so when going down to next level of recursion, check if input[i] == input[i - 1], if true, skip it. This implementation also works for the original "all subset" problem but the input array has duplications.
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
Arrays.sort(candidates);
dfs(candidates, 0, target, new ArrayList<Integer>(), results);
return results;
}
private void dfs(int[] candidates, int level, int target, List<Integer> result, List<List<Integer>> results) {
if (target == 0) {
results.add(new ArrayList(result));
return;
} else if (target < 0) {
return;
} else if (level == candidates.length) {
return;
}
for (int i = level; i < candidates.length; i++) {
if (i != level && candidates[i] == candidates[i - 1]) {
continue;
}
result.add(candidates[i]);
dfs(candidates, i + 1, target - candidates[i], result, results);
result.remove(result.size() - 1);
}
}
}
You need understand this line:
if (i != level && candidates[i] == candidates[i - 1])
If i == level, it is first element to choose then we can not skip no matter it is equal to candidates[i - 1] or not; if i != level and candidates[i] == candidates[i - 1], then candidates[i] has to be skipped because candidates[i - 1] must has been selected to the position level before it. I emphasize here it is i ! = level not i != 0.
Time complexity is O(2n) where n is the size of candidates array. Why? You may think it is O(nn) because there are at most n branches from one recursion tree node and there are at most n levels. But, in the recursion tree, each node(including leaf nodes and non-leaf nodes) represents a subset, and there are 2n subset totally, so the time complexity is O(2n) which is more bounded.
Space complexity is O(n).
It is considered as a binary problem. Each DFS level represents picking or not picking one number, and based on alreay select one number in the previous level, it has two choice in next level. For example, input is [1, 2, 3], the dfs recursion tree is like that,
1: 1 () pick 1 or not
/ \ / \
2: (1)2 (1) 2 () pick 2 or not
/ \ / \ / \ / \
3: (12)3 (12) (1) (1)3 (2)3 (2) 3 () pick 3 or not
All subsets are listed as leaf nodes. To de-duplicate the solution, the idea is that sort first, then when not selecting the duplicate nubmer, skip all remaining duplicate numbers until a different one. For example,
1: 1 ()
/ \ / |
2: (1)2 (1) 2 |
/ | | / | |
2: (12)2 | | (2)2 | |
/ \ / \ / \ / \ / \ / \
3: (122)3 (122) (12)3 (12) (1)3 (1) (22)3 (22) (2)3 (2) 3 ()
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
Arrays.sort(candidates);
dfs(candidates, 0, target, new ArrayList<Integer>(), results);
return results;
}
private void dfs(int[] candidates, int level, int target, List<Integer> result, List<List<Integer>> results) {
if (target == 0) {
results.add(new ArrayList(result));
return;
} else if (target < 0) {
return;
} else if (level == candidates.length) {
return;
}
result.add(candidates[level]);
dfs(candidates, level + 1, target - candidates[level], result, results);
result.remove(result.size() - 1);
while (level != candidates.length - 1 && candidates[level] == candidates[level + 1]) {
level++;
}
dfs(candidates, level + 1, target, result, results);
}
}
Comparing to method 1, method 2 does not have a for loop and there is a while loop to skip the duplicate numbers. One subtle difference:
// method 1 comopare i with i - 1
if (i != level && candidates[i] == candidates[i - 1])
// method 2 compare level with level + 1
while (level != candidates.length - 1 && candidates[level] == candidates[level + 1])
Time complexity is O(2n) where n is the size of input array. Space complexity is O(n).
43. Multiply Strings
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.
Note:
- The length of both num1 and num2 is < 110.
- Both num1 and num2 contains only digits 0-9.
- Both num1 and num2 does not contain any leading zero.
- You must not use any built-in BigInteger library or convert the inputs to integer directly.
Solution:
public class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null) {
return null;
}
int len1 = num1.length(), len2 = num2.length();
int len3 = len1 + len2;
int[] num3 = new int[len3];
for (int i = len1 - 1; i >= 0; i--) {
int carry = 0;
int j;
for (j = len2 - 1; j >= 0; j--) {
int product = carry + num3[i + j + 1] + Character.getNumericValue(num1.charAt(i)) * Character.getNumericValue(num2.charAt(j));
num3[i + j + 1] = product % 10;
carry = product / 10;
}
num3[i + j + 1] = carry;
}
StringBuilder sb = new StringBuilder();
int i = 0;
while (i < len3 - 1 && num3[i] == 0) {
i++;
}
while (i < len3) {
sb.append(num3[i++]);
}
return sb.toString();
}
}
46. Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Solution:
It is a DFS problem.
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
helper(nums, new ArrayList<Integer>(), results);
return results;
}
private void helper(int[] nums, List<Integer> result, List<List<Integer>> results) {
if (result.size() == nums.length) {
results.add(new ArrayList(result));
return;
}
for (int i = 0; i < nums.length; i++) {
if (result.contains(nums[i])) {
continue;
}
result.add(nums[i]);
helper(nums, result, results);
result.remove(result.size() - 1);
}
}
}
If it just asks for print out of all permutations, then we can use the "swap-swap" method.
if (index == nums.length) {
print one permutation;
}
for (int i = index; i < nums.length; i++) {
swap(nums, index, i);
helper(nums, index);
swap(nums, index, i);
}
47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
Solution:
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
int[] visited = new int[nums.length];
helper(nums, visited, new ArrayList<Integer>(), results);
return results;
}
private void helper(int[] nums, int[] visited, List<Integer> result, List<List<Integer>> results) {
if (result.size() == nums.length) {
results.add(new ArrayList(result));
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] == 1 || (i != 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0)) {
continue;
}
result.add(nums[i]);
visited[i] = 1;
helper(nums, visited, result, results);
result.remove(result.size() - 1);
visited[i] = 0;
}
}
}
48. Rotate Image
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
Solution:
public class Solution {
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int length = matrix.length;
for (int i = 0; i < length / 2; i++) {
for (int j = 0; j < (length + 1) / 2; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[length - j - 1][i];
matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
matrix[j][length - i - 1] = tmp;
}
}
}
}
49. Group Anagrams
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:
There are two ways to detect anagram, which can further develop two solutions for this problem.
Method 1: based on sort.
Two anagrams have the same letters so after sorting, they are the same. This is the simplest way to detect anagram. To group anagrams, a HashMap is needed whose value is the sorted string and value is a list of all anagrams. Next time a new String will be sorted first then check in the HashMap if contains a key equal to the sorted String, if so, append the original String to the value list.
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> results = new ArrayList<>();
if (strs == null || strs.length == 0) {
return results;
}
HashMap<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chs = s.toCharArray();
Arrays.sort(chs);
String sSorted = String.valueOf(chs);
if (!map.containsKey(sSorted)) {
map.put(sSorted, new ArrayList<>());
}
map.get(sSorted).add(s);
}
for (List<String> value : map.values()) {
results.add(value);
}
return results;
}
}
Method 2: based on hash.
The fastest way to detect anagram is by hash. How to design a hash function can assign anagrams the same hash value, non-anngrams different hash values? The answer is to use prime numbers. A prime number only has two divisors: 1 and itself. For example, 2, 3, 5, and 7 are prime numbers. The product of a group of prime numbers are unique, regardless the sequence. And the product of one group of prime numbers is different from that of another group, because p1 * p2 can only transform to 1 * p1 * p2, no way to transform to p1 * p3 or p3 * p4.
Because all inputs will be lower-case, so we use 26 prime numbers to represents the 26 letters. An efficient way to map the 1-1 relationship is array.
public class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> results = new ArrayList<>();
if (strs == null || strs.length == 0) {
return results;
}
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
Map<Integer, List<String>> map = new HashMap<>();
for (String s : strs) {
int hash = 1;
for (char c : s.toCharArray()) {
hash *= primes[c - 'a'];
}
if (!map.containsKey(hash)) {
map.put(hash, new ArrayList<>());
}
map.get(hash).add(s);
}
for (List<String> value : map.values()) {
results.add(value);
}
return results;
}
}
It is O(n) to get the hash value, while in sort-based solution, it is O(nlog) time to detect anagrams.
For space complexity, storing integers is more efficient than storing Strings. Although it uses a constant extra space to store primes, but if the input is very large therefore the HashMap is getting larger and larger, the advantage of storing integers is more precious.
50. Pow(x, n)
Implement pow(x, n).
Solution:
public class Solution {
public double myPow(double x, int n) {
if (x == 0 && n == 0) {
throw new IllegalArgumentException("both x and n are zero");
} else if (n == 0) {
return 1;
}
if (n < 0) {
return 1 / helper(x, -n);
} else {
return helper(x, n);
}
}
private double helper(double x, int n) {
if (n == 1) {
return x;
}
double y = helper(x, n / 2);
if (n % 2 ==0) {
return y * y;
} else {
return y * y * x;
}
}
}
54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Solution:
Method 1, use recursion, there are three base cases:
- mSize is 0 or nSize is 0, means nothing left,
- mSize is 1, means one row left,
- nSize is 1, means one column left.
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int offset = 0;
int mSize = matrix.length;
int nSize = matrix[0].length;
helper(matrix, offset, mSize, nSize, result);
return result;
}
private void helper(int[][] matrix, int offset, int mSize, int nSize, List<Integer> result) {
if (mSize == 0 || nSize == 0) {
return;
} else if (mSize == 1) {
for (int i = 0; i < nSize; i++) {
result.add(matrix[offset][offset + i]);
}
return;
} else if (nSize == 1) {
for (int i = 0; i< mSize; i++) {
result.add(matrix[offset + i][offset]);
}
return;
}
for (int i = 0; i < nSize - 1; i++) {
result.add(matrix[offset][offset + i]);
}
for (int i = 0; i < mSize - 1; i++) {
result.add(matrix[offset + i][offset + nSize - 1]);
}
for (int i = nSize - 1; i >= 1; i--) {
result.add(matrix[offset + mSize - 1][offset + i]);
}
for (int i = mSize - 1; i >= 1 ; i--) {
result.add(matrix[offset + i][offset]);
}
helper(matrix, offset + 1, mSize -2, nSize - 2, result);
}
}
Method 2, written in iteration:
test
55. Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Solution:
Method 1, DP from left to right to fill in a boolean array. result[i] is true if from result[i + 1] to result[i + k], anyone is true where k is the value of result[i].
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
if (nums.length == 1) {
return true;
}
boolean[] result = new boolean[nums.length];
result[result.length - 1] = true;
for (int i = result.length - 2; i >= 0; i--) {
for (int j = i + 1; j <= i + nums[i]; j++) {
if (result[j] == true) {
result[i] = true;
break;
}
}
}
return result[0];
}
}
Time complexity is O(n2) and it exceeds time limit in LeetCode. Space complexity is O(n).
Method 2, greedy way. The idea is that if nums[i] can be reached, then all positions before i are also reachable.
public class Solution {
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int farthest = 0;
for (int i = 0; i < nums.length; i++) {
if (i <= farthest && nums[i] + i >= farthest) {
farthest = nums[i] + i;
}
}
return farthest >= nums.length - 1;
}
}
Time complexity is O(n) and space complexity is O(1).
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
Solution:
Sort all intervals based on the start, then iteratively compare the ends to do merge or not.
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> result = new ArrayList<>();
if (intervals == null || intervals.size() == 0) {
return result;
}
Collections.sort(intervals, new IntervalComparator());
Interval last = intervals.get(0);
for (int i = 1; i < intervals.size(); i++) {
Interval cur = intervals.get(i);
if (cur.start <= last.end) {
last.end = Math.max(cur.end, last.end);
} else {
result.add(last);
last = cur;
}
}
result.add(last);
return result;
}
private class IntervalComparator implements Comparator<Interval> {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
}
}
59. Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Solution:
Similar to Problem 54. Spiral Matrix I, it can be solved either recursively or iteratively.
Method 1, recursion:
public class Solution {
public int[][] generateMatrix(int n) {
if (n < 0) {
return null;
}
int[][] result = new int[n][n];
helper(0, 1, n, result);
return result;
}
private void helper(int offset, int val, int size, int[][] result) {
if(size == 0) {
return;
} else if (size == 1) {
result[offset][offset] = val;
return;
}
for (int i = 0; i < size - 1; i++) {
result[offset][offset + i] = val++;
}
for (int i = 0; i < size - 1; i++) {
result[offset + i][size + offset - 1] = val++;
}
for (int i = size - 1; i > 0; i--) {
result[size + offset - 1][i + offset] = val++;
}
for (int i = size - 1; i > 0; i--) {
result[i + offset][offset] = val++;
}
helper(offset + 1, val, size - 2, result);
}
}
60. Permutation Sequence
The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
Solution:
61. Rotate List
Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
Solution:
Find the right position to break the list. Use dummy node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) {
return head;
}
int length = getLength(head);
k = k % length;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy ;
ListNode fast = dummy;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
fast.next = dummy.next;
dummy.next = slow.next;
slow.next = null;
return dummy.next;
}
private int getLength(ListNode head) {
int length = 0;
while (head != null) {
head = head.next;
length++;
}
return length;
}
}
62. Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Solution:
Method 1:
It is a math problem. In the example, the robot needs to move 8(3 - 1 + 7 - 1) steps totally. And in the 8 steps, it has 2 down and 6 left. So it is equilvalent to calculate C28.
public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int down = combine(m + n - 2, m - 1);
return down;
}
private int combine(int n, int k) {
long result = 1;
for (int i = 1; i <= k; i++) {
result = result * (n - k + i) / i;
}
return (int) result;
}
}
Method 2:
The DP solution is more general. At each cube in the map, it has two possible comming steps,one is from the up, the other is from the left. The base case is the top row and left column.
public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 1;
}
int[][] sum = new int[m][n];
for (int i = 0; i < m; i++) {
sum[i][0] = 1;
}
for (int i = 0; i < n; i++) {
sum[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
}
}
return sum[m - 1][n - 1];
}
}
63. Unique Paths II
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.
Note: m and n will be at most 100.
Solution:
The DP solution in Problem 62. Unique Path I can be easily modified. The difference is the base case: in this problem, when initializing the top row and left column, if there is a obstacle cube, the remaining cubes are not reachable so they should be 0 rather than 1.
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0] == null || obstacleGrid[0].length == 0) {
return 0;
}
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] sum = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 0) {
sum[i][0] = 1;
} else {
break;
}
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 0) {
sum[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 0) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1];
}
}
}
return sum[m - 1][n - 1];
}
}
64. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Solution:
DP.
public class Solution {
public int minPathSum(int[][] grid) {
// sanity check
int m = grid.length;
int n = grid[0].length;
int[][] sum = new int[m][n];
sum[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
sum[i][0] = sum[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
sum[0][i] = sum[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
sum[i][j] = Math.min(sum[i][j - 1], sum[i - 1][j]) + grid[i][j];
}
}
return sum[m - 1][n - 1];
}
}
71. Simplify Path
Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Corner Cases:
- Did you consider the case where path = "/../"?
- In this case, you should return "/".
- Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
- In this case, you should ignore redundant slashes and return "/home/foo".
Solution:
First you need to know a little about Unix-stype path. ".." means parent directory and "." means current directory.
The solution has two steps:
- Separate the path by slash, use
path.split("/+");where /+ is regular expression which means "/" can be once or more than once; - Then read the split array, if met ".." delete one element from the path, if met "." or ""(explained below) do nothing; otherwise add to the path;
In step 2, it requires attention to the split function when the delimiter is the first element. For example, the input is '/a/b' and the delimiter is "/+", then the splited result is (empty), a and b. So you need get rid of the (empty) string from the splited string array.
public class Solution {
public String simplifyPath(String path) {
String result = "/";
String[] stubs = path.split("/+");
List<String> paths = new ArrayList<String>();
for (String s : stubs){
if(s.equals("..")){
if(paths.size() > 0){
paths.remove(paths.size() - 1);
}
}else if (!s.equals(".") && !s.equals("")){
paths.add(s);
}
}
for (String s : paths){
result += s + "/";
}
if (result.length() > 1)
result = result.substring(0, result.length() - 1);
return result;
}
}
73. Set Matrix Zeroes
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
- Did you use extra space?
- A straight forward solution using O(mn) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
Solution:
O(m + n) space is easy, we can use two lists to store the row and column indexes who need to be set as zero.
To use O(1) space, the idea is that use the 1st row and the 1st column to recored the rows and columns who need to be zero. Before that, check if the 1st row and the 1st column need to be set as zero.
public class Solution {
public void setZeroes(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length ==0)
return;
int rows = matrix.length;
int cols = matrix[0].length;
// indicate whether the 1st row/column needs to be zero
boolean empty_row0 = false;
boolean empty_col0 = false;
for(int i = 0; i < cols; i++){
if(matrix[0][i] == 0){
empty_row0 = true;
break;
}
}
for(int i = 0; i < rows; i++){
if(matrix[i][0] == 0){
empty_col0 = true;
break;
}
}
//use the 1st row/column to record
for(int i = 1; i < rows; i++) {
for(int j =1; j<cols; j++){
if(matrix[i][j] == 0){
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for(int i = 1; i<rows; i++) {
for (int j=1; j< cols; j++) {
if(matrix[0][j] == 0 || matrix[i][0] == 0)
matrix[i][j] = 0;
}
}
if(empty_row0){
for(int i = 0; i < cols; i++){
matrix[0][i] = 0;
}
}
if(empty_col0){
for(int i = 0; i < rows; i++){
matrix[i][0] = 0;
}
}
}
}
74. Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
Solution:
It is a binary search problem.
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
return false;
}
int left = 0;
int right = matrix.length * matrix[0].length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int row = mid / matrix[0].length;
int col = mid % matrix[0].length;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
}
75. Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
Solution:
It is a rainbow sort problem. [0, i) not including i is zero zone, [i, j) including i not including j is one zone and (k, length - 1] not including k is two zone. Initially i, j is zero, and k is length - 1. Between j and k including j and k is area not explored yet. We maintain the properties of i, j and k during runtime. The pointer j is examined in the solution. Of course you can examine pointer k.
public class Solution {
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int i = 0;
int j = 0;
int k = nums.length - 1;
while (j <= k) {
if (nums[j] == 1) {
j++;
} else if (nums[j] == 0) {
swap(nums, i, j);
i++;
j++;
} else {
swap(nums, j, k);
k--;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
77. Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Solution:
DFS problem.
public class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<>();
if (n <= 0 || k <= 0) {
return result;
}
//assume n >= k
List<Integer> combine = new ArrayList<>();
helper(1, n, k, combine, result);
return result;
}
private void helper(int i, int n, int k, List<Integer> combine, List<List<Integer>> result) {
if (combine.size() == k) {
result.add(new ArrayList(combine));
return;
}
for (int j = i; j <= n; j++) {
combine.add(j);
helper(j + 1, n, k, combine, result);
combine.remove(combine.size() - 1);
}
}
}
78. Subsets
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Solution:
It is a DFS problem.
Method 1:
Consider it is a binary problem: for each number, either pick or not pick. Take the input array [1,2,3] as an example, there are three levels in the recursion tree, and the 1st level is picking or not picking 1, and based on the choice has made on the 1st level, the 2nd level will choose to pick or not pick 2.
1: 1 ()
/ \ / \
2: (1)2 (1) 2 ()
/ \ / \ / \ / \
3: (12)3 (12) (1)3 (1) (2)3 (2) 3 ()
The leaf nodes in the recursion tree represents all the subset.
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
List<Integer> result = new ArrayList<>();
helper(0, nums, result, results);
return results;
}
private void helper(int level, int[] nums, List<Integer> result, List<List<Integer>> results) {
if (level == nums.length) {
results.add(new ArrayList(result));
return;
}
result.add(nums[level]);
helper(level + 1, nums, result, results);
result.remove(result.size() - 1);
helper(level + 1, nums, result, results);
}
}
Method 2:
Another way of recursion: at level i, if number input[i] is chosen, then at level i + 1, all numbers from input[i + 1], input[i + 2] can be chosen.
0: ()
/ | \
1: 1 2 3
/ \ |
2: (1)2 (1)3 (2)3
/
3: (12)3
There are three level in the recursion tree. All nodes represent the subsets, pay attenetion to how to handle the base case.
public class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
List<Integer> result = new ArrayList<>();
helper(0, nums, result, results);
return results;
}
private void helper(int index, int[] nums, List<Integer> result, List<List<Integer>> results) {
results.add(new ArrayList(result));
for (int i = index; i < nums.length; i++) {
result.add(nums[i]);
helper(i + 1, nums, result, results);
result.remove(result.size() - 1);
}
}
}
For both methods, time complexity is (2n) and space complexity is O(n).
79. Word Search
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
Solution:
DFS problem: for each letter in the board, do a DFS. There are a few questions need to answer first:
- What is the base case? how to handle when arriving the boundary of the matrix?
- Because same cell can only be used once, how to label it?
- How to process the returned results at each recursion level?
public class Solution {
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || word == null) {
return false;
}
if (word.length() == 0) {
return true;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
boolean result = dfs(board, i, j, 0, word);
if (result) {
return result;
}
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, int level, String word) {
if (level == word.length()) {
return true;
}
if (i < 0 || i>= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(level)){
return false;
}
board[i][j] = '#';
boolean result = dfs(board, i + 1, j, level + 1, word) || dfs(board, i, j + 1, level + 1, word) || dfs(board, i - 1, j, level + 1, word) || dfs(board, i, j - 1, level + 1, word);
board[i][j] = word.charAt(level);
return result;
}
}
Answers to the three questions:
- The base case: if out of boundary of matrix, return false; if current letter in the matrix is not equal to the corresponding letter in the word, return false because no need to go to deeper recursion level; if
level == word.length(), return false; - When a cell is visited, mark it as '#', then next time it is visited, return false. After all the recursion calls in the same level finished, restore the cell to its original letter.
- As long as one sequence in the matrix is equal to the word, return true. So use
||
Time complexity is O(mn 4k), because dfs's recursion tree is 4-branching, and its height is k where k is the lenght of the word. And each cell in the matrix needs perform a dfs and there are total mn cells in the matrix.
80. Remove Duplicates from Sorted Array II
Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3],
Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.
Solution:
Two pointers method: [0, slow] is on-going result, (fast, length - 1) is unexplored area. Initially slow is 1, fast is 2. The termination condition is fast >= nums.length.
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums == null) {
}
if (nums.length <= 2) {
return nums.length;
}
int slow = 1;
int fast = 2;
while (fast < nums.length) {
if (nums[fast] == nums[slow - 1]) {
fast++;
} else {
swap(nums, fast, slow + 1);
fast++;
slow++;
}
}
return slow + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
81. Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order 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).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
Solution:
Comparing to Problem 33. Search in Rotated Sorted Array, this problem allows duplicate numbers. This has one consequence: if there are more than two numbers, and nums[left] == nums[mid](in other word, left != right and nums[left] == nums[mid]), then we can not decide to go left or right. For eample, the input array is 1,1,1, ..., 1 and there is one 2 inside, then the 2 can be either in the left half or the right half. So what we can do is left++ because nums[mid](equals to nums[left]) has been checked that it is not equal to target at the beginning.
Method 1, iteratively:
public class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return true;
}
}
return false;
}
}
Time complexity is O(n).
Method 2, binary search with handling nums[left] == nums[mid]
public class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[left] < nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if (nums[left] > nums[mid]){
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return false;
}
}
Time complexity is O(n) for worst case, which is that the input array is [1,1,1,...,1] and one 2 can be at any posiiton in the array.
82. Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
Solution:
Method 1: two pointers method with dummy node. [slow, fast) contains the same elements and use a counter to recored its size.
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tail = dummy;
ListNode slow = head;
ListNode fast = head;
int counter = 0;
while(fast != null) {
while (fast != null && fast.val == slow.val) {
fast = fast.next;
counter++;
}
if (counter == 1) {
tail.next = slow;
tail = tail.next;
}
slow = fast;
counter = 0;
}
tail.next = null;
return dummy.next;
}
}
Method 2: at node head, check head.next and head.next.next. Use a temporary variable val to recored the 1st value, if the next element is equal to val, delete it.
public class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
while (head.next != null && head.next.next != null) {
if (head.next.val == head.next.next.val) {
int val = head.next.val;
while (head.next != null && head.next.val == val) {
head.next = head.next.next;
}
} else {
head = head.next;
}
}
return dummy.next;
}
}
86. Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
Solution:
Build two new lists: one for < x, the other is for >= x. Iteratively scan the list and send the node to the list based on its valule. Finally join these two lists. Set null to the end of the 2nd list.
public class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null) {
return head;
}
ListNode dummySmall = new ListNode(0);
ListNode dummyLarge = new ListNode(0);
ListNode tailSmall = dummySmall;
ListNode tailLarge = dummyLarge;
while (head != null) {
if (head.val < x) {
tailSmall.next = head;
tailSmall = tailSmall.next;
} else {
tailLarge.next = head;
tailLarge = tailLarge.next;
}
head = head.next;
}
tailSmall.next = dummyLarge.next;
tailLarge.next = null;
return dummySmall.next;
}
}
89. Gray Code
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2
Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.
Solution:
This problem requires some backgrounds about constructing gray code.
2-bit list: 00, 01, 11, 10
Reflected: 10, 11, 01, 00
Prefix old entries with 0: 000, 001, 011, 010,
Prefix new entries with 1: 110, 111, 101, 100
Concatenated: 000, 001, 011, 010, 110, 111, 101, 100
public class Solution {
public List<Integer> grayCode(int n) {
List<Integer> result = new ArrayList<Integer>();
if (n <= 1) {
for (int i = 0; i <= n; i++){
result.add(i);
}
return result;
}
result = grayCode(n - 1);
List<Integer> r1 = reverse(result);
int x = 1 << (n-1);
for (int i = 0; i < r1.size(); i++) {
r1.set(i, r1.get(i) + x);
}
result.addAll(r1);
return result;
}
private List<Integer> reverse (List<Integer> r) {
List<Integer> rev = new ArrayList<Integer>();
for (int i = r.size() - 1; i >= 0; i--) {
rev.add(r.get(i));
}
return rev;
}
}
90. Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
Solution:
In Problem 78. Subsets, I list two solutions. Those two methods can be modified to solve this problem.
Also this problem is very similar to Problem 40. Combination Sum II.
Method 1, detailed analysis is in method 2 of Problem 40. Combination Sum II.
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
List<Integer> result = new ArrayList<>();
helper(0, nums, result, results);
return results;
}
private void helper(int level, int[] nums, List<Integer> result, List<List<Integer>> results) {
if (level == nums.length) {
results.add(new ArrayList(result));
return;
}
result.add(nums[level]);
helper(level + 1, nums, result, results);
result.remove(result.size() - 1);
while (level < nums.length - 1 && nums[level] == nums[level + 1]) {
level++;
}
helper(level + 1, nums, result, results);
}
}
Method 2, detailed analysis is in method 1 of Problem 40. Combination Sum II.
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
Arrays.sort(nums);
List<Integer> result = new ArrayList<>();
helper(0, nums, result, results);
return results;
}
private void helper(int index, int[] nums, List<Integer> result, List<List<Integer>> results) {
results.add(new ArrayList(result));
for (int i = index; i < nums.length; i++) {
if (i != index && nums[i - 1] == nums[i]) {
continue;
}
result.add(nums[i]);
helper(i + 1, nums, result, results);
result.remove(result.size() - 1);
}
}
}
91. Decode Ways
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
Solution:
It can be solved by DP.
The base case is the 1st digit and the first 2 digits in the array.
The induction rule is:
M[i] = M[i - 2] if input[i - 1 : i] >= 10 && <= 26
+
M[i - 1] if input[i] is !0
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] nums = new int[s.length()];
nums[0] = s.charAt(0) != '0' ? 1 : 0;
if (s.length() >=2) {
if (s.charAt(1) != '0') {
nums[1] = nums[0];
}
int twoDigits = (s.charAt(0) - '0') * 10 + s.charAt(1) - '0';
if (twoDigits >= 10 && twoDigits <= 26) {
nums[1] += 1;
}
}
for (int i = 2; i < s.length(); i++) {
if (s.charAt(i) != '0') {
nums[i] = nums[i - 1];
}
int twoDigits = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';
if (twoDigits >= 10 && twoDigits <= 26) {
nums[i] += nums[i - 2];
}
}
return nums[s.length() - 1];
}
}
We can see there is redundancy in the solution. If we extend the base case to
nums[0] = 1;
nums[1] = s.charAt(0) != '0' ? 1 : 0;
then nums[2] can inherit nums[0].
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int[] nums = new int[s.length() + 1];
nums[0] = 1;
nums[1] = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= s.length(); i++) {
if (s.charAt(i - 1) != '0') {
nums[i] = nums[i - 1];
}
int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0';
if (twoDigits >= 10 && twoDigits <= 26) {
nums[i] += nums[i - 2];
}
}
return nums[s.length()];
}
}
92. Reverse Linked List II
Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note: Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
Solution:
The idea is simple, but not easy to implement. The solution is from jiuzhang.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 0; i < m - 1; i++) {
head = head.next;
}
ListNode premNode = head;
ListNode mNode = head.next;
ListNode nNode = mNode;
ListNode postnNode = nNode.next;
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;
premNode.next = nNode;
return dummy.next;
}
}
Time complexity is O(n) and space complexity is O(1).
93. Restore IP Addresses
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given "25525511135",
return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Solution:
It is a DFS problem.
A valid IP address needs to satisfy several requirements:
- made by 4 numbers, each number is between 0 and 255;
- among the 4 numbers, two-digit numbers and three digit numbers can not start with zero, for example, 055 or 06 are not allowed;
So apply these restrictions during DFS. Before implementing the DFS solution, several questions need to be clear:
- Number of levels of recursion tree is uncertain, which depends on the lenght of input string,
- Each node of the recursion tree will have at most three branches: one-digit number, two digit number and three-digit number.
- Base case is: if there are exactly 4 numbers until the end of input string, it is one valid IP address; if there are 4 numbers but not at the end of input string, it is impossible to get a valid IP address; if there are less than 4 numbers at the end of the string, it is considered in the body of recursion code so you do not need explicitly return it.
public class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> results = new ArrayList<>();
if (s == null || s.length() < 4 || s.length() > 12 ) {
return results;
}
List<String> path = new ArrayList<>();
helper(s, 0, path, results);
return results;
}
private void helper(String s, int start, List<String> path, List<String> results) {
if (path.size() == 4) {
if (start != s.length()) {
return;
}
StringBuilder sb = new StringBuilder();
for (String str : path) {
sb.append(str);
sb.append(".");
}
sb.deleteCharAt(sb.length() - 1);
results.add(sb.toString());
return;
}
for (int i = start; i < start + 3 && i < s.length(); i++) {
String str = s.substring(start, i + 1);
if(isValid(str)) {
path.add(str);
helper(s, i + 1, path, results);
path.remove(path.size() - 1);
}
}
}
private boolean isValid(String s) {
if (s.charAt(0) == '0') {
return s.equals("0");
}
int num = Integer.parseInt(s);
return num >= 0 && num <= 255;
}
}
In the above code, path stores the current exploring address and if it is valid, it is passed to results with the help of a StringBuilder. The method isValid first checks that if the string starts with '0', return s.equals("0") because only 0 is valid, 05 or 022 is not valid number in the IP address, then checks if the number is in the appropriate range.
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree [1,null,2,3],
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
Solution:
95. Unique Binary Search Trees II
Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution:
Problem 96. Unique Binary Search Tree is here.
This problem requires the output of all BST structures. The idea is a little bit similar to Problem 96, assuming i is selected as the root, then its left subtree is constructed by [1, ..., i - 1] and its right subtree is constructed by [i + 1, ... , n]. Then recursively construct the left subtree and right subtree.
public class Solution {
public List<TreeNode> generateTrees(int n) {
if (n < 1) {
return new ArrayList<TreeNode>();
}
return generate(1, n);
}
private List<TreeNode> generate(int left, int right) {
List<TreeNode> result = new ArrayList<>();
if (left > right) {
result.add(null);
return result;
}
for (int i = left; i <= right; i++) {
List<TreeNode> leftTree = generate(left, i - 1);
List<TreeNode> rightTree = generate(i + 1, right);
for (TreeNode l : leftTree) {
for (TreeNode r : rightTree) {
TreeNode root = new TreeNode(i);
root.left = l;
root.right = r;
result.add(root);
}
}
}
return result;
}
}
In the above solution, in the 1st level of generate method, result stores all possible root nodes, from 1 to n. In the 2nd level of recursion, two new result store all possible root nodes of the left subtree and right subtree, respectively, so after returned back to the 1st level, we combine the root at the 1st level with all possible roots of the left subtree and all possible roots of the right subtree.
From Problem 96, there are C(n) BST structures, where C(n) is a catalan number. And each structure has n treendoes, so the time complexity is O(n * C(n)). Space complexity is O(n2) because there are n levels in the recursion tree and each level uses O(n) space to store all possible root nodes. The space complexity can be further improved because only the 1st level requires the storage of root nodes to be returned, other levels don't need.
96. Unique Binary Search Trees
Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
Solution:
I have no idea how to do it, so let's try some simple cases first.
n = 1, f(1) is 1,
1
n = 2, f(2) is 2,
1 2
\ /
2 1
n = 3, f(3) is 5
1 1 2 3 3
\ \ / \ / /
3 2 1 3 2 1
/ \ / \
2 3 1 2
For n = 3,
- if 1 is root, 2, 3 are on the right subtree, so f(0) * f(2);
- if 2 is root, 1 is on the left, 3 is on the right, so f(1) * f(1);
- if 3 is root, 1, 2 are on the left subtree, so f(0) * f(2);
So we can conclude that f(0) = 1 and f(n) = f(0) f(n - 1) + f(1) f(n - 2) + ... + f(n - 1) * f(0).
The final equation we derived is catalan number. An alternative solution is to use catalan number's mathematic expression directly, whose time complexity is O(n) and space complexity is O(1).
public class Solution {
public int numTrees(int n) {
int[] count = new int[n + 1];
count[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
count[i] += count[j] * count[i - j - 1];
}
}
return count[n];
}
}
Time complexity is O(n2) and space complexity is O(n).
98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Binary tree [2,1,3], return true.
Example 2:
1
/ \
2 3
Binary tree [1,2,3], return false.
Solution:
Firstly I came up a solution based on the definition of BST. It uses recursion and from one level to the next level, it will pass the range where the node's value should be. For the root node, the range is [Integer.MIN_VALUE, Integer.MAX_VALUE]. At some level, it received a range [min, max] from pervious level, and its node value is val, then check current node first, then pass [min, val] to its left subtree, and [val, max] to its right subtree.
This solution can pass most test cases, but does not work for corner case where node's value is Integer.MIN_VALUE or Integer.MAX_VALUE. So I change to Lont type and it works. It looks like some people are fond of testing unreasonable corner cases.
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return helper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean helper(TreeNode root, long min, long max) {
if (root == null) {
return true;
}
if (root.val <= min || root.val >= max) {
return false;
}
return helper(root.left, min, root.val) && helper (root.right, root.val, max);
}
}
Method 2:
Use in-order traversal because in-order traversal of a BST is in ascending order.
public class Solution {
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
return helper(root);
}
private boolean helper(TreeNode root) {
TreeNode cur = root;
long prevVal = Long.MIN_VALUE;
Deque<TreeNode> stack = new LinkedList<>();
while (!stack.isEmpty() || cur != null) {
if (cur != null) {
stack.offerFirst(cur);
cur = cur.left;
} else {
cur = stack.pollFirst();
int curVal = cur.val;
if (curVal <= prevVal) {
return false;
}
prevVal = curVal;
cur = cur.right;
}
}
return true;
}
}
The traversal of a tree iteratively is very important.
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Solution:
BFS with two queues. The idea is that use one queue to output one layer, then use the next queue for the next layer, then use the 1st queue again, so on so forth. I don't recommend this method because in method 1, you will see one queue is enough. Here I just want to show how to use two queues, more specifically, how to swith the two queues.
queue1.add(root);
while (queue1.size() != 0) {
List<Integer> level = new ArrayList<Integer>();
queue2.clear();
for (int i = 0; i < queue1.size(); i++) {
/*
codes
*/
// swap q1 and q2
List<TreeNode> temp = queue1;
queue1 = queue2;
queue2 = temp;
// add to result
result.add(level);
}
}
Method 2:
BFS with one queue. When one layer has been finished, all the nodes of next layer are stored in the queue, so record the size of queue at this time, which can be used as the iteration times of for loop.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if (root == null) {
return results;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp = queue.poll();
level.add(tmp.val);
if (tmp.left != null) {
queue.offer(tmp.left);
}
if (tmp.right != null) {
queue.offer(tmp.right);
}
}
results.add(level);
}
return results;
}
}
In the code, if you use for (int i = 0; i < queue.size(); i++), it doesn't work because size of the queue is changing during iterations inside the for loop.
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
Solution:
In Problem 102. Binary Tree Level Order Traversal, we use a queue. Now for zigzag output, we can use a deque. Why and How?
First, one queue is not working. You may ask, how about at one layer, offer left nodes first, then right nodes, to the queue, and at next level, offer rigth nodes first, then left nodes? For example,
3
/ \
9 20
/ \ / \
1 4 15 7
Level 2: from right to the left, 20 is offer to the queue first, then 9;
Level 3: poll 20, offer 15 and 7; poll 9, offer 1 and 4;
The output is:
[
[3],
[20,9],
[15,7,1,4]
]
But the expected output should be:
[
[3],
[20,9],
[1,4,15,7]
]
If you compare the wrong output with the expected output, you will see: the wrong output does not change the order of subtrees, it only change the order inside the subtrees. More specifically, I mean, from [20,9] in the wrong output, 20 is printed first, but its subnodes 15 and 7 are also printed first in the next level; 9 is printed after 20, and its nodes 1 and 4 are also printed after the subnodes of 20. That is because we use one queue. The only changes it made is changing the orders of nodes in the same subtree: for the subtree rooted at 20, 20 is printed from right to left, and its subnodes [15,7] is printed from left to right. Hopefully you got what I mean.
To change the orders between the subtrees, we should use two stacks:
- from left to right, put 9 and 20 to the 1st stack,
| 9 20 >, - pop 20, from right to left, put its subnodes 7 and 15 to the 2nd stack, do the same thing to 9,
|7 15 4 1 >, for level 2, we get[20.9], - for level 3, we can get
[1,4,15,7]
This idea is similar to the "I love coding" trick I used in the Problem 189. Rotate Array: use stack to reverse the orders between subtrees, and change from "from left to right" to "from right to left" to reverse the order of nodes inside the subtree, so finally get zigzag output.
Can you implement this idea by two stacks? (Hint: method 1 of Problem 102)
Java has a interface "deque" which can be used as two stacks in this problem.
public class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> results = new ArrayList<>();
if (root == null) {
return results;
}
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root);
boolean layer = true;
while (!deque.isEmpty()) {
int size = deque.size();
List<Integer> level = new ArrayList<>();
if(layer) {
for (int i = 0; i < size; i++) {
TreeNode tmp = deque.pollLast();
level.add(tmp.val);
if (tmp.left != null) {
deque.offerFirst(tmp.left);
}
if (tmp.right != null) {
deque.offerFirst(tmp.right);
}
}
} else {
for (int i = 0; i < size; i++) {
TreeNode tmp = deque.pollFirst();
level.add(tmp.val);
if (tmp.right != null) {
deque.offerLast(tmp.right);
}
if (tmp.left != null) {
deque.offerLast(tmp.left);
}
}
}
layer = !layer;
results.add(level);
}
return results;
}
}
So now you see, if offerFirst node A to the deque, then at next level pollFirst will poll it from the deque; if offerLast node A to the deque, then pollFast will poll it. So in this way, the deque is playing as two stacks as we discussed above. Finally don't forget to switch between "from left to right" and "from right to left".
In the solution, I put if(layer) outside of for (int i = 0; i < size; i++), because it can reduce comparing frequency. A short way but with more comparing frequency is:
// code
for (int i = 0; i < size; i++) {
TreeNode tmp = layer ? deque.pollLast() : deque.pollFirst();
level.add(tmp.val);
if (layer) {
if (tmp.left != null) {
deque.offerFirst(tmp.left);
}
if (tmp.right != null) {
deque.offerFirst(tmp.right);
}
else {
// from right to left
}
}
// code
(Can we use two queue? My answer is no, the reason is in my analysis above. Please let me know your opinion.)
105. Construct Binary Tree from Preorder and Inorder Traversal
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
106. Construct Binary Tree from Inorder and Postorder Traversal
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
109. Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
My first idea is refer to Problem 108. Convert Sorted Array to Binary Search Tree, which starts from the middle node as the root and builds the subtrees from the top level to the leaf level.
In the solution, I use the slow-fast pointers to get the middle node:
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
For two different cases:
1 -> 2 -> 3, slow is 2;
1 -> 2 -> 3 -> 4, slow is 3;
In Problem 108, it uses two variables left and right to indicate the range of subtree. Similarly, here I use two pointers head and tail.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode tail) {
if (head == tail) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = helper(head, slow);
root.right = helper(slow.next, tail);
return root;
}
}
Time complexity is O(nlogn) because there are logn levels in the recursion tree and each level uses n/2 time to get the middle nodes. Space complexity is O(logn).
Method 2:
Problem 108's time complexity is O(n), so a naive idea is to transform the list to an array, then apply Problem 108's solution to the array. Time complexity is O(n) and space complexity is O(logn).
Method 3:
Theoretically, the time complexity can not beat O(n) because we need O(n) time to build the BST. To achieve the O(n) time complexity, we can not spend O(n) time to find the middle node as Method 1 did, in contrast, we can only iterate the list.
(It is difficult to understand this method but I will try my best.)
The fact that the in-order traversal of a BST is in ascending order tells us that we need to build the BST in in-order. And for in-order traversal, it is a bottom-up approach.
7
/ \
3 9
/ \ / \
1 4 8 12
Its in-order travesal is [1, 3, 4, 7, 8, 9, 12] and it is the order we are going to follow to build the BST from the ascending LinkedList.
Let's review the concept of in-order traversal first:
void inOrder (TreeNode head) {
// step 1: basecase
if (head == null) {
return;
}
// step 2:
inOrder(head.left);
// step 3: perform some task on the current node
print(head.val);
// step 4:
inOrder(head.right);
}
In above in-order traversal precedures, line print(head.val) is the only place where we can build the TreeNode and further constructing the BST. Now the first time this function(createBST) reaches step 3, it should build a TreeNode based on the 1st element in the list, which is in O(1) time. Then we forward the pointer to next ListNode. The next time the function(createBST) reaches step 3, it should use current ListNode to build a TreeNode, which time cost is O(1) too. This goes on until the last node.
The key point here is:
Because the in-order traversal of a BST is in ascending order, so if we iterate the LinkedList, it is equivalenet to iterate the tree which needs to be built, in the in-order traversal way.
Now you understand the process we are going to implement. In this process, we need a pointer curNode which is the input parameter and output parameter of this function(createBST). Before executing function(createBST), curNode is pointing to the ListNode which the TreeNode is going to build upon, and after executing the function, the subtree has been built, and curNode is pointing to the next ListNode which the TreeNode is going to build upon.
In Java, there is no way to define a variable which can be input paramter and output paramter at the same time, because Java is passing-by-value. My idea is to define a CurNode class which contains curNode variable and pass this CurNode object among in-order traversal calls, in this way, curNode can be modified during the whole recursion tree.
As for the base case, I use a variable size to stand for the number of TreeNodes of the subtree we are going to build. The base case is size <= 0 which means there is no TreeNode to build, so null is returned. An alternation is, as Problem 108. did, using two variables left and right.
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
return helper(new CurNode(head), size);
}
// build a class to store curNode
private class CurNode {
ListNode node;
CurNode(ListNode node) {
this.node = node;
}
}
private TreeNode helper(CurNode cur, int size) {
if (size <= 0) {
return null;
}
TreeNode left = helper(cur, size / 2);
TreeNode root = new TreeNode(cur.node.val);
cur.node = cur.node.next;
TreeNode right = helper(cur, size - 1 - size / 2);
root.left = left;
root.right = right;
return root;
}
}
Using left and right variables, and the size of subtree is right - left + 1:
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
return helper(new CurNode(head), 0, size -1);
}
// build a class to store curNode
private class CurNode {
ListNode node;
CurNode(ListNode node) {
this.node = node;
}
}
private TreeNode helper(CurNode cur, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode leftNode = helper(cur, left, mid - 1);
TreeNode root = new TreeNode(cur.node.val);
cur.node = cur.node.next;
TreeNode rightNode = helper(cur, mid + 1, right);
root.left = leftNode;
root.right = rightNode;
return root;
}
}
Another way to implement this bottom-up approach is to use a instance varialbe curNode, which is sharing by the methods in the class.
public class Solution {
private ListNode curNode;
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
curNode = head;
return helper(size);
}
private TreeNode helper(int size) {
if (size <= 0) {
return null;
}
TreeNode leftNode = helper(size / 2);
TreeNode root = new TreeNode(curNode.val);
curNode = curNode.next;
TreeNode rightNode = helper(size - 1 - size / 2);
root.left = leftNode;
root.right = rightNode;
return root;
}
}
Comparing to define a custom class to store the curNode variable, this instance-variable mehtod is not recommended because the instance field might be changed by other methods
113. Path Sum II
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:
It is a typical DFS problem. I came up with two ways to implement it:
- add next TreeNode to the path, then DFS;
- add current TreeNode to the path;
The base cases are different for these two different implementation.
The 1st way of implementation:
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if (root == null) {
return results;
}
List<Integer> result = new ArrayList<>();
result.add(root.val);
helper(root, sum - root.val, result, results);
return results;
}
private void helper(TreeNode root, int target, List<Integer> result, List<List<Integer>> results) {
if (target == 0 && root.left == null && root.right == null) {
results.add(new ArrayList(result));
return;
}
if (root.left != null) {
result.add(root.left.val);
helper(root.left, target - root.left.val, result, results);
result.remove(result.size() - 1);
}
if (root.right != null) {
result.add(root.right.val);
helper(root.right, target - root.right.val, result, results);
result.remove(result.size() - 1);
}
}
}
The 2nd way of implementation:
public class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> results = new ArrayList<>();
if (root == null) {
return results;
}
List<Integer> result = new ArrayList<>();
helper(root, sum, result, results);
return results;
}
private void helper(TreeNode root, int target, List<Integer> result, List<List<Integer>> results) {
if (root == null) {
return;
}
result.add(root.val);
target -= root.val;
if (target == 0 && root.left == null && root.right == null) {
results.add(new ArrayList(result));
} else {
helper(root.left, target, result, results);
helper(root.right, target, result, results);
}
result.remove(result.size() - 1);
}
}
114. Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
Hints: If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Solution:
By the hint, it is a pre-order problem.
Method 1, pre-order traversal iteratively:
public class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
helper(root);
}
private void helper(TreeNode root) {
Deque<TreeNode> stack = new LinkedList<>();
TreeNode dummy = new TreeNode(0);
TreeNode cur = dummy;
stack.offerFirst(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollFirst();
if (node.right != null) {
stack.offerFirst(node.right);
}
if (node.left != null) {
stack.offerFirst(node.left);
}
cur.left = null;
cur.right = node;
cur = node;
}
}
}
Method 2, pre-order traversal recursively, an instance variable is needed(not recommended).
One trick here is that root.right is changed when calling the left subtree at next level of recursion, so root.right needs to be stored in advance.
public class Solution {
private TreeNode cur = null;
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (cur != null) {
cur.left = null;
cur.right = root;
} else {
cur = root;
}
cur = root;
TreeNode right = root.right;
flatten(root.left);
flatten(right);
}
}
116. Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example, Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
Solution:
My first idea is to use level order traversal, while its space complexity is O(n), not constant as the problem required.
There is a O(1) space solution. The idea is that, consider it as two while loops: one outer while loop and one nested while loop. The outer while loop will go through the leftmost path from the root, i.e., [1, 2] in the example, and the inner while loop will take each node from the outer while loop and work on its next level of nodes from left to right, i.e., [2, 3] and [4, 5, 6, 7].
Assume the outer while loop stops at node 2, the inner while loop will make 4->5 and 5->6 by
node.left.next = node.right;
if (node.next != null) {
node.right.next = node.next.left;
}
// move node from 2 to 3;
node = node.next;
That is the body of the inner while loop. The complete soluton is below.
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
while (root != null && root.left != null) {
TreeLinkNode node = root;
while (node != null) {
node.left.next = node.right;
if (node.next != null) {
node.right.next = node.next.left;
}
node = node.next;
}
root = root.left;
}
}
}
117. Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example, Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
Solution:
Comparing to Problem 116. Populating Next Right Pointers in Each Node, the binary tree is not necessary perfect here. What is the difference?
Let's see the example in the problem description. If we use the solution of Problem 116, when processing node 2, make 4 -> 5, this is good, but then make 5 -> null because 2.next.left is null. So we need to modify the method to get node 7 to make 5 -> 7. Another difference is that for the outer loop, we need find the left end of each levels because node 4 might be missing.
The framework of solution is very similar to that of Problem 116, while there ares some difference:
- The while loop is
while (root != null)notroot != null && root.left != nullbecause root.left might be null here. - Variable
nextis representing the left end node of next level, which can be found during processing the current level. - Variable
preis representing the last processed node at next level, for example, after we make 4 -> 5, pre is Node 5, then after we find Node 7, we make 5 -> 7, and pre becomes Node 7. - For
cur.leftandcur.right, process separately. Ifpre == nullwhich means processing just starts, setpre == cur.leftifcur.left != null; ifpre != null, thenpre.next = cur.leftaccording to the definition ofpreand movepreone step right.
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) {
return;
}
while (root != null) {
TreeLinkNode cur = root;
// the left end of next level
TreeLinkNode next = null;
// the last scanned node of next level
TreeLinkNode pre = null;
while (cur != null) {
// looking for the left end of next level until found
if (next == null) {
next = (cur.left != null) ? cur.left : cur.right;
}
if (cur.left != null) {
if (pre != null) {
pre.next = cur.left;
pre = pre.next;
} else {
pre = cur.left;
}
}
if (cur.right != null) {
if (pre != null) {
pre.next = cur.right;
pre = pre.next;
} else {
pre = cur.right;
}
}
cur = cur.next;
}
root = next;
}
}
}
There is another way to find next which is the left end of next level: dummy node.
while (root != null) {
TreeLinkNode cur = root;
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode pre = dummy;
while (cur != null) {
// same as previous implementation
}
root = dummy.next;
}
127. Word Ladder
Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:
- Only one letter can be changed at a time.
- Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,
Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
- You may assume no duplicates in the word list.
- You may assume beginWord and endWord are non-empty and are not the same.
UPDATE (2017/1/20):
The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
Solution:
This is a BFS problem. Starting from the beginWord, we can find all nextWords which are differed by one letter in the wordList, and from these nextWords, continue to find nextWords at next level of BFS until endWord has been found. In BFS, the shortest of path is the number of levels it explored.
Now let's think about some details. How to get nextWord for a word A? There are two ways:
- iterate the wordList to check if it is differed to A by one letter. Time complexity is O(mn) where m is the size of wordList and n is length of word A;
- change word A by one letter, check if it is in the wordList. Time complexity is O(mn*26);
It seems the 1st way is better. But the update in the problem told us that the wordList was Set, and we know that looking up in Set is O(1). To make use of the constant time look-up feature of Set, we can transform the wordList to a Set at the begining. If the wordList is a Set now, which is better among the above two ways?
- Time complexity is still O(mn);
- Time complexity is O(26n);
So we choose the 2nd way to get nextWord.
Another trick is that we need to mark visited words in BFS. We can use a Set to store all visited words. Or you can use a Map whose value is true if key is visited, false if key is not visited, either way works.
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//assumptions in the note
Set<String> dict = new HashSet<>();
for (String word : wordList) {
dict.add(word);
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
visited.add(beginWord);
int length = 1;
while (!queue.isEmpty()) {
length++;
int size = queue.size();
for (int i = 0; i < size; i++) {
String word = queue.poll();
for (String nextWord : getNextWords(word, dict)) {
if (visited.contains(nextWord)) {
continue;
}
if (nextWord.equals(endWord)) {
return length;
} else {
visited.add(nextWord);
queue.offer(nextWord);
}
}
}
}
return 0;
}
private List<String> getNextWords(String word, Set<String> dict) {
List<String> result = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(i)) {
continue;
}
String nextWord = replace(word, i, c);
if (dict.contains(nextWord)) {
result.add(nextWord);
}
}
}
return result;
}
private String replace(String word, int i, char c) {
char[] chars = word.toCharArray();
chars[i] = c;
return new String(chars);
}
}
The solution above is accepted in LeetCode platform. Can it be further improved?
Because the beginWord and endWord are known in this problem, so it can be solved by bidirectional BFS. The traditional BFS is one-directional, which means the iteration map is a triangle from the tip to the widest edge. For bidirectional BFS, it is started from the beginWord and endWord separately, and the stop condition is one node has been marked by the other direction.
Is bidirectional BFS is simply two BFS? Almost. There is one tiny thing for this problem. The assumption is that the beginWord is not in the wordList and endWord is in the wordList. This assumption is good for the one-directional BFS because the endWord is found as a transformed word during BFS. But for bidirectional BFS, we need to check wheter the endWord is in the wordList at the beginning.
public class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//assumptions in the note
Set<String> dict = new HashSet<>();
for (String word : wordList) {
dict.add(word);
}
if (!dict.contains(endWord)) {
return 0;
}
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
Set<String> rvisited = new HashSet<>();
Queue<String> rqueue = new LinkedList<>();
queue.offer(beginWord);
visited.add(beginWord);
rqueue.offer(endWord);
rvisited.add(endWord);
int length = 1;
int rlength = 1;
while (!queue.isEmpty() && !rqueue.isEmpty()) {
int size = queue.size();
int rsize = rqueue.size();
if (length < rlength) {
length++;
for (int i = 0; i < size; i++) {
String word = queue.poll();
for (String nextWord : getNextWords(word, dict)) {
if (visited.contains(nextWord)) {
continue;
}
if (rvisited.contains(nextWord)) {
return length + rlength - 1;
} else {
visited.add(nextWord);
queue.offer(nextWord);
}
}
}
} else {
rlength++;
for (int i = 0; i < rsize; i++) {
String word = rqueue.poll();
for (String nextWord : getNextWords(word, dict)) {
if (rvisited.contains(nextWord)) {
continue;
}
if (visited.contains(nextWord)) {
return length + rlength - 1;
} else {
rvisited.add(nextWord);
rqueue.offer(nextWord);
}
}
}
}
}
return 0;
}
private List<String> getNextWords(String word, Set<String> dict) {
List<String> result = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
for (char c = 'a'; c <= 'z'; c++) {
if (c == word.charAt(i)) {
continue;
}
String nextWord = replace(word, i, c);
if (dict.contains(nextWord)) {
result.add(nextWord);
}
}
}
return result;
}
private String replace(String word, int i, char c) {
char[] chars = word.toCharArray();
chars[i] = c;
return new String(chars);
}
}
129. Sum Root to Leaf Numbers
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
Solution:
It is a typical DFS problem.
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root, 0);
}
private int helper(TreeNode root, int prev) {
if (root.left == null && root.right == null) {
return prev * 10 + root.val;
}
int sum = 0;
if (root.left != null) {
sum += helper(root.left, prev * 10 + root.val);
}
if (root.right != null) {
sum += helper(root.right, prev * 10 + root.val);
}
return sum;
}
}
Another way of implementation:
public class Solution {
public int sumNumbers(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root, 0);
}
private int helper(TreeNode root, int prev) {
if (root == null) {
return 0;
}
int sum = prev * 10 + root.val;
if (root.left == null && root.right == null) {
return sum;
}
return helper(root.left, sum) + helper(root.right, sum);
}
}
130. Surrounded Regions
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
Solution:
Omm this is a interesting problem. It asks to find all 'O's surrounded by 'X's and change them to 'X's. From the example we can see that 'O's are not surrounded by 'X's only if part of the 'O's cluster are on the boundary.
A clever idea is to find all 'O's not surrounded by 'X's. If so, they can be marked by some temporary value, then iterating the whole board to flip 'O's to 'X's, and finally restore the cells with temporary values to 'O's.
How to find all 'O's not surrounded by 'X's?
It is simple. From the cells with 'O' on the edge rows and edge columns, do BFS or DFS.
Below is a solution with BFS. It is a good practice.
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int col = board[0].length;
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
helper(i, 0, board);
}
if (board[i][col - 1] == 'O') {
helper(i, col - 1, board);
}
}
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O') {
helper(0, i, board);
}
if (board[row - 1][i] == 'O') {
helper(row - 1, i, board);
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
switch(board[i][j]) {
case 'O':
board[i][j] = 'X';
break;
case 'E':
board[i][j] = 'O';
}
}
}
}
private void helper(int i, int j, char[][] board) {
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(i, j));
board[i][j] = 'E';
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (Node node : expand(board, cur)) {
queue.offer(node);
}
}
}
private List<Node> expand(char[][] board, Node node) {
List<Node> expansion = new ArrayList<>();
int[] directionX = {1, -1, 0, 0};
int[] directionY = {0, 0, 1, -1};
for (int i = 0; i < directionX.length; i++) {
int x = node.x + directionX[i];
int y = node.y + directionY[i];
if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O') {
board[x][y] = 'E';
expansion.add(new Node(x, y));
}
}
return expansion;
}
private class Node {
int x;
int y;
Node(int x, int y) {
this.x = x;
this.y = y;
}
}
}
There is another BFS implementation in the internet and I think it worth to share. In the 1st implementation, we did multiple BFSs from the board boundaries, actually one BFS is enough. It is good to break thinking tendency.
Also in the 1st implementation, a Node class is defined to represent a board cell. It is not necessary because you can transform the cell index (x, y) to number x * col + y and store it in the queue.
public class Solution {
public void solve(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int col = board[0].length;
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < row; i++) {
if (board[i][0] == 'O') {
queue.offer(index(i, 0, col));
}
if (board[i][col - 1] == 'O') {
queue.offer(index(i, col - 1, col));
}
}
for (int i = 1; i < col - 1; i++) {
if (board[0][i] == 'O') {
queue.offer(index(0, i, col));
}
if (board[row - 1][i] == 'O') {
queue.offer(index(row - 1, i, col));
}
}
int[] directionX = {1, -1, 0, 0};
int[] directionY = {0, 0, 1, -1};
while (!queue.isEmpty()) {
int cur = queue.poll();
int x = cur / col;
int y = cur % col;
board[x][y] = 'E';
for (int i = 0; i < directionX.length; i++) {
int x2 = x + directionX[i];
int y2 = y + directionY[i];
if (x2 >= 0 && x2 < row && y2 >= 0 && y2 < col && board[x2][y2] == 'O') {
board[x2][y2] = 'E';
queue.offer(index(x2, y2, col));
}
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
switch(board[i][j]) {
case 'O':
board[i][j] = 'X';
break;
case 'E':
board[i][j] = 'O';
}
}
}
}
private int index(int x, int y, int col) {
return x * col + y;
}
}
131. Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[
["aa","b"],
["a","a","b"]
]
Solution:
First we need to understand the problem precisely. It is asked to break the string s into parlindrome substrings(all substrings need to be parlindrome).
It is a DFS problem. The DFS recursion tree is a K-branches tree, in other words, the number of branches is not determinable. From left to right, pick a substring [i, j] to see if it is parlindrome, if so continue to pick next substring [j + 1, k] by DFS.
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> results = new ArrayList<>();
if (s == null || s.length() == 0) {
return results;
}
List<String> result = new ArrayList<>();
helper(s, 0, result, results);
return results;
}
private void helper(String s, int start, List<String> result, List<List<String>> results) {
if (start == s.length()) {
results.add(new ArrayList<String>(result));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
result.add(s.substring(start, i + 1));
helper(s, i + 1, result, results);
result.remove(result.size() - 1);
}
}
}
private boolean isPalindrome(String s, int left, int right) {
while (left <= right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
Time complexity is O(nn) because there are at most n levels in the recursion tree and at most n branches. Remember big O represents upper bound. Can the time complexity be more bounded? I don't know.
There is an improvement for it. It is not likely that you will be asked about this improvement and I think the DFS solution above is good enough.
This improvement shares similar idea with Problem 5. Longest Palindromic Substring.
In the original DFS solution, it makdes more than enough comparisons. For example, the input string is aaccdd, in a DFS path(from root to leaf of the recursion tree), we pick aa, cc and dd, but later in another DFS path we pick aacc and dd. There is redundancy when calculating aa, cc and aacc. The idea is to build a 2D palindrome map and map[i][j] represents the substring [i, j] is palindrome or not. The efficient way to build the map is from the center of the string to the two ends.
The code is copied from jiuzhang.
public class Solution {
List<List<String>> results;
boolean[][] isPalindrome;
/**
* @param s: A string
* @return: A list of lists of string
*/
public List<List<String>> partition(String s) {
results = new ArrayList<>();
if (s == null || s.length() == 0) {
return results;
}
getIsPalindrome(s);
helper(s, 0, new ArrayList<Integer>());
return results;
}
private void getIsPalindrome(String s) {
int n = s.length();
isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++) {
isPalindrome[i][i] = true;
}
for (int i = 0; i < n - 1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
for (int i = n - 3; i >= 0; i--) {
for (int j = i + 2; j < n; j++) {
isPalindrome[i][j] = isPalindrome[i + 1][j - 1] && s.charAt(i) == s.charAt(j);
}
}
}
private void helper(String s,
int startIndex,
List<Integer> partition) {
if (startIndex == s.length()) {
addResult(s, partition);
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (!isPalindrome[startIndex][i]) {
continue;
}
partition.add(i);
helper(s, i + 1, partition);
partition.remove(partition.size() - 1);
}
}
private void addResult(String s, List<Integer> partition) {
List<String> result = new ArrayList<>();
int startIndex = 0;
for (int i = 0; i < partition.size(); i++) {
result.add(s.substring(startIndex, partition.get(i) + 1));
startIndex = partition.get(i) + 1;
}
results.add(result);
}
}
In the code above, do you notice that it record the indices along the path of DFS recursion tree rather than calling the API substring? It translatet the list of indices to list of strings. This way of implementation is more efficient because those unsucessful pathes in the DFS recursion tree do not show in the result List, so calling substring API during the whole DFS process(including sucessful pathes and failed pathes) will be definitely more frequent than only calling substring API on those sucessful paths, which are the indices stored in the result List.
This trick can apply to the previous method too. It is a good follow up.
133. Clone Graph
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization: Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node. As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
- First node is labeled as 0. Connect node 0 to both nodes 1 and
- Second node is labeled as 1. Connect node 1 to node 2.
- Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Solution:
It can be solved by either BFS or DFS.
Remember that in a graph traversal problem, usually we need a HashSet/HashMap to mark the visited nodes. In some cases we don't need HashSet/Map because the graphs are special, for example, a tree and we are traversing from root to leaf without turning back, or a 2D array and we are traversing from top left to bottom right without turnning back. In short, if the BFS/DFS traversal can not make a circle, then you don't need additional data structure to mark visited nodes.
Now for this problem, definitely we need a HashMap, which has two roles:
- mark visited;
- store the 1-1 relationship of oldNode to newNode;
Method 1: BFS
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Queue<UndirectedGraphNode> queue = new LinkedList<>();
UndirectedGraphNode head = new UndirectedGraphNode(node.label);
map.put(node, head);
queue.offer(node);
while (!queue.isEmpty()) {
UndirectedGraphNode cur = queue.poll();
for(UndirectedGraphNode neighbor : cur.neighbors) {
if (!map.containsKey(neighbor)) {
queue.offer(neighbor);
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
}
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return head;
}
}
Method 2: DFS
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
UndirectedGraphNode head = new UndirectedGraphNode(node.label);
map.put(node, head);
dfs(map, node);
return head;
}
private void dfs(Map<UndirectedGraphNode, UndirectedGraphNode> map, UndirectedGraphNode node) {
for (UndirectedGraphNode neighbor : node.neighbors) {
if (!map.containsKey(neighbor)) {
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
dfs(map, neighbor);
}
map.get(node).neighbors.add(map.get(neighbor));
}
}
}
134. Gas Station
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note: The solution is guaranteed to be unique.
Solution:
This is a interesting problem. My first 2cents:
If the total amount of gas < total cost of visiting all stations, it is impossible to visit all stations. OK, the problem says there is one unique solution, so total gas >= total cost. What next?
Let's go through an example.
- initially tank is empty, and start from the 0th station, solution stored in
index = 0; - at the 0th station,
tank = gas[0], iftank >= cost[0], can reach station 1; - at the 1st station,
tank += gas[1], iftank >= cost[1], can reach station 2; - what if
tank < cost[1]? can not reach station 2. So from station 0, we can not reach station 2, and further we know from station 1 we can not reach station 2 either. Why? We know that station 0 can reach station 1 and can not reach station 2. If the trip starting from station 1 with empty tank can reach station 2, then the origial trip from station 0 stops at station 1 with gas in tank >= 0 must can reach station 2 too. There is a contradiction! - from step 4, so if
tank < cost[1], makeindex = 2andtank = 0; - finally if
totalGas >= totalCost, returnindex; otherwise-1.
The solution is just simulating the process I just described.
public class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if (gas == null || cost == null || gas.length == 0 || cost.length == 0) {
return -1;
}
int tank = 0;
// totalGas - totalCost
int total = 0;
int index = 0;
for(int i = 0; i< gas.length; i++) {
tank += gas[i] - cost[i];
total += gas[i] - cost[i];
if(tank < 0) {
index = i + 1;
tank = 0;
}
}
return total < 0 ? -1 : index;
}
}
This solution assumes that there is one station starting from which can traverse all other stations. What about no such station exists? If so, the solution above will get index's value equals to gas.length.
137. Single Number II
Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Solution:
Method 1: use Map. It is linear time but O(n) space.
One trick is that if a number is in the map as key and the value is 2, then delete it from the map because this number shows three times; otherwise value increase by one. Finally there is only one number in the map, which is the answer.
Method 2:
The 'Int' type in Java has 32 bits. So use an array whose size is 32 to record the occurrence of '1' at that bit.
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null) {
throw new IllegalArgumentException("array is null");
}
int[] bitNum = new int[32];
int result = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < nums.length; j++) {
bitNum[i] += (nums[j] >> i) & 1;
}
result |= (bitNum[i] % 3) << i;
}
return result;
}
}
Time complexity is O(32n) and space complexity is O(1). This is a general solution. If all numbers show *k times except one number shows exactly once, this method can solve it.
Method 3: a special method only works for this problem.
Use three varialbes: one, two and three to simulate ternary. Assuming for one particular bit: if there is a 1, one = 1, two =0, three = 0; another 1, one = 0, two = 1, three 0; anther 1, one = 1, two = 1, three = 0 then changes to one = 0, two = 0, three = 1. Finally return one which stores all bits appearance once.
public class Solution {
public int singleNumber(int[] nums) {
if (nums == null) {
throw new IllegalArgumentException("array is null");
}
int one=0, two=0, three=0;
for(int i = 0; i < nums.length; i++){
two |= one & nums[i];
one ^= nums[i];
//cout<<one<<endl;
three = one & two;
one &= ~three;
two &= ~three;
}
return one;
}
}
It is very difficult to understand. Nobody will ask you about this solution. I will explain the line two |= one & nums[i] for myself:
If a bit in nums[i] is 1 and the corresponding bit in one is 1 too, then the bit in two need to be 1, and reset the bit in one to 0. This is one case. Why one ^= nums[i]? It is summarized from different cases. I will stop here because it does not worth my time.
138. Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
Solution:
Definitely we can use BFS or DFS, as Problem 133. Clone Graph did. But it looks like using a musket to kill a butterfly because this is a LinkedList.
Method 1:
- Iterate the LinkedList to copy all nodes and theirs next variables. Use a HahsMap to store 1-1 relationship between oldNode and newNode.
- Iterate the original LinkedList again to copy their random variable to the corresponding newNode with the help of HashMap.
Methdo 2:
Similar to Method 1, just combine the two steps into one round iteration. head is iterating the original LinkedList and newNode is building the new LinkedList.
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
Map<RandomListNode, RandomListNode> map = new HashMap<>();
RandomListNode dummy = new RandomListNode(0);
RandomListNode pre = dummy;
RandomListNode newNode;
while (head != null) {
if (map.containsKey(head)) {
newNode = map.get(head);
} else {
newNode = new RandomListNode(head.label);
}
pre.next = newNode;
if (head.random != null) {
if (map.containsKey(head.random)) {
newNode.random = map.get(head.random);
} else {
newNode.random = new RandomListNode(head.random.label);
map.put(head.random, newNode.random);
}
}
pre = newNode;
head = head.next;
}
return dummy.next;
}
}
Method 3:
This is a very smart method.
In previous methods, we need a HashMap to store the 1-1 relationship between oldNode and newNode. There is another way to store this information: put the newNode after the newNode. For example, the original LinkedList is 1 -> 2 -> 3, first we build new nodes with next field copied to get 1 -> 1' -> 2 -> 2' -> 3 -> 3'. Now we know how the 1-1 relationship are stored withouth HashMap. Then iterate the new LinkedList to copy the random variable from old nodes to new nodes and delete the old nodes.
Code is from jiuzhang.
public class Solution {
private void copyNext(RandomListNode head) {
while (head != null) {
RandomListNode newNode = new RandomListNode(head.label);
newNode.random = head.random;
newNode.next = head.next;
head.next = newNode;
head = head.next.next;
}
}
private void copyRandom(RandomListNode head) {
while (head != null) {
if (head.next.random != null) {
head.next.random = head.random.next;
}
head = head.next.next;
}
}
private RandomListNode splitList(RandomListNode head) {
RandomListNode newHead = head.next;
while (head != null) {
RandomListNode temp = head.next;
head.next = temp.next;
head = head.next;
if (temp.next != null) {
temp.next = temp.next.next;
}
}
return newHead;
}
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return null;
}
copyNext(head);
copyRandom(head);
return splitList(head);
}
}
Time complexity is O(n) and space complexity is O(1).
139. Word Break
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
UPDATE (2017/1/4): The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.
Solution:
It looks like a DFS problem whose recursion tree is K-branches. If you agree, you are on the right track.
It can be solved by DP.
142. Linked List Cycle II
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:
The idea of the solution is described in Problem
143. Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
Solution:
This is a combination of several basic operations:
- Find the middle node and break the LinkedList;
- Reverse the 2nd half part of the LinkedList to get Ln->Ln-1->Ln-2...;
- Merge the reversed LinkedList from step 2 with the 1st half part of the original LinkedList;
Solution:
144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
Soluton:
147. Insertion Sort List
Sort a linked list using insertion sort.
Solution:
148. Sort List
Sort a linked list in O(nlogn) time using constant space complexity.
Solution:
To get O(nlogn) time complexity, it is straightforward to think about merge sort and quick sort.
Method 1: merge sort.
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode right = sortList(mid.next);
mid.next = null;
ListNode left = sortList(head);
return merge(left, right);
}
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
if (left == null) {
tail.next = right;
} else {
tail.next = left;
}
return dummy.next;
}
}
The code above is quite straightforward. One possible mistake is that if the input LinkedList is 1 -> 2, findMiddle should return node 1, not node 2.
Method 2: quick sort.
The code is from jiuzhang.
Some points about the implementation:
- The middle node is chosen as the pivot, other points also works;
- Then iterate the LinkedList to get three sublists: left list(< pivot.val), middle list(== pivot.val) and right list(> pivot.val). Why three sublists? Because by so we konw the pivot must be in the middle list. For the array version of quick sort, after the pivot has been selected, the whole array is iterated except the pivot by moving the pivot to the tail of the array. In LinkedList, we have to cut the pivot node out, then partition the whole LinkedList except the pivot node. To use three sublists can perfectly avoid the mess to cut the pivot node out.
After got the three sublists and partition the left list and right list, we need to concat them. The method is
concat(left, middleDummy.next, right)which callsgetTail.private ListNode concat(ListNode left, ListNode middle, ListNode right) { ListNode dummy = new ListNode(0); ListNode tail = dummy; tail.next = left; // getTail(left) is wrong because left may be null tail = getTail(tail); tail.next = middle; tail = getTail(tail); tail.next = right; return dummy.next; }In the array version of quick sort, we don't need
concatbecause it is array!
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = findMiddle(head);
ListNode leftDummy = new ListNode(0);
ListNode leftTail = leftDummy;
ListNode rightDummy = new ListNode(0);
ListNode rightTail = rightDummy;
ListNode middleDummy = new ListNode(0);
ListNode middleTail = middleDummy;
// partition
while (head != null) {
if (head.val < mid.val) {
leftTail.next = head;
leftTail = leftTail.next;
} else if (head.val > mid.val) {
rightTail.next = head;
rightTail = rightTail.next;
} else {
middleTail.next = head;
middleTail = middleTail.next;
}
head = head.next;
}
leftTail.next = null;
rightTail.next = null;
middleTail.next = null;
ListNode left = sortList(leftDummy.next);
ListNode right = sortList(rightDummy.next);
return concat(left, middleDummy.next, right);
}
private ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode concat(ListNode left, ListNode middle, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
tail.next = left;
tail = getTail(tail);
tail.next = middle;
tail = getTail(tail);
tail.next = right;
return dummy.next;
}
private ListNode getTail(ListNode head) {
if (head == null) {
return null;
}
while (head.next != null) {
head = head.next;
}
return head;
}
}
150. Evaluate Reverse Polish Notation
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
Solution:
151. Reverse Words in a String
Given an input string, reverse the string word by word.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Update (2015-02-12): For C programmers: Try to solve it in-place in O(1) space.
Clarification:
- What constitutes a word?
- A sequence of non-space characters constitutes a word.
- Could the input string contain leading or trailing spaces? Yes. However, your reversed string should not contain leading or trailing spaces.
- How about multiple spaces between two words? Reduce them to a single space in the reversed string.
Solution:
In Java, String is immutable so it has to use extra space. The simplest method is to use String's API: split, as the code below shows.
public class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return "";
}
String[] array = s.split("\\s+");
StringBuilder sb = new StringBuilder();
for (int i = array.length - 1; i >= 0; --i) {
if (!array[i].equals("")) {
sb.append(array[i]).append(" ");
}
}
//remove the last " "
return sb.length() == 0 ? "" : sb.substring(0, sb.length() - 1);
}
}
If the input is char array or we are not allowed to use the API split, what are we going to do?
We can transfer the input String to char array, then apply the trick "I love coding".
152. Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
Solution:
It is a variant to Problem 53. Maximum Subarray.
The definition of the 1D array M[i] is similar: M[i] represents the maximum product of a subarray from the 0-th number to the i-th number, including the i-th number. We also need a global variable result to record the maximum product.
How to get the maximum product? It has two cases because of the sign of numbers: during the iteration, we need maintain two variable preMax and preMin(I didn't use 1D array to achieve O(1) space complexity).
- if a number is positive, the maximum product including this number is
Math.max(nums[i], preMax * nums[i]), the minimum product including this number isMath.min(nums[i], preMin * nums[i]); - if a number is negative, then the maximum product including this number is
Math.max(nums[i], preMin * nums[i]), the minimum product including this number isMath.min(nums[i], preMax * nums[i]);
public class Solution {
public int maxProduct(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("input not valid");
}
int min = nums[0];
int minPre = nums[0];
int max = nums[0];
int maxPre = nums[0];
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= 0) {
max = Math.max(maxPre * nums[i], nums[i]);
min = Math.min(minPre * nums[i], nums[i]);
} else {
max = Math.max(minPre * nums[i], nums[i]);
min = Math.min(maxPre * nums[i], nums[i]);
}
result = Math.max(result, max);
maxPre = max;
minPre = min;
}
return result;
}
}
Inside the for loop, there is another implementation to get max and min. Either way works.
max = Math.max(nums[i], Math.max(maxPre * nums[i], minPre * nums[i]));
min = Math.min(nums[i], Math.min(maxPre * nums[i], minPre * nums[i]));
153. Find Minimum in Rotated Sorted Array
Suppose an array sorted in ascending order 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).
Find the minimum element.
You may assume no duplicate exists in the array.
Solution:
It is a variant of Problem 33. Search in Rotated Sorted Array I. The idea is that in all possible rotations, there are two cases.
l mid r
0 1 2 3 4 5 6 7 no rotation
1 2 3 4 5 6 7 0
2 3 4 5 6 7 0 1
3 4 5 6 7 0 1 2
4 5 6 7 0 1 2 3
5 6 7 0 1 2 3 4
6 7 0 1 2 3 4 5
7 0 1 2 3 4 5 6
input[left] < input[mid], soinput[left:mid]is sorted;input[left] > input[mid], soinput[mid:right]is sorted;
How to get the minimum?
If
input[left] > input[mid], the minimum is always ininput[left:mid]by observing all rotations;If
input[left] < input[mid], the minimum is always ininpus[mid:right]except if not rotated; if not rotated, the minimum isinput[left];
So we need to check if rotated or not first, use if (input[left] < input[right]).
The complete code is below. It uses "left-right" pointers method.
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("input not valid");
}
int left = 0;
int right = nums.length - 1;
// if no rotation
if (nums[left] < nums[right]) {
return nums[left];
}
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[left] < nums[mid]) {
left = mid;
} else {
right = mid;
}
}
return nums[left] < nums[right] ? nums[left] : nums[right];
}
}
If I comment out if (nums[left] < nums[right]), the result is wrong for not-rotated array.
Is it necessary to check rotation first? The answer is no. We can compare input[mid] with input[right]:
- If
input[mid] < input[right], the minimus is always ininput[left:mid]; - If
input[mid] > input[right], the minimus is always ininput[mid:right];
So comparing input[left] with input[mid] is not equivalent to comparing input[mid] with input[right]. Why? I don't know, just from observation.
public class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("input not valid");
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid;
}
}
return nums[left] < nums[right] ? nums[left] : nums[right];
}
}
162. Find Peak Element
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞.
For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.
Solution:
The O(n) solution is naive: use three variables to iterate the array.
How to get a O(logn) solution? O(logn) -> binary search.
Firsty the peak element must exists because the assumption num[-1] = num[n] = -∞. You need understand this because we are going to use this conclusion all the time.
Let's review binary search again. There are two key points:
- Every time reduce the size of problem to half;
- Make sure the half input which has been throw away does not contain the final answer we want;
For this problem, if we got input[mid], there are two cases:
- If
input[mid] > input[mid + 1], there must be a peak element ininput[0:mid]because of the conclustion I just mentioned above; - If
input[mid] < input[mid + 1], there must be a peak element ininput[mid + 1:length - 1];
Remember we just need return one peak element, not all, so we can safely throw away half input as long as long there is one peak element there. Obviously if it is asked to return all peak elements, only iteration works out.
Use the "left-right" pointers method.
public class Solution {
public int findPeakElement(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("input not valid");
} else if (nums.length == 1) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left] > nums[right] ? left : right;
}
}
The implementation above strictly obey the two principles of binary search.
165. Compare Version Numbers
Compare two version numbers version1 and version2. If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
You may assume that the version strings are non-empty and contain only digits and the . character. The . character does not represent a decimal point and is used to separate number sequences. For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.
Here is an example of version numbers ordering:
0.1 < 1.1 < 1.2 < 13.37
Solution:
Method 1: use API split and parseInt.
Method 2: iterate both strings to get the number separated by .. It is faster than the 1st method, but more lines.
public class Solution {
public int compareVersion(String version1, String version2) {
if (version1 == null || version2 == null) {
throw new IllegalArgumentException("input not valid");
}
int i = 0;
int j = 0;
int num1 = 0;
int num2 = 0;
while (i < version1.length() || j < version2.length()) {
num1 = 0;
num2 = 0;
while (i < version1.length() && version1.charAt(i) != '.') {
num1 = num1 * 10 + version1.charAt(i) - '0';
i++;
}
//then skip '.'
i++;
while (j < version2.length() && version2.charAt(j) != '.') {
num2 = num2 * 10 + version2.charAt(j) - '0';
j++;
}
j++;
if (num1 < num2) {
return -1;
} else if (num1 > num2) {
return 1;
}
}
return 0;
}
}
166. Fraction to Recurring Decimal
Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".
Solution:
The key insight here is to notice that once the remainder starts repeating, so does the divided result. To alert the repeat of remainder, we need a HashMap whose key is the remainder and value is the position of the fractional part. We may enclose the reoccurring fractional part with parentheses, then return.
If the remainder is zero, return.
Beware of the corner case such as negative fractions and zero. Transform 'int' type to 'long' type because there is a test case -2147483648 / -1.
public class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (denominator == 0) {
throw new IllegalArgumentException("input not valid");
} else if (numerator == 0) {
return "0";
}
long nume = Math.abs((long) numerator);
long deno = Math.abs((long) denominator);
String sign = (numerator < 0) ^ (denominator < 0) ? "-" : "";
long rem = nume % deno;
long ans = nume / deno;
if (rem == 0) {
return sign + ans;
}
Map<Long, Integer> map = new HashMap<>();
StringBuilder sb = new StringBuilder();
sb.append(sign + ans + ".");
while (rem != 0) {
rem = rem * 10;
if (map.containsKey(rem)) {
int start = map.get(rem);
sb.insert(start, "(");
sb.append(")");
return sb.toString();
} else {
map.put(rem, sb.length());
sb.append(rem/deno);
rem = rem % deno;
}
}
return sb.toString();
}
}
173. Binary Search Tree Iterator
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Solution:
To iterate the BST in ascending order, we need use in-order traversal. A not good solution is to put in-order traversal into a list then output one by one, unfortunately the problem asks for O(h) space.
It can be solved by the iterative in-order traversal. We need a variable next to store next visiting node and subtree.
- While
nextis not null, pushnextto stack and go left; - If
nextis null, means the left subtree of the root is finished(the root is the top element in the stack). Print the top and letnext = top.right; - do previous steps until
nextis null and stack is empty;
The iterative in-order traversal code is below:
public List<Integer> inOrder(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new LinkedList<>();
TreeNode next = root;
while (next != null || !stack.isEmpty()) {
if (next != null) {
stack.offerFirst(next);
next = next.left;
} else {
cur = stack.pollFirst();
result.add(cur.val);
cur = cur.right;
}
}
return result;
}
Based on this, We can implement the iterator code:
public class BSTIterator {
private Deque<TreeNode> stack = new LinkedList<>();
private TreeNode next = null;
public BSTIterator(TreeNode root) {
while (root != null) {
stack.offerFirst(root);
root = root.left;
}
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
/** @return the next smallest number */
public int next() {
// assume next exists
// return type should be Integer, return null to handle if (!hasNext())
TreeNode cur = stack.pollFirst();
next = cur.right;
while (next != null) {
stack.offerFirst(next);
next = next.left;
}
return cur.val;
}
}
Below is copied from jiuzhang. Can you spot the difference? Which one is better?
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
private Deque<TreeNode> stack = new LinkedList<>();
private TreeNode next = null;
public BSTIterator(TreeNode root) {
next = root;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
if (next != null) {
addNodeToStack(next);
next = null;
}
return !stack.isEmpty();
}
private void addNodeToStack(TreeNode root) {
while (root != null) {
stack.offerFirst(root);
root = root.left;
}
}
/** @return the next smallest number */
public int next() {
// assume next exists
// return type should be Integer, return null to handle if (!hasNext())
TreeNode cur = stack.pollFirst();
next = cur.right;
return cur.val;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.hasNext()) v[f()] = i.next();
*/
Both implementations are accepted in LeetCode platform. Remember LeetCode points out at the bottom of the coding pad that the usage of the iterator is while (i.hasNext()) v[f()] = i.next(). The version of jiuzhang works for calling hasNext() then next(), but it does not work for calling next() without calling hasNext(). Do you agree with me?
My implementation works good withouth such issue.
The last thing I want to mention is that the iterative in-order traversal also satisfies average O(1) time, which is amortized time complexity.
179. Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
Solution:
This is a hard problem. I refered to the internet to solve it.
Firstly, it is obvious that sorting in natural order does not work. For example, [21, 10, 3] is listed in descending order, but we need [3, 21, 10], which makes the largest number 32110. What is this kind of order?
The answer is reversal lexicographical order(字典顺序). "Tim" will be before "Tom", which is before "Toy". In Java, comparisons between Strings uses lexicographical order.
There is still one issue. For example, in the problem description, sort [3, 30] by reversal lexicographical order will be [30, 3] becaues they share prefix and 30 is longer than 3. But the largest number is 330 which comes from [3, 30]. So we need a customized order.
The new comparator is (s1, s2) -> (s2 + s1).compareTo(s1 + s2), where s1 and s2 are Strings. This comparator simply says that put s1 ahead of s2 if s2 + s1 < s1 + s2. It works for the two situations above.
public class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
List<String> list = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
list.add(String.valueOf(nums[i]));
}
StringBuilder sb = new StringBuilder();
list.sort((s1, s2) -> (s2 + s1).compareTo(s1 + s2));
for (String s : list) {
sb.append(s);
}
// find first non-zero index, to remove leading zeros
int start = 0;
for (; start < sb.length() - 1; start++) {
if (sb.charAt(start) != '0') {
break;
}
}
sb.delete(0, start);
return sb.toString();
}
}
187. Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].
Solution:
A naive solution is to iterate the string and call the API substring, and maintain a HashSet to detect repeatedness. Time complexity is O(10*n) and space complexity is O(n).
An improvement is using Robin-Karp algorithm.
Remember we only have four letters, so we can use quaternary(四进制) number to represent a 10-letter substring. A letter is 2 bits so the 10-letter substring can be converted to a 20-bits integer.
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> result = new ArrayList<>();
if (s == null || s.length() <= 10) {
return result;
}
Map<Character, Integer> map = new HashMap<>();
map.put('A', 0);
map.put('C', 1);
map.put('G', 2);
map.put('T', 3);
Set<Integer> visited = new HashSet<>();
Set<Integer> added = new HashSet<>();
int hash = 0;
for (int i = 0; i < s.length(); i++) {
hash = (hash << 2) + map.get(s.charAt(i));
if (i >= 9) {
// make length of hash to be 20
hash = hash & ((1 << 20) - 1);
if (visited.contains(hash) && !added.contains(hash)) {
result.add(s.substring(i - 9, i + 1));
added.add(hash);
} else {
visited.add(hash);
}
}
}
return result;
}
}
It is quaternary so we can use hash << 2.
One mistake I made is:
// does not do what I want
hash = hash << 2 + map.get(s.charAt(i));
because the precedence of + is higher than <<.
199. Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
For example:
Given the following binary tree,
1 <---
/ \
2 3 <---
\ \
5 4 <---
You should return [1, 3, 4].
Solution:
This is a variant of level order traversal. We need to find the right-most TreeNode of each level.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode cur = queue.poll();
if (i == 0) {
result.add(cur.val);
}
if (cur.right != null) {
queue.offer(cur.right);
}
if (cur.left != null) {
queue.offer(cur.left);
}
}
}
return result;
}
}
200. Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
Solution:
An island is a patch of 1s which belongs to the same "group", in other words, starting from any 1 in one island, it is able to traverse the whole island. There are two solutions based on BFS and DFS, respectively.
The third solution is based on union-find set. It is a follow up of Youtube onsite(in Chinese).
Method 1: based on BFS.
One example of implementing BFS in a 2D matrix is Problem 130. Surrounded Regions. It is a good practice to go through that problem again.
For the coordinate (x, y), there are three ways to store it in a Queue:
- Create a new class "Pair" to hold x and y, as the solution of Problem 130 shows;
- Transfer
(x, y)tox * col + yto store in the Queue, and Problem 130 also shows this implementation; - Use
int[]to represent(x, y), which shows below.
To mark visited, we can create a 2D boolean matrix, in which true stands for visited. Or we can modify the visited cell to some other values, for example '0' or '2'. I '2' because you can restore the original matrix. Problem 130 also involves this idea.
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int islands = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
bfs(grid, i, j);
islands++;
}
}
}
return islands;
}
private void bfs(char[][] grid, int x, int y) {
int[] directionX = {0, 0, -1, 1};
int[] directionY = {1, -1, 0, 0};
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
grid[x][y] = '2';
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int i = 0; i < directionX.length; i++) {
int xAdj = cur[0] + directionX[i];
int yAdj = cur[1] + directionY[i];
if (isValid(xAdj, yAdj, grid)) {
queue.offer(new int[]{xAdj, yAdj});
grid[xAdj][yAdj] = '2';
}
}
}
}
private boolean isValid(int x, int y, char[][] grid) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1';
}
}
There are some people asking why their BFS implementations reach a time limit exceed error in LeetCode discuss forum. The short answer is they did it wrong.
OK. The problem is when you mark the visited cell. Just think about visiting a cell step by step:
- Initially the cell is not visited;
- It is put into the Queue by expanding a cell in the Queue;
- It is polled out from the Queue, now it has been visited;
So there are three types of cells in the BFS: not visited yet, in the visiting process, visited. These three states are also known as "not visited yet", "generated but not expanded" and "expanded".
When to mark visited? Immediately after the status changes to "generated but not expanded".
The code can get time exceed error:
while (!queue.isEmpty()) {
int[] cur = queue.poll();
// mark visited. wrong!
grid[x][y] = '2';
// BFS continues
}
It is wrong because one cell can be put into the Queue multiple times.
Method 2: based on DFS.
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int islands = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
islands++;
}
}
}
return islands;
}
private void dfs(char[][] grid, int x, int y) {
if (!isValid(x, y, grid)) {
return;
}
grid[x][y] = '2';
dfs(grid, x - 1, y);
dfs(grid, x + 1, y);
dfs(grid, x, y - 1);
dfs(grid, x, y + 1);
}
private boolean isValid(int x, int y, char[][] grid) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == '1';
}
}
Method 3: based on union-find set.
201. Bitwise AND of Numbers Range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
For example, given the range [5, 7], you should return 4.
Solution:
O(n) time is not accepted because the range is from 0 to 2147483647.
It requires some math. For continuous range, bitwise and can get the common left header. For example,
[26, 30] whose binary representations are:
11010 11011 11100 11101 11110
all have a common left head 11.
Method 1:
To get the common left head of m and n, move both one bit right until they are equal.
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int count = 0;
while (m != n) {
m = m >> 1;
n = n >> 1;
count++;
}
return m << count;
}
}
Another implementation: use a bit mask to cut off left head.
public class Solution {
public int rangeBitwiseAnd(int m, int n) {
int mask = Integer.MAX_VALUE;
while ((m & mask) != (n & mask)) {
mask = mask << 1;
}
return (m & mask);
}
}
207. Course Schedule
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
Hints:
- This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.
Solution:
As the hint says, it is topological sort problem.
Method 1:
Kahn's algorithm based on BFS.
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses < 0 || prerequisites == null) {
throw new IllegalArgumentException("not valid input");
}
if (numCourses == 0 || prerequisites.length == 0) {
return true;
}
int[] inDegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int numNoPre = queue.size();
while (!queue.isEmpty()) {
int top = queue.poll();
for (int i = 0; i < prerequisites.length; i++) {
if (prerequisites[i][1]==top) {
inDegree[prerequisites[i][0]]--;
if (inDegree[prerequisites[i][0]] == 0) {
queue.offer(prerequisites[i][0]);
numNoPre++;
}
}
}
}
return numNoPre == numCourses;
}
}
Method 2:
DFS. If A -> B, then the finished time of A is later than finished time of B. So the reverse order of the finished time can produce topological order output.
Use visited array to indicate status: 0 is unvisited, -1 is visited but its neighbors not visited yet, 1 is visited and its neighbors visited too.
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses < 0 || prerequisites == null) {
throw new IllegalArgumentException("not valid input");
}
if (numCourses == 0 || prerequisites.length == 0) {
return true;
}
int[] visited = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : prerequisites) {
if (map.containsKey(edge[1])) {
map.get(edge[1]).add(edge[0]);
} else {
List<Integer> l = new ArrayList<>();
l.add(edge[0]);
map.put(edge[1], l);
}
}
for (int i = 0; i < numCourses; i++) {
if (!dfs(map, visited, i)) {
return false;
}
}
return true;
}
private boolean dfs(Map<Integer, List<Integer>> map, int[] visited, int i) {
if (visited[i] == -1) {
return false; // cycle exists
}
if (visited[i] == 1) {
return true;
}
visited[i] = -1;
if (map.containsKey(i)) {
for (int j : map.get(i)) {
if (!dfs(map, visited, j)) {
return false;
}
}
}
visited[i] = 1;
return true;
}
}
208. Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Note: You may assume that all inputs are consist of lowercase letters a-z.
Solution:
Wikipage of Trie is here.
Method 1: use array to represent children.
public class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
int index = c - 'a';
if (cur.children[index] == null) {
cur.children[index] = new TrieNode();
cur = cur.children[index];
} else {
cur = cur.children[index];
}
}
cur.hasWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = searchNode(word);
return node != null && node.hasWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = searchNode(prefix);
return node != null;
}
private TrieNode searchNode(String s) {
if (s == null || s.length() == 0) {
return null;
}
TrieNode cur = root;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
int index = c - 'a';
if (cur.children[index] != null) {
cur = cur.children[index];
} else {
return null;
}
}
return cur;
}
}
class TrieNode {
TrieNode[] children;
boolean hasWord;
public TrieNode() {
this.children = new TrieNode[26];
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
Method 2: use HashMap to represent children.
public class Trie {
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
Map<Character, TrieNode> children = cur.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!children.containsKey(c)) {
children.put(c, new TrieNode());
}
cur = children.get(c);
children = cur.children;
}
cur.hasWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node = searchNode(word);
return node != null && node.hasWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node = searchNode(prefix);
return node != null;
}
private TrieNode searchNode(String s) {
if (s == null || s.length() == 0) {
return null;
}
TrieNode cur = root;
Map<Character, TrieNode> children = cur.children;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (children.containsKey(c)) {
cur = children.get(c);
children = cur.children;
} else {
return null;
}
}
return cur;
}
}
class TrieNode {
Map<Character, TrieNode> children;
boolean hasWord;
public TrieNode() {
this.children = new HashMap<>();
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(nlogn).
Solution:
It is a sliding window problem.
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0 || s < 0) {
return 0;
}
int left = 0;
int sum = 0;
int ans = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (left <= right && sum >= s) {
sum -= nums[left];
ans = Math.min(ans, right - left + 1);
left++;
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
Time complexity is O(n).
The O(n) time solution is good enough, why would we bother to get a O(nlogn) time solution?
The O(nlogn) solution is using binary search. See here.
210. Course Schedule II
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
Hints:
- This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
- Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
- Topological sort could also be done via BFS.
Solution:
It is similar to Problem 207. Course Schedule. The code only need a few changes.
Method 1: bfs.
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses < 0 || prerequisites == null) {
throw new IllegalArgumentException("not valid input");
}
int[] ans = new int[numCourses];
int index = 0;
int[] inDegree = new int[numCourses];
for (int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int numNoPre = queue.size();
while (!queue.isEmpty()) {
int top = queue.poll();
ans[index++] = top;
for (int i = 0; i < prerequisites.length; i++) {
if (prerequisites[i][1]==top) {
inDegree[prerequisites[i][0]]--;
if (inDegree[prerequisites[i][0]] == 0) {
queue.offer(prerequisites[i][0]);
numNoPre++;
}
}
}
}
if (numNoPre == numCourses) {
return ans;
} else {
return new int[0];
}
}
}
Method 2: dfs.
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
if (numCourses < 0 || prerequisites == null) {
throw new IllegalArgumentException("not valid input");
}
int[] visited = new int[numCourses];
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] edge : prerequisites) {
if (map.containsKey(edge[1])) {
map.get(edge[1]).add(edge[0]);
} else {
List<Integer> l = new ArrayList<>();
l.add(edge[0]);
map.put(edge[1], l);
}
}
int[] ans = new int[numCourses];
int[] index = new int[]{numCourses - 1};
for (int i = 0; i < numCourses; i++) {
if (!dfs(map, visited, i, ans, index)) {
return new int[0];
}
}
return ans;
}
private boolean dfs(Map<Integer, List<Integer>> map, int[] visited, int i, int[] ans, int[] index) {
if (visited[i] == -1) {
return false;
}
if (visited[i] == 1) {
return true;
}
visited[i] = -1;
if (map.containsKey(i)) {
for (int j : map.get(i)) {
if (!dfs(map, visited, j, ans, index)) {
return false;
}
}
}
ans[index[0]--] = i;
visited[i] = 1;
return true;
}
}
211. Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.
You should be familiar with how a Trie works. If not, please work on this problem: Implement Trie (Prefix Tree) first.
Solution:
It is a trie. Refer Problem 208. Implement Trie (Prefix Tree).
The only difference here is that we need to deal with ..
Not working.
public class WordDictionary {
/** Initialize your data structure here. */
private TrieNode root;
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode cur = root;
Map<Character, TrieNode> children = cur.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!children.containsKey(c)) {
children.put(c, new TrieNode());
}
cur = children.get(c);
children = cur.children;
}
cur.hasWord = true;
}
/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return searchNode(word, 0, root);
}
private boolean searchNode(String word, int index, TrieNode cur) {
if (index == word.length() - 1) {
if (cur.hasWord) {
return true;
} else {
return false;
}
}
Character c = word.charAt(index);
if (cur.children.containsKey(c)) {
return searchNode(word, index + 1, cur.children.get(c));
} else if (c == '.') {
boolean result = false;
for (Map.Entry<Character, TrieNode> entry : cur.children.entrySet()) {
if ((index == word.length() - 1) && entry.getValue().hasWord) {
return true;
} else {
if (searchNode(word, index + 1, entry.getValue())) {
result = true;
}
}
}
return result;
} else {
return false;
}
}
}
class TrieNode {
Map<Character, TrieNode> children;
boolean hasWord;
public TrieNode() {
this.children = new HashMap<>();
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
213. House Robber II
Note: This is an extension of House Robber.
After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
Solution:
215. Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: You may assume k is always valid, 1 ≤ k ≤ array's length.
Solution:
Th naive solution is to sort the array and output the kth largest element. A better solution is to use a min heap.
public class Solution {
public int findKthLargest(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
throw new IllegalArgumentException("input not valid");
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : nums) {
pq.offer(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
}
Time complexity is O(nlogk) and space complexity is O(k).
216. Combination Sum III
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Solution:
It is a typical DFS problem. We should compare all Combination Sum problems to get a better understanding.
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> results = new ArrayList<>();
if (k <= 0 || n <= 0) {
return results;
}
dfs(1, k, n, new ArrayList<Integer>(), results);
return results;
}
private void dfs(int start, int k, int sum, List<Integer> result, List<List<Integer>> results) {
if (sum < 0) {
return;
}
if (sum == 0 && result.size() == k) {
results.add(new ArrayList<Integer>(result));
}
for (int i = start; i <= 9; i++) {
result.add(i);
dfs(i + 1, k, sum - i, result, results);
result.remove(result.size() - 1);
}
}
}
220. Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
Solution:
This problem talks about the absolute difference rather than duplications.
To guarantee the absolute difference between i and j is <= k, we can use sliding window. Then the problem is that how to check if exists two nums whose absolute difference is <=t in the window? There are two ways.
- TreeSet, a balanced binary search tree, O(logn) to search a value;
- HashMap, storing buckets. It is similar to bucket sort.
Method 1:
Use TreeSet. In the TreeSet, we need to find out in the range [candidate - t, candiate + t] exists any element, where candidate is the number being scanned. We only need to check two numbers, one is the greatest element less than or equal to candidate, which can be obtained from the API set.floor(); the other is the least element greater than or equal to candidate, which can be obtained from the API set.ceiling(). If any of these two numbers are in the range of [candidate - t, candiate + t], return true.
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0 || t < 0 || k <= 0) {
return false;
}
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
int candidate = nums[i];
Integer floor = set.floor(candidate);
Integer ceiling = set.ceiling(candidate);
if((floor != null && candidate <= t + floor) || (ceiling != null && candidate + t >= ceiling)) {
return true;
}
set.add(candidate);
if (i >= k) {
set.remove(nums[i - k]);
}
}
return false;
}
}
Method 2:
For the window, build a series of buckets whose size is t or t + 1. For a number being scanned and its bucket ID is k, check three nearby buckets k - 1, k and k + 1.
A good solution with implementation details is here.
221. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
Solution:
This is a DP problem which needs a little bit math observations.
We are going to fill in a 2D array whose valuse m[i][j] represents the size of the largest 1s matrix with its right-bottom element is m[i][j].
The base case is the left-most column and top-most row. The induction rule is that:
m[i][j] = Math.min(left_top, Math.min(left, top)) + 1, if input[i][j] is 1;
m[i][j] = 0, if input[i][j] is 0;
Somebody explained by graph here.
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
int[][] result = new int[row][col];
int res = 0;
// base case
for (int i = 0; i < col; i++) {
result[0][i] = Character.getNumericValue(matrix[0][i]);
res = Math.max(res, result[0][i]);
}
for (int i = 1; i < row; i++) {
result[i][0] = Character.getNumericValue(matrix[i][0]);
res = Math.max(res, result[i][0]);
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][j] == '1') {
result[i][j] = Math.min(result[i - 1][j], Math.min(result[i][j - 1], result[i - 1][j - 1])) + 1;
} else {
result[i][j] = 0;
}
res = Math.max(res, result[i][j]);
}
}
return res * res;
}
}
The space complexity is O(m n). It can be further improved to O(n). The idea is to use a 2D matrix whose size is 2 n. Use i % 2 where i is the row index to rotate. Base case is included in the for loop.
public class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int row = matrix.length;
int col = matrix[0].length;
int[][] result = new int[2][col];
int res = 0;
for (int i = 0; i < row; i++) {
result[i % 2][0] = Character.getNumericValue(matrix[i][0]);
res = Math.max(result[i % 2][0], res);
for (int j = 1; j < col; j++) {
if (i > 0) {
if (matrix[i][j] == '1') {
result[i % 2][j] = Math.min(result[(i - 1) % 2][j], Math.min(result[i % 2][j - 1], result[(i - 1) % 2][j - 1])) + 1;
} else {
result[i % 2][j] = 0;
}
} else {
result[i % 2][j] = Character.getNumericValue(matrix[i][j]);
}
res = Math.max(res, result[i % 2][j]);
}
}
return res * res;
}
}
222. Count Complete Tree Nodes
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Solution:
Counting Tree Nodes in O(n) time is simple. Here we have a complete tree, what improvements can we make?
For a complete binary tree, there are two cases:
- Full binary tree: if its left-most height(always along left pointer down to leaf) is equal to its right-most height, then the total number of tree nodes is
2^h - 1. - Otherwise, the total number of nodes is equal to the number of nodes in the left subtree plus that of the right subtree and plus onez(root itself).
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = getLeftHeight(root);
int rightHeight = getRightHeight(root);
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
} else {
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
private int getLeftHeight(TreeNode root) {
int height = 0;
while (root != null) {
root = root.left;
height++;
}
return height;
}
private int getRightHeight(TreeNode root) {
int height = 0;
while (root != null) {
root = root.right;
height++;
}
return height;
}
}
Time complexity is O(h2) where h is the tree height.
There is a small improvement. You might have noticed that there is redundancy when calculating heights.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return countNodes(root, -1, -1);
}
private int countNodes(TreeNode root, int leftHeight, int rightHeight) {
if (leftHeight == -1) {
leftHeight = getLeftHeight(root);
}
if (rightHeight == -1) {
rightHeight = getRightHeight(root);
}
if (leftHeight == rightHeight) {
return (1 << leftHeight) - 1;
} else {
return countNodes(root.left, leftHeight -1, -1) + countNodes(root.right, -1, rightHeight - 1) + 1;
}
}
private int getLeftHeight(TreeNode root) {
int height = 0;
while (root != null) {
root = root.left;
height++;
}
return height;
}
private int getRightHeight(TreeNode root) {
int height = 0;
while (root != null) {
root = root.right;
height++;
}
return height;
}
}
223. Rectangle Area
Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Assume that the total area is never beyond the maximum possible value of int.
Solution:
It is a math problem.
The total area is area1 + area2 - overlap. To get overlap, we need find out the its lengths. Its x-dimensional length is Math.min(C, G) - Math.max(A, E) if overlap, otherwise 0.
public class Solution {
public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
int area1 = (D - B) * (C - A);
int area2 = (H - F) * (G - E);
if (Math.min(C, G) < Math.max(A, E) || Math.min(D, H) < Math.max(B, F)) {
return area1 + area2;
}
return area1 + area2 - (Math.min(C, G) - Math.max(A, E)) * (Math.min(D, H) - Math.max(B, F));
}
}
227. Basic Calculator II
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Solution:
There is * and / in the equation which requires higher priority than + and -. So we need two steps:
- First iteration: solve
*and/first. We can use a stack to store numbers, iterate the input, if met*or/,stack.push(stack.pop() * number). If-, put-numberinto the stack. - Second iteration: get the sum for the stack.
I use readNumber() to read a number from the string, it returns two values: the read number and the last index of the number in the string.
public class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
s = s.replaceAll(" ", "");
Deque<Integer> stack = new LinkedList<>();
int i = 0;
// read the first number
int[] re = readNumber(s, i);
stack.push(re[0]);
i = re[1];
while (i < s.length()) {
char c = s.charAt(i);
re = readNumber(s, i + 1);
if (c == '+') {
stack.push(re[0]);
} else if (c == '-') {
stack.push(-re[0]);
} else if (c == '*') {
stack.push(stack.pop() * re[0]);
} else if (c == '/') {
stack.push(stack.pop() / re[0]);
}
i = re[1];
}
int result = 0;
while (!stack.isEmpty()) {
result += stack.pop();
}
return result;
}
private boolean isNumber(char c) {
return c >= '0' && c <= '9';
}
private int[] readNumber(String s, int i) {
int num = 0;
while (i < s.length() && isNumber(s.charAt(i))) {
num = num * 10 + s.charAt(i) - '0';
i++;
}
return new int[] {num, i};
}
}
228. Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
Solution:
public class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
int start = 0;
int end = 0;
while (end < nums.length) {
if (end + 1 < nums.length && nums[end + 1] == nums[end] + 1) {
end++;
} else {
if (start == end) {
result.add(Integer.toString(nums[start]));
} else {
result.add(nums[start] + "->" + nums[end]);
}
end++;
start = end;
}
}
return result;
}
}
229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Solution:
It is a variant of Problem 169. Majority Element, where the majority element appears more than ⌊ n/2 ⌋ times. One difference is that Problem 169 assumes there exists one and exactly one major element, while here we don't have such assumption.
For this problem, we know that there are at most two majority elements. So we use vote algorithm to get two possible majority elements, then check whether they are valid.
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
// initial value can be random
int maj1 = 0;
int maj2 = 0;
int counter1 = 0;
int counter2 = 0;
for (int num : nums) {
if (num == maj1) {
counter1++;
} else if (num == maj2) {
counter2++;
} else if (counter1 == 0) {
maj1 = num;
counter1 = 1;
} else if (counter2 == 0) {
maj2 = num;
counter2 = 1;
} else {
counter1--;
counter2--;
}
}
counter1 = 0;
counter2 = 0;
for (int num : nums) {
if (num == maj1) {
counter1++;
} else if (num == maj2) {
counter2++;
}
}
if (counter1 > nums.length / 3) {
result.add(maj1);
}
if (counter2 > nums.length / 3) {
result.add(maj2);
}
return result;
}
}
Time complexity is O(n) and space complexity is O(1).
230. Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ? k ? BST's total elements.
Follow up: What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Solution:
For BST, its in-order traversal is in ascending order.
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root == null || k < 1) {
throw new IllegalArgumentException("not valid input");
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode next = root;
while (next != null || !stack.isEmpty()) {
while (next != null) {
stack.push(next);
next = next.left;
}
next = stack.pop();
k--;
if (k == 0) {
return next.val;
}
next = next.right;
}
return 0;
}
}
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Solution:
There are two cases for TreeNode p and TreeNode q:
pandqare in direct ancestor-descendant relation.pandqare not in direct ancestor-descendant relation.
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
} else if (root == p) {
return p;
} else if (root == q) {
return q;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
return left == null ? right : left;
}
}
238. Product of Array Except Self
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Solution:
It is an interesting problem. Actually it is simple.
The product of array except nums[i] is equal to the product of subarry before nums[i] times the product of subarray after nums[i].
Now we know how to solve it. Calculate the product before nums[i] and the product after nums[i], respectively.
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int[] preProduct = new int[nums.length];
preProduct[0] = 1;
int[] postProduct = new int[nums.length];
postProduct[nums.length - 1] = 1;
int[] product = new int[nums.length];
for (int i = 1; i < nums.length; i++) {
preProduct[i] = preProduct[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
postProduct[i] = postProduct[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
product[i] = preProduct[i] * postProduct[i];
}
return product;
}
}
Now the follow up asks for O(1) space. Can we avoid use the two additional arrays in the code above? The answer is yes. Just store the preProduct array and postProduct array in the product array.
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int[] product = new int[nums.length];
product[0] = product[nums.length - 1] = 1;
// first iteration, product stores preProduct
for (int i = 1; i < nums.length; i++) {
product[i] = product[i - 1] * nums[i - 1];
}
// second iteration, product = preProduct * postPreduct
int postProduct = 1;
for (int i = nums.length - 2; i >= 0; i--) {
product[i] *= postProduct * nums[i + 1];
postProduct *= nums[i + 1];
}
return product;
}
}
240. Search a 2D Matrix II
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false
Solution:
Use binary search. There are two good starting positions: bottom left and top right. For example, the bottom left number is 18, if smaller than 18, go up, if larger than 18, go right.
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int i = row - 1;
int j = 0;
while (i >= 0 && j < col) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] < target) {
j++;
} else {
i--;
}
}
return false;
}
}
What if there are duplicate numbers in the matrix and it asks to return the occurrence of target? For example, consider target is 3 and the matrix is:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
It should return 2. To handle the new requirement, we only need modify a few lines:
while (i >= 0 && j < col) {
if (matrix[i][j] == target) {
count++;
i--;
j++;
} else if (matrix[i][j] < target) {
j++;
} else {
i--;
}
}
241. Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".
((2-1)-1) = 0
(2-(1-1)) = 2
Output: [0, 2]
Example 2
Input: "2*3-4*5"
(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10
Output: [-34, -14, -10, -10, 10]
Solution:
This is a very good question.
My first thought is a DFS problem, but it is not. The DFS problem of parenthese is to count the valid permutations of 3 paris of parentheses, without showing any numbers.
DFS doesn't work here because we don't know how many parentheses will be added. Another reason is that we can not simply put parenthese at any possible position, for example, (1 +) 2 is not valid.
A problem who shares similar solution is Problem 95. Unique Binary Search Trees II. Before read solution below, try if any idea.
It solved by recursion. For each operator +, - or*, it can break the string into two parts: it is equivalent to adding parentheses! For its left substring and right substring, it can be solved recursively: the values are stored in the list, the two lists(one is from left substring, the other is from right substring) can be combined to get a list for the whole string. Please note that at each recursion level, we need new a list to store results of current level.
public class Solution {
public List<Integer> diffWaysToCompute(String input) {
List<Integer> result = new ArrayList<>();
if (input == null || input.length() == 0) {
return result;
}
result = helper(input, 0, input.length() - 1);
return result;
}
private List<Integer> helper(String input, int start, int end) {
List<Integer> res = new ArrayList<>();
for (int i = start; i <= end; i++) {
if (isOperator(input.charAt(i))) {
List<Integer> left = helper(input, start, i - 1);
List<Integer> right = helper(input, i + 1, end);
for (int num1 : left) {
for (int num2 : right) {
switch(input.charAt(i)) {
case '+' : res.add(num1 + num2);
break;
case '-' : res.add(num1 - num2);
break;
case '*' : res.add(num1 * num2);
break;
}
}
}
}
}
// base case, only number exists
if (res.isEmpty()) {
res.add(readNumber(input, start, end));
}
return res;
}
private boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*';
}
private int readNumber(String input, int start, int end) {
int num = 0;
while (start <= end) {
num = num * 10 + input.charAt(start) - '0';
start++;
}
return num;
}
}
Did you notice any redundancy in this recursion solution? For a substring, it might be computed multiple times. To avoid redundancy, we can use memoization: a HashMap to store calculated results, and for any substring to calculate, look it up in the HashMap first.
The key of the HashMap is (start, end) index pair, the value is a List<Integer> which stores all possible results of that substring.
260. Single Number III
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. Could you implement it using only constant space complexity?
Solution:
It is a variant of Problem 6. Single Number I. Please refer here.
public class Solution {
public int[] singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[0];
}
int xorResult = 0;
for (int num : nums) {
xorResult ^= num;
}
int bitFlag = xorResult & (~(xorResult - 1));
int[] ans = new int[2];
for (int num : nums) {
if ((num & bitFlag) == 0) {
ans[0] ^= num;
} else {
ans[1] ^= num;
}
}
return ans;
}
}
264. Ugly Number II
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note that 1 is typically treated as an ugly number, and n does not exceed 1690.
Solution:
Because ugly number's factors are 2, 3 and 5, so a new ugly number can be obtained from an existing ugly number by multiple 2, 3 or 5.
Ugly number : 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
Then 1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2, 9*2, 10*2, 12*2, ...
And 1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3, 9*3, 10*3, 12*3, ...
And 1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5, 9*5, 10*5, 12*5, ...
are all ugly numbers.
public class Solution {
public int nthUglyNumber(int n) {
if (n <= 0) {
throw new IllegalArgumentException("not valid input");
}
List<Integer> list = new ArrayList<>();
list.add(1);
int p2 = 0, p3 = 0, p5 = 0;
while (list.size() < n) {
int m2 = list.get(p2) * 2;
int m3 = list.get(p3) * 3;
int m5 = list.get(p5) * 5;
int min = Math.min(m2, Math.min(m3, m5));
list.add(min);
if (min == m2) {
p2++;
}
if (min == m3) {
p3++;
}
if (min == m5) {
p5++;
}
}
return list.get(n - 1);
}
}
274. H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
Solution:
The h is in the range of [0, n].
First sort the citations array. If at index 4, citations[4] is 6, there are length - 4 papers whose citations are >= 6, including index 4 paper.
Please refer here.
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
Arrays.sort(citations);
int length = citations.length;
for (int i = 0; i < length; i++) {
if (citations[i] >= length - i) {
return length - i;
}
}
return 0;
}
}
275. H-Index II
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
Solution:
Binary search.
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int length = citations.length;
int left = 0;
int right = citations.length - 1;
while (left < right - 1) {
int mid = left + (right - left) / 2;
if (citations[mid] >= length - mid) {
right = mid;
} else {
left = mid + 1;
}
}
if (citations[left] >= length - left) {
return length - left;
} else if (citations[right] >= length - right) {
return length - right;
} else {
return 0;
}
}
}
Another implementation from the internet here. But I don't know how to explain its correctness.
public class Solution {
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int length = citations.length;
int left = 0;
int right = citations.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (citations[mid] >= length - mid) {
right = mid;
} else {
left = mid + 1;
}
}
return length - left;
}
}
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
Solution:
Method 1:
Based on Number Theory. Timie complexity O(sqrt n).
Refer here.
Method 2:
DP. The induction rule is dp[x + y * y] = min(dp[x + y * y], dp[x] + 1).
public class Solution {
public int numSquares(int n) {
if (n < 0) {
return 0;
}
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i * i <= n; i++) {
dp[i * i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; i + j * j <= n; j++) {
dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
}
}
return dp[n];
}
}
Another similar implementation:
public class Solution {
public int numSquares(int n) {
if (n < 0) {
return 0;
}
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 1; i + j * j <= n; j++) {
dp[i + j * j] = Math.min(dp[i + j * j], dp[i] + 1);
}
}
return dp[n];
}
}
284. Peeking Iterator
Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation -- it essentially peek() at the element that will be returned by the next call to next().
Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].
Call next() gets you 1, the first element in the list.
Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.
Follow up: How would you extend your design to be generic and work with all types, not just integer?
Solution:
Please refer here.
// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> iterator;
private Integer cur;
public PeekingIterator(Iterator<Integer> iterator) {
// initialize any member here.
this.iterator = iterator;
this.cur = iterator.hasNext() ? iterator.next() : null;
}
// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
return cur;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
Integer res = cur;
this.cur = iterator.hasNext()? iterator.next() :null;
return res;
}
@Override
public boolean hasNext() {
return cur != null;
}
}
287. Find the Duplicate Number
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.
Solution:
Method 1:
Binary search. Please refer here.
public class Solution {
public int findDuplicate(int[] nums) {
if (nums == null || nums.length == 0) {
throw new IllegalArgumentException("input not valid");
}
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
int count = countMid(nums, mid);
if (count <= mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int countMid(int[] nums, int target) {
int count = 0;
for (int num : nums) {
if (num <= target) {
count++;
}
}
return count;
}
}
Time complexity is O(nlogn) and space complexity is O(1).
Method 2:
Consider it as a LinkedList.
here.
here.
289. Game of Life
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
- Any live cell with fewer than two live neighbors dies, as if caused by under-population.
- Any live cell with two or three live neighbors lives on to the next generation.
- Any live cell with more than three live neighbors dies, as if by over-population..
- Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
- Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
- In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?
Solution:
Method 1:
To do it in place, we can use the higher bit to store next state. Finally, shift one bit right to update the board.
public class Solution {
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int col = board[0].length;
int[] x = {-1, -1, 0, 1, 1, 1, 0, -1};
int[] y = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int count = 0;
for (int k = 0; k < 8; k++) {
int i2 = i + x[k];
int j2 = j + y[k];
if (i2 >= 0 && i2 < row && j2 >= 0 && j2 < col && (board[i2][j2] & 1) == 1) {
count++;
}
}
//go live
if(board[i][j] == 0 && count == 3){
board[i][j] |= 2;
}
// live continue
if (board[i][j] == 1 && (count == 2 || count == 3)) {
board[i][j] |= 2;
}
//>3 die
if(board[i][j] == 1 && (count < 2 || count > 3)){
board[i][j] &= 1;
}
}
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
board[i][j] = board[i][j] >> 1;
}
}
}
}
Method 2:
Please refer here.
public class Solution {
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return;
}
int row = board.length;
int col = board[0].length;
int[] x = {-1, -1, 0, 1, 1, 1, 0, -1};
int[] y = {0, 1, 1, 1, 0, -1, -1, -1};
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
int count = 0;
for (int k = 0; k < 8; k++) {
int i2 = i + x[k];
int j2 = j + y[k];
if (i2 >= 0 && i2 < row && j2 >= 0 && j2 < col && (board[i2][j2] == 1 || board[i2][j2] == 2)) {
count++;
}
}
if (board[i][j] == 1 && (count < 2 || count > 3)) {
board[i][j] = 2;
} else if (board[i][j] == 0 && count == 3) {
board[i][j] = 3;
}
}
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
board[i][j] = board[i][j] % 2;
}
}
}
}
299. Bulls and Cows
You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called "bulls") and how many digits match the secret number but locate in the wrong position (called "cows"). Your friend will use successive guesses and hints to eventually derive the secret number.
For example:
Secret number: "1807"
Friend's guess: "7810"
Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend's guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return "1A3B".
Please note that both secret number and friend's guess may contain duplicate digits, for example:
Secret number: "1123"
Friend's guess: "0111"
In this case, the 1st 1 in friend's guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return "1A1B".
You may assume that the secret number and your friend's guess only contain digits, and their lengths are always equal.
Solution:
The naive solution I proposed:
public class Solution {
public String getHint(String secret, String guess) {
if (secret == null || guess == null) {
return null;
}
int[] map = new int[10];
int bulls = 0;
int cows = 0;
for (int i = 0; i < secret.length(); i++) {
map[secret.charAt(i) - '0']++;
}
for (int i = 0; i < guess.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
map[guess.charAt(i) - '0']--;
}
}
for (int i = 0; i < guess.length(); i++) {
if (secret.charAt(i) != guess.charAt(i)) {
if (map[guess.charAt(i) - '0'] > 0) {
cows++;
map[guess.charAt(i) - '0']--;
}
}
}
return bulls + "A" + cows + "B";
}
}
There is a much better solution online. The author must be a genius.
public class Solution {
public String getHint(String secret, String guess) {
if (secret == null || guess == null) {
return null;
}
int[] map = new int[10];
int bulls = 0;
int cows = 0;
for (int i = 0; i < guess.length(); i++) {
int s = secret.charAt(i) - '0';
int g = guess.charAt(i) - '0';
if (s == g) {
bulls++;
} else {
if (map[s] < 0) {
cows++;
}
if (map[g] > 0) {
cows++;
}
map[s]++;
map[g]--;
}
}
return bulls + "A" + cows + "B";
}
}
The idea is that for numbers in secret, map[s]++, for numbers in guess, map[g]--: use positive frequency for secret, and negative frequency for guess, and it allows them to cancel each other.
For a number in secret, if map[s] < 0, means there is a same number appeared before in guess: it is a cow. It is noted that for a cow, the cow is detected when the latter number in the cow pair appears.
300. Longest Increasing Subsequence
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?
Solution:
Method 1:
It is a DP problem.
Fill array ans where ans[i] represents the size of longest ascending subsequence, including nums[i]. The induction rule is
ans[i] = Math.max(ans[i], ans[j] + 1), if nums[j] < nums[i] where j < i.
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] ans = new int[nums.length];
int longest = 0;
for (int i = 0; i < nums.length; i++) {
ans[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
ans[i] = Math.max(ans[i], ans[j] + 1);
}
}
longest = Math.max(longest, ans[i]);
}
return longest;
}
}
Time complexity is O(n2) and space complexity is O(n).
Method 2:
Binary search. Please refer here.
The idea is that storing the ascending subsequence in a list(not actually the longest ascending subsequence, but the length is the same, see reference above).
- If the
list.size() == 0, add num to the list; - If num > last element in list, add num to the list;
- Else, replace the smallest element among those bigger than num in the list by num;
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
List<Integer> list = new ArrayList<>();
for (int num : nums) {
if (list.size() == 0 || list.get(list.size() - 1) < num) {
list.add(num);
} else {
int index = binarySearch(list, num);
list.set(index, num);
}
}
return list.size();
}
// find the 1st element(> target) in the list
private int binarySearch(List<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (list.get(mid) < target) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
}
Time complexity is O(nlogn) and space complexity is O(n).
304. Range Sum Query 2D - Immutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:
Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
- You may assume that the matrix does not change.
- There are many calls to sumRegion function.
- You may assume that row1 ≤ row2 and col1 ≤ col2.
Solution:
It is essentially the same as 1D Range Sum Query problem.
public class NumMatrix {
private int[][] prefixSum;
public NumMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length ==0) {
return;
}
int row = matrix.length;
int col = matrix[0].length;
prefixSum = new int[row + 1][col + 1];
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
prefixSum[r + 1][c + 1] = prefixSum[r + 1][c] + prefixSum[r][c + 1] + matrix[r][c] - prefixSum[r][c];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
306. Additive Number
Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.
1 + 99 = 100, 99 + 100 = 199
Note:
Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?
Solution:
Not working.
public class Solution {
public boolean isAdditiveNumber(String num) {
if (num == null || num.length() == 0) {
return false;
}
int length = num.length();
for (int i = 1; i < length; i++) {
if(num.charAt(i) == '0' && i > 1) {
break;
}
for (int j = i + 1; j < length; j++ ) {
if(num.charAt(i) == '0' && j - i > 1) {
break;
}
int num1 = getNum(num, 0, i);
int num2 = getNum(num, i, j);
if(isAdditiveNumber(num1, num2, num, j)) {
return true;
}
}
}
return false;
}
private boolean isAdditiveNumber(int num1, int num2, String num, int index) {
if(index == num.length()) {
return true;
}
int sum = num1 + num2;
int sumLength = sum / 10 + 1;
if (index + sumLength > num.length() || sum != getNum(num, index, index + sumLength)) {
return false;
}
return isAdditiveNumber(num2, sum, num, index + sumLength);
}
private int getNum(String num, int start, int end) {
int ans = 0;
for (int i = start; i < end; i++) {
ans = ans * 10 + num.charAt(i) - '0';
}
return ans;
}
}
307. Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
- The array is only modifiable by the update function.
- You may assume the number of calls to update and sumRange function is distributed evenly.
Solution:
Please refer here.
309. Best Time to Buy and Sell Stock with Cooldown
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:
- You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
- After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:
prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]
Solution:
I have no idea how to solve this problem.
Please refer here.
public class Solution {
public int maxProfit(int[] prices) {
int sell = 0, prev_sell = 0, buy = Integer.MIN_VALUE, prev_buy;
for (int price : prices) {
prev_buy = buy;
buy = Math.max(prev_sell - price, prev_buy);
prev_sell = sell;
sell = Math.max(prev_buy + price, prev_sell);
}
return sell;
}
}
310. Minimum Height Trees
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).
You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.
Example 1:
Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]
0
|
1
/ \
2 3
return [1]
Example 2:
Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]
0 1 2
\ | /
3
|
4
|
5
return [3, 4]
Note:
(1) According to the definition of tree on Wikipedia): “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Solution:
313. Super Ugly Number
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
- 1 is a super ugly number for any given primes.
- The given numbers in primes are in ascending order.
- 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
- The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
Solution:
In Problem 264. Ugly Number II, we have three factors: 2, 3 and 5. In this problem, we have a list of factors.
In Problem 264, we use three variables to store the ugly numbers from which to get other ugly numbers. Here we need an array.
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if (n <= 0 || primes == null || primes.length == 0) {
throw new IllegalArgumentException("not valid input");
}
int[] nums = new int[n];
nums[0] = 1;
int[] index = new int[primes.length];
for (int i = 1; i < n; i++) {
nums[i] = Integer.MAX_VALUE;
for (int j = 0; j < primes.length; j++) {
nums[i] = Math.min(nums[i], nums[index[j]] * primes[j]);
}
for (int j = 0; j < primes.length; j++) {
if (nums[i] == nums[index[j]] * primes[j]) {
index[j]++;
}
}
}
return nums[n - 1];
}
}
318. Maximum Product of Word Lengths
Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
Example 1:
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".
Example 2:
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".
Example 3:
Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.
Solution:
The key point is how to determine two words share common letters or not. A efficient way is to use bit manipulation. There are 26 lower case letters so an int datatype is enough to represent the letters occurred in a word. For checking two words have common letters or not, just use AND.
public class Solution {
public int maxProduct(String[] words) {
int length = words.length;
int[] map = new int[length];
for (int i = 0; i < length; i++){
for(int j = 0; j < words[i].length(); j++){
map[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
int ans = 0;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if ((map[i] & map[j]) == 0) {
ans = Math.max(ans,words[i].length() * words[j].length());
}
}
}
return ans;
}
}
A better solution:
Still use bit manipulation to check common letters. The difference here is that first sort strings based on their length. Please pay attention to the nest for loops to calculate product of two strings.
public class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0) {
return 0;
}
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
if (s1.length() == s2.length()) {
return 0;
}
return s1.length() < s2.length() ? 1 : -1;
}
});
int[] bitMasks = getBitMasks(words);
int ans = 0;
for (int i = 1; i < words.length; i++) {
for (int j = 0; j < i; j++) {
int prod = words[i].length() * words[j].length();
if (prod <= ans) {
break;
}
if ((bitMasks[i] & bitMasks[j]) == 0) {
ans = Math.max(ans, prod);
}
}
}
return ans;
}
private int[] getBitMasks(String[] words) {
int[] map = new int[words.length];
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words[i].length(); j++) {
map[i] |= 1 << (words[i].charAt(j) - 'a');
}
}
return map;
}
}
Because the strings are sorted in descending order based on their length, so the nested for loops above can stop ahead, rather than iterating all possible pairs. It has two modifications:
- The outer loop
istarts from 1, and the inner loopjis bounded byi; - If found a smaller product, break the loop.
Last thing, in Java 8, comparator can be replaced by lambda expression:
Arrays.sort(words, (String s1, String s2) -> {
if (s1.length() == s2.length()) {
return 0;
}
return s1.length() < s2.length() ? 1 : -1;
});
319. Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.
Solution:
It is a math problem. See here.
public class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
322. Coin Change
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note: You may assume that you have an infinite number of each kind of coin.
Solution:
This is another very good question. Somebody asked me this problem and my answer is to use greedy(DFS, try larger denomination first, return first result). I was wrong. An example is [1, 3, 5, 6] and amout is 8, by greedy, it will return 3 (6 + 1 + 1), but the solution should be 2 (5 + 3). Why greedy does not work? My 2cent is that because the input is not continuous. I was told that greedy is easy to propose but difficult to prove and this is a good example.
Actually this is a back-pack problem. There is a famous review for back-pack problem: 背包九讲.
The DP array result[i] represent the fewest number of coins for amount i. Initially result[0] = 0. To fill in result[i], it needs look back all meaningful elements between result[0] and result[i-1]: result[i - coin1], result[i - coin2], ...etc.
If i >= coin and result[i - coin] is not filled yet:
result[i] = result[i - coin] + 1
If i >= coin and result[i - coin] is filled before:
result[i] = Math.min(result[i], result[i - coin] + 1) for all coins
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
}
int[] result = new int[amount + 1];
result[0] = 0;
for (int i = 1; i <= amount; i++) {
result[i] = -1;
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j] && result[i - coins[j]] != -1) {
if (result[i] == -1) {
result[i] = result[i - coins[j]] + 1;
} else {
result[i] = Math.min(result[i], result[i - coins[j]] + 1);
}
}
}
}
return result[amount];
}
}
A similar implementation:
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
}
int[] result = new int[amount + 1];
result[0] = 0;
for (int i = 1; i <= amount; i++) {
result[i] = Integer.MAX_VALUE;
for (int j = 0; j < coins.length; j++) {
if (i >= coins[j] && result[i - coins[j]] != Integer.MAX_VALUE) {
result[i] = Math.min(result[i], result[i - coins[j]] + 1);
}
}
}
return result[amount] == Integer.MAX_VALUE ? -1 : result[amount];
}
}
Method 2:
Use BFS: the least number of coins is the shortes path length, and each coin is one possible step.
It havs some modification comparing to traditional BFS: it use a Set to speed up otherwise it will throw TLE in LeetCode.
(You can forget about this method, nobody will ask you about it.)
public class Solution {
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount < 0) {
return -1;
} else if (amount == 0) {
return 0;
}
Queue<Integer> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
for (int coin : coins) {
if (coin == amount) {
return 1;
} else if (coin < amount) {
queue.offer(coin);
set.add(coin);
}
}
// fewest number of coins
int level = 1;
while (!queue.isEmpty()) {
int size = queue.size();
level++;
for (int i = 0; i < size; i++) {
int cur = queue.poll();
for (int coin : coins) {
if (cur + coin == amount) {
return level;
} else if (!set.contains(cur + coin) && cur + coin < amount) {
queue.offer(cur + coin);
set.add(cur + coin);
}
}
}
}
return -1;
}
}
406. Queue Reconstruction by Height
Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note: The number of people is less than 1,100.
Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
Solution:
I have no idea how to solve it. So I ask google.
I try my best to explain the idea, because a good programmer understands the solution, not remember it.
First, sort the array because it is hard to use a unsorted array and we have no structure information about the unsorted array. How to sort?
- Firstly, sort in descending order by h. Because k contains information of higher or equal thank k, in front of this person.
- Secondly, for equal h, sort in ascending order by k. Because for same h, pairs with smaller k must be before those pairs with larger k.
It might be difficult to propose this sorting strategy, but after we understand the reason why sort like this, it is understandable.
After sorting, the array is [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]].
Then let's try manually to get some idea.
[7,0]is good.[7,1]is good.[6,1]is not in the right position. Take[7,1]out and put[6,1]at index 1. Now the current output is[[7,0], [6,1]], and we store[7,1]somewhere(we don't know what data structure should be used yet).[5,0]is not in the right position either. So empty the current output and put[5,0]at the head.[[7,0]and[6,1]]are stored somewhere too. We need guarantee when putting back[7,1],[[7,0]and[6,1]],[7,0]is put back firt, then[6,1]then[7,1]. It is LIFO, so we use a stack to store them.- For
[5,2], put back[7,0]so the output is[[5,0], [7,0]], then append[5,2]to make the output is[[5,0], [7,0]], [5,2]. The stack is|| [7,1], [6, 1] > top. - For
[4,4], it requires 4 pairs in the output, so we put back 1 pairs from the stack, so the output now is[[5,0], [7,0]], [5,2], [6,1]then append[4,4], the output is[[5,0], [7,0]], [5,2], [6,1], [4,4]and stack is|| [7,1] > top. - Finally put back
[7,1]from the stack and the output is[[5,0], [7,0]], [5,2], [6,1], [4,4], [7,1]. Done.
OK, the steps above looks complicated. How to understand them?
- Use a new empty list to store the output. Use a stack to store temporary pairs.
- The elements in the output list + in the stack are scanned.
- The pairs not explored yet have smaller h than those scanned, because all pairs are descending-ordered by h during pre-processing. In other words, all pairs scanned(in the outputlist and in the stack) have larger or equal h than the pair which is being scanned.
- Based on the 3rd property, if the pair which is being scanned is
[h,k], it requires k pairs in the output list, then we can append the current pair[h,k]. We might need move some pairs from the stack to the output list or from the output list to the stack, to make exactly k pairs in the output list. - So the stack is helping the output list by storing temporary pairs, to make exactly k paris in the output list. Alternatively, without stack, we can use the List API
list.add(index, element), or even do it in place. - Finally if there are pairs in the stack, append them to the output list.
- In the 4th property, if we can not make k pairs in the output list, it means there is no correct output: the total number of scanned pairs(output list + stack) is less than k. In this problem, it assumes the output list exists.
In the code below, to save space, I use an output array which has the same size with the input and a variable size to act as a list.
public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (p1, p2) -> {if (p1[0] != p2[0]) {
return p2[0] - p1[0];
} else {
return p1[1] - p2[1];
}
});
int[][] result = new int[people.length][2];
// size is the next available index in the result array
int size = 0;
Deque<int[]> stack = new LinkedList<>();
for (int i = 0; i < people.length; i++) {
int[] cur = people[i];
while (size < cur[1]) {
result[size++] = stack.pollFirst();
}
while (size > cur[1]) {
stack.addFirst(result[--size]);
}
result[size++] = cur;
}
while (!stack.isEmpty()) {
result[size++] = stack.pollFirst();
}
return result;
}
}
As it is pointed out above, use List API add(index, element) rather than the stack:
public class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (p1, p2) -> {if (p1[0] != p2[0]) {
return p2[0] - p1[0];
} else {
return p1[1] - p2[1];
}
});
List<int[]> result = new LinkedList<>();
for (int i = 0; i < people.length; i++) {
int[] cur = people[i];
result.add(cur[1], cur);
}
return result.toArray(new int[people.length][2]);
}
}
It is also can be done in O(1) space.
The time complexities for both with stack and without stack are the same O(n2).
413. Arithmetic Slices
A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, these are arithmetic sequence:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
The following sequence is not arithmetic.
1, 1, 2, 5, 7
A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.
A slice (P, Q) of array A is called arithmetic if the sequence: A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.
The function should return the number of arithmetic slices in the array A.
Example:
A = [1, 2, 3, 4]
return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
Solution:
Method 1:
By DP. dp[i] respresents the number of arithmetic slices ends with A[i].
Induction rule:
dp[i] = dp[i - 1] + 1, if A[i - 2], A[i - 1], A[i] is arithmetic slice;
dp[i] = 0, otherwise;
The induction rules says that, if A[i - 2], A[i - 1], A[i] can make a arithmetic slice, then arithemetic slices ends at A[i] = {arithemetic slices ends at A[i - 1] + A[i]} + new arithmetic slice {A[i - 2], A[i - 1], A[i]}.
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length < 3) {
return 0;
}
int result = 0;
int dpPre = 0;
int dp = 0;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
dp = dpPre + 1;
} else {
dp = 0;
}
result += dp;
dpPre = dp;
}
return result;
}
}
Method 2:
For an array whose length is n, there are (n - 1) * (n - 2) / 2 subarrays whose length >= 3. (n - 2 subarrays whose length is 3, n - 3 subarrays whose length is 4, ..., 1 subarray whose length is n.)
So we need to find all arithmetic subarrays(as long as possible, if {1,2,3,4,5} can be found, we don't count the shorter {1,2,3,4} or {1,2,3}) and apply the equation to calculate the number of arithmetic slices contained in that subarry, finally sum all subarrays.
public class Solution {
public int numberOfArithmeticSlices(int[] A) {
if (A == null || A.length < 3)
return 0;
int sum = 0;
int len = 2;
for (int i = 2; i < A.length; i++) {
if (A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
len++;
} else {
if (len > 2) {
sum += calculateSlices(len);
}
// reset the length of new slice
len = 2;
}
}
// add up the slice in the rear
if (len > 2)
sum += calculateSlices(len);
return sum;
}
private int calculateSlices(int n) {
return (n - 1) * (n - 2) / 2;
}
}
416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100. The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
Solution:
Method 1:
It is a back-pack problem and can be solved by DP, when the sum of the elements is not too big.
public class Solution {
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
sum /= 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int i = 0; i < nums.length; i++) {
for (int j = sum; j >=nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[sum];
}
}
Method 2:
There is another solution online.
Use a BigInteger where bits[i](count from right to left) is 1 if amount i can be obtained from the input.
The proof by induction is below:
- Assume in the subarray of the original input array, all obtainable amounts are
a ~ b,c ~ d.... - If number
kis added to the subarray, then all obtainable amounts area~b,c~d... +(a+k) ~ (b+k),(c+k) ~ (d+k).... The new added obtainable amounts(a+k) ~ (b+k),(c+k) ~ (d+k)... is equivalent tobits << k. - So all obtainable amounts is
bits |= bits << k.
import java.math.BigInteger;
public class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 == 1) {
return false;
}
BigInteger bits = new BigInteger("1");
for (int num : nums){
bits = bits.or(state.shiftLeft(num));
}
return bits.testBit(sum / 2);
}
}
Method 3:
By recursion. It is slower(O(2n)) than method 1 and 2. But it works if the sum is big.
Refer here.
417. Pacific Atlantic Water Flow
Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
The order of returned grid coordinates does not matter. Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
Solution:
It is similar to Problem 130. Surrounded Region.
The idea is that: conduct DFS/BFS from Pacific and Atlantic, respectively, to get grids where water can flow to Pacific and Atlantic, respectively. The final answer is the common grids.
Method 1: by DFS.
public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int row = matrix.length;
int col = matrix[0].length;
boolean[][] pacific = new boolean[row][col];
boolean[][] atlantic = new boolean[row][col];
for (int i = 0; i < row; i++) {
dfs(matrix, Integer.MIN_VALUE, i, 0, pacific);
dfs(matrix, Integer.MIN_VALUE, i, col - 1, atlantic);
}
for (int i = 0; i < col; i++) {
dfs(matrix, Integer.MIN_VALUE, 0, i, pacific);
dfs(matrix, Integer.MIN_VALUE, row - 1, i, atlantic);
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(new int[] {i, j});
}
}
}
return result;
}
private void dfs(int[][] matrix, int pre, int i, int j, boolean[][] visited) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j] || matrix[i][j] < pre) {
return;
}
visited[i][j] = true;
dfs(matrix, matrix[i][j], i + 1, j, visited);
dfs(matrix, matrix[i][j], i - 1, j, visited);
dfs(matrix, matrix[i][j], i, j - 1, visited);
dfs(matrix, matrix[i][j], i, j + 1, visited);
}
}
Method 2 : by BFS.
public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return result;
}
int row = matrix.length;
int col = matrix[0].length;
Queue<int[]> pqueue = new LinkedList<>();
Queue<int[]> aqueue = new LinkedList<>();
boolean[][] pacific = new boolean[row][col];
boolean[][] atlantic = new boolean[row][col];
for (int i = 0; i < col; i++) {
pqueue.offer(new int[]{0, i});
pacific[0][i] = true;
aqueue.offer(new int[]{row - 1, i});
atlantic[row -1][i] = true;
}
for (int i = 0; i < row; i++) {
pqueue.offer(new int[]{i, 0});
pacific[i][0] = true;
aqueue.offer(new int[]{i, col - 1});
atlantic[i][col - 1] = true;
}
bfs(matrix, pqueue, pacific);
bfs(matrix, aqueue, atlantic);
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (pacific[i][j] && atlantic[i][j]) {
result.add(new int[] {i, j});
}
}
}
return result;
}
private void bfs(int[][] matrix, Queue<int[]> queue, boolean[][] visited) {
int[] directionX = {1, -1, 0, 0};
int[] directionY = {0, 0, 1, -1};
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int i = 0; i < 4; i++) {
int x = cur[0] + directionX[i];
int y = cur[1] + directionY[i];
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]) {
continue;
}
queue.offer(new int[] {x, y});
visited[x][y] = true;
}
}
}
}
419. Battleships in a Board
Given an 2D board, count how many battleships are in it. The battleships are represented with 'X's, empty slots are represented with '.'s. You may assume the following rules:
- You receive a valid board, made of only battleships or empty slots.
- Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
- At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.
Example:
X..X
...X
...X
In the above board there are 2 battleships.
Invalid Example:
...X
XXXX
...X
This is an invalid board that you will not receive - as battleships will always have a cell separating between them.
Follow up:
Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?
Solution:
It is similar to Problem 200. Number of Islands, we can either solve it by BFS or DFS. But it will require extra space.
This problem has its own speciality: the battleship has to be vertical or horizontal, and they are separated. So we can count the head of the battleship, the head is definied as the left-end cell or top cell. For example,
Xxx.
...X
...x
...x
There are two battleships in the board above and their heads are represent by capital X.
public class Solution {
public int countBattleships(char[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) {
return 0;
}
int row = board.length;
int col = board[0].length;
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'X' && (i ==0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
res++;
}
}
}
return res;
}
}
421. Maximum XOR of Two Numbers in an Array
Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.
Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.
Could you do this in O(n) runtime?
Example:
Input: [3, 10, 5, 25, 2, 8]
Output: 28
Explanation: The maximum result is 5 ^ 25 = 28.
Solution:
The brute force solution is straightforward(O(n2)).
It says the number has at most 32 bits. XOR means "same 0 different 1".
Method 1: better than brute force solution. To get maximum XOR, the top bits need to be different.
public class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int mask = 1 << 31;
List<Integer> nums0 = new ArrayList<>();
List<Integer> nums1 = new ArrayList<>();
while (mask != 0) {
for (int num : nums) {
if ((num & mask) == 0) {
nums0.add(num);
} else {
nums1.add(num);
}
}
if (!nums0.isEmpty() && !nums1.isEmpty()) {
break;
}
mask = mask >> 1;
}
return helper(nums0, nums1, mask);
}
private int helper(List<Integer> nums0, List<Integer> nums1, int mask) {
if (mask <= 1) {
return mask;
}
mask = mask >> 1;
List<Integer> nums00 = new ArrayList<>();
List<Integer> nums01 = new ArrayList<>();
List<Integer> nums10 = new ArrayList<>();
List<Integer> nums11 = new ArrayList<>();
for (int num0 : nums0) {
if ((num0 & mask) == 0) {
nums00.add(num0);
} else {
nums01.add(num0);
}
}
for (int num1 : nums1) {
if ((num1 & mask) == 0) {
nums10.add(num1);
} else {
nums11.add(num1);
}
}
int ans = 0;
if (!nums10.isEmpty() && !nums01.isEmpty()) {
ans = Math.max(ans, helper(nums10, nums01, mask));
}
if (!nums00.isEmpty() && !nums11.isEmpty()) {
ans = Math.max(ans, helper(nums00, nums11, mask));
}
if (ans == 0) {
ans = helper(nums0, nums1, mask) - mask;
}
return ans + mask * 2;
}
}
Method 2: a even better solution.
public class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int mask = 0;
int result = 0;
for (int bit = 31; bit >= 0; bit--) {
mask = mask | (1 << bit);
Set<Integer> prefixSet = new HashSet<>();
for (int num : nums) {
prefixSet.add(num & mask);
}
int guess = result | (1 << bit);
for (int pre : prefixSet) {
if (prefixSet.contains(pre ^ guess)) {
result = guess;
break;
}
}
}
return result;
}
}
Method 3: trie.
Explanation is here. And Java solution is here.
public class Solution {
public int findMaximumXOR(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int result = 0;
Node root = new Node();
for (int num : nums) {
insertTrie(root, num);
}
for (int num : nums) {
int xorNum = findMatchXor(root, num);
result = Math.max(result, xorNum ^ num);
}
return result;
}
private int findMatchXor(Node root, int num) {
int result = 0;
for (int i = 31; i >= 0; i--) {
int bit = num & (1 << i);
int flag = bit == 0 ? 0 : 1;
if (root.next[1 - flag] == null) {
result += flag << i;
// or result += bit;
root = root.next[flag];
} else {
result += (1 - flag) << i;
root = root.next[1 - flag];
}
}
return result;
}
private void insertTrie(Node root, int x) {
for (int i = 31; i >= 0; i--) {
int bit = x & (1 << i);
int flag = bit == 0 ? 0 : 1;
if (root.next[flag] == null) {
root.next[flag] = new Node();
}
root = root.next[flag];
}
}
private static class Node {
Node[] next;
public Node() {
next = new Node[2];
}
}
}
494. Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
- The length of the given array is positive and will not exceed 20.
- The sum of elements in the given array will not exceed 1000.
- Your output answer is guaranteed to be fitted in a 32-bit integer.
Solution:
Method 1, DFS:
public class Solution {
public int findTargetSumWays(int[] nums, int S) {
if (nums == null || nums.length == 0) {
return 0;
}
return helper(nums, 0, 0, S);
}
private int helper(int[] nums, int sum, int level, int S) {
if (level == nums.length) {
return sum == S ? 1 : 0;
}
return helper(nums, sum + nums[level], level + 1, S) + helper(nums, sum - nums[level], level + 1, S);
}
}
Time complexity is O(2n) where n is the length of input array. Space complexity is O(n) because there are n levels in the recursion tree.
Method 2: