LeetCode Solution Set

---

A personal LeetCode/LintCode Java solution set.

Binary Search

#	Title	Difficulty	Comment
LeetCode 33	Search in Rotated Sorted Array	Medium
LeetCode 81	Search in Rotated Sorted Array II	Medium
LeetCode 240	Search a 2D Matrix II	Medium	See the L-shaped array as a sorted array; iterate from the left bottom conner, each loop drop a half
LeetCode 302	Smallest Rectangle Enclosing Black Pixels	Hard	Do binary search in all directions
LeetCode 162	Find Peak Element	Medium
LeetCode 153	Find Minimum in Rotated Sorted Array	Medium
LeetCode 154	Find Minimum in Rotated Sorted Array II	Hard
LeetCode 34	Find First and Last Position of Element in Sorted Array	Medium	Use two BinarySearch to find first and last indices.
LeetCode 162	Find Peak Element	Medium	Use binary search to drop a half elements in each iteration. Note that the premise that this question can use binary search is based on two conditions: one is nums[-1] = nums[n] = -∞, another is that we only need to return one peak index.
LeetCode 658	Find K Closest Elements	Medium	Good question. Using binary search to find the start index of the k window. A obvious characteristic of the final state is that the difference of left element and x should always be less than or equal to that of the right element. So we can use x - arr[mid] > arr[mid + k] - x as the binary search condition and we initialize like int start = 0, end = n - k;, since the start index of the k window must be in this range.

Binary Tree

#	Title	Difficulty	Comment
LeetCode 104	Minimum Depth of Binary Tree	Easy
LeetCode 257	Binary Tree Paths	Easy
LeetCode 110	Balanced Binary Tree	Easy	Use custom class ResultType to return more than one value
LeetCode 236	Lowest Common Ancestor of a Binary Tree	Medium	Two cases: one side each or both in a side; preorder traversal
LeetCode 543	Diameter of Binary Tree	Easy	Helper function used to calculate the tree depth; in the process of calculating tree depth, update max diameter
LeetCode 617	Merge Two Binary Trees	Easy	Manipulate two trees at the same time using preorder traversal in a single method
LeetCode 958	Check Completeness of a Binary Tree	Medium	BFS or Divide & Conquer; BFS: while meeting a null element, break while loop, and check whether there's any non-null nodes remaining in the queue. (after break, we need to iterate the remained elements in the queue)
LeetCode 572	Subtree of Another Tree	Easy	Two method: One is used to recursively apply on its two subtree; the other is used to recursively check whether two binary tree are the same.
LeetCode 103	Binary Tree Zigzag Level Order Traversal	Medium	Make some modification on level traversal. Use a boolean variable as a switch to control whether in this level we traverse from the left to the right or from the right to the left. Instead of polling the first element in the queue, we poll the last. Be careful about the order with the switch variable.
LeetCode 545	Boundary of Binary Tree	Medium	Write 3 traversal functions to traverse 3 parts of the binary tree: left side, bottom leaves, right side. A corner case is [1]. In this case, we need to judge whether this tree is only of level 1, otherwise it will add the root twice into the result set.
LeetCode 105	Construct Binary Tree from Preorder and Inorder Traversal	Medium	Use the first element in the preorder array to determine the root. Then find the root value in the inorder array and separate the original array into two partitions. We can implement it by using a helper function. See details in the code. Notice to handle the null node case.
LeetCode 235	Lowest Common Ancestor of a Binary Search Tree	Easy	If the current node's value is between p and q, return it as the lowest common ancester. Notice that p.val might be larger than q.val, we need to do a check first.
LeetCode 314	Binary Tree Vertical Order Traversal	Medium	Cannot use pre/in/postorder traversal to traverse all the nodes, Since the vertical order traversal must be from root to leaves. So we can use BFS to solve this problem.
LeetCode 116	Populating Next Right Pointers in Each Node	Medium	The requirement is to limit the space complexity to O(1), so we cannot use BFS since we need a O(n) space queue. Alternately, we can use two pointers: one points to the head of each level, another points to currently operating node. For each cur node, we connect its cur.left.next to cur.right and then move cur to the next node in the same level by cur = cur.next.
LeetCode 117	Populating Next Right Pointers in Each Node II	Medium	Extended from 116. The binary tree now is not a perfect tree. We can use 3 pointers to solve this case: levelHead represents the head of the next level, cur represents the current node of the current level, lead represents the current leading node for assigning .next attribute.
LeetCode 979	Distribute Coins in Binary Tree	Medium	Use a helper function to do divide conquer recursion call. The helper function will return how many coins it can provided to the higher level. And use a global variable to record the steps for moving coins. The coins a tree can provide is equal to root.val + leftRes + rightRes - 1. The steps for moving coins can be calculated by res += (abs(leftRes) + abs(rightRes)).

Divide & Conquer

#	Title	Difficulty	Comment
LeetCode 106	Construct Binary Tree from Inorder and Postorder Traversal	Medium	The last node of preorder array is the current root. Then find its position in inorder array and split each array into two subtree part (both required a start and end boundary). Do it using divide&conquer recursively.
LeetCode 124	Binary Tree Maximum Path Sum	Hard	Declare a global variable to restore the max sum; For any maximum path, its must be composed by two parts: the path from two end nodes to their lowest common ancestor; So the return value of our help Divide & Conquer function is the max sum from the end node to its lca; There's a trick here: for any part of two subtree, if its max path is nagetive, make it 0, as negative value will make no contribution to the answer and making it 0 can exclude its influence on the result.
LeetCode 1325	Delete Leaves With a Given Value	Medium	First, apply the function on both of the two subtrees. Then, handle the current root node based on the results we get in the first step.
LeetCode 1443	Minimum Time to Collect All Apples in a Tree	Medium	Divide & conquer. Another approach is to reverse the original tree, then start from the child nodes and count their total distance to node 0, then times 2 and get the answer.

BFS

#	Title	Difficulty	Comment
LeetCode 297	Serialize and Deserialize Binary Tree	Hard	serialize: BFS, then trim null elements in the tail; deserialize: iterate array and add current node to its position; use a queue to record current node which is being added; use a flag to mark left or right, each time meeting a left node means that it requires to get next node to be added
LeetCode 133	Clone Graph	Medium	3 steps: collect all old nodes in a list; create new nodes and keep it in a pair with old nodes in a map; copy edges
LeetCode 199	Binary Tree Right Side View	Medium	Level traversal on a binary tree. In each level, use a variable to store the size of the current level.
LeetCode 994	Rotting Oranges	Easy	Level traversal on a chess board. First you should add all neighbors of rotten oranges into the BFS queue. Then use a counter to record the total number of fresh oranges.
LeetCode 542	01 Matrix	Medium	Use a one-time BFS which starts at all 0 points. For each level, increase the distance by one. Use a matrix to record the shortest distance to 0 for every points. If the current distance is less than ans[i][j], update ans[i][j] and add it into the BFS queue. Do not use a boolean[][] isVisited array and set the non-zero point to Integer.MAX_VALUE in the beginning. See more details in the code.
LeetCode 909	Snakes and Ladders	Medium	We can't use DP to solve this problem since there're snakes and ladders which will destroy the optimal subproblem structure. Use BFS to do level traversal until reaching the end point. Write a helper function to get the coordinate by the square number i. If a snake takes to a previously visited square, skip it so that we will not get into a cycle.
LeetCode 286	Walls and Gates	Medium	Similar to LeetCode 542.
LeetCode 505	The Maze II	Medium	Similar to LeetCode 490. This problem requires to calculate the distance to the stop points. Thus we can use BFS to do it.
LeetCode 1306	Jump Game III	Medium	Use BFS or DFS to traverse. If find an index whose corresponding element is equal to 0, return true.

Connected Components & Union-Find

#	Title	Difficulty	Comment
LeetCode 323	Number of Connected Components in an Undirected Graph	Medium	BFS or DFS; use a boolean[] to record the isVisited state of each node
LeetCode 200	Number of Islands	Medium	Count connected blocks. Use direction array and bfs to traverse all nodes in the chessboard. Required a private custom class Point for queue and a boolean array for marking whether a point has been visited.
LeetCode 1202	Smallest String With Swaps	Medium	Use Disjoint Set Algorithm (CLRS Chapter # 21) to get connected components. Then sort each group and generate the new string.
LeetCode 1061	Lexicographically Smallest Equivalent String	Medium	Use UnionFind to divide letters into serveral groups. Then get the smallest letter for each group. Note that we can also do some slight modification on the original UnionFind, since we only need to get the smallest letter in each group. So we don't need rank array, and we just simply attach the letter with higher lexicographical order to the lower one. (See the second solution in the code.)
LeetCode 990	Satisfiability of Equality Equations	Medium	Two pass. First pass union, second pass check.
LeetCode 959	Regions Cut By Slashes	Medium	First we should divide a square into 4 parts by its two diagonal (see the comment in the code). Then we can do a mapping to map the 4*n*n elements into an array by 4n*i + 4*j + t . Then we can do UnionFind. When we iterate the grids, we only union the inner partitions and the previous partitions (that means only union the upper partition and left partition with their neighbors). For counting distinct groups, we can use a counter variable count inside the UnionFind class and decrease it by one when the results of find() in union() are not equal. Note that we can also use DFS to solve this question. That is divide each of the original grid into a 3*3 square. Then the question is like Number of Islands. See C++ with picture, DFS on upscaled grid.

Topological Sorting

#	Title	Difficulty	Comment
LeetCode 207	Course Schedule	Medium	Build graph and then topological sort
LeetCode 210	Course Schedule II	Medium	Refer to 207. This question requires to return a possible solution.
LeetCode 269	Alien Dictionary	Hard	Extend to 210 Course Schedule II. The question changes the way it gives the graph. We need to determine the from -> to pair by comparing words[i] and words[i+1]; For the first time we find a character in these two strings has a different letter in the same index, it's just the from -> to pair. Then build graph and do topological sorting.

DFS

#	Title	Difficulty	Comment
LeetCode 39	Combination Sum	Medium
LeetCode 40	Combination Sum II	Medium	Don't allow more than one same elements to be added into combination in a single for loop while writing the DFS helper function.
LeetCode 216	Combination Sum III	Medium	Brute force approach is okay. Time complexity is O(C(9, k)) => O(9^k). Iterating from bigger end can quit the for loop early and avoid unnecessary work.
LeetCode 494	Target Sum	Medium	Also see DP #3
LeetCode 301	Remove Invalid Parentheses	Hard	First, count the amount of parentheses required for deletion; Then, dfs; use int idx, int dropOpenCnt, int dropCloseCnt as parameters; use this condition if (dropOpenCnt == 0 && dropCloseCnt == 0 && isValid(s)) to add element; Note for recursive call idx should be i
LeetCode 698	Partition to K Equal Sum Subsets	Medium	1⃣️. calculate the sum of the array, and calculate the sum for each subset. If sum % k != 0, it's false; 2⃣️. use dfs to search all possible subset partitions; just like backtracking subset question, we need a boolean[] isVisited and idx (permutation doesn't need idx, because it cares about the order); ifk == 1, it just can return true, as we promise the sum % k = 0
LeetCode 1079	Letter Tile Possibilities	Medium	Similar to subsets II & permutation. But there's a more tricky solution. Count the occurrence of all the letters. Then each step select one letter. Count the total selection of the specific length.
LeetCode 863	All Nodes Distance K in Binary Tree	Medium	Use a adjacent to store a binary tree as a graph and for each tree node, the parent also represents an edge. So first we need to use DFS to construct the graph. Then use BFS to collect the node whose distance to the target node is K.
LeetCode 980	Unique Paths III	Hard	First find the start point and count all empty squares. Then use DFS+Backtracking to iterate all possible paths. If all emptys have been visited and the path reaches the end point, increase counter by 1.
LeetCode 841	Keys and Rooms	Medium	It's a graph problem. Start from 0, check whether we can connect to all vertices using DFS.
LeetCode 733	Flood Fill	Easy	Flood fill the same color pixels. We can use a helper function to do the DFS easily. Note that if the newColor is the same color as the target pixel, do nothing and return the original matrix.
LeetCode 490	The Maze	Medium	DFS in a fixed direction. Use a helper dfs function to do it. Then use a 2D boolean[][] array to record the stop points. When the DFS meets a visited stop point, just skip it.
LeetCode 694	Number of Distinct Islands	Medium	We can use DFS to traverse each connected component. In order to distinguish each different island shape, we can generate a string of traversal order and use a hashset to remove the duplicate. **Notice that ** for the case [[1,1,0],[0,1,1],[0,0,0],[1,1,1],[0,1,0]] if we don't add a delimiter for each node, it will have some duplicates.
LeetCode 1087	Brace Expansion	Medium	Backtracking. Better to parse curly braces first, then start to do DFS. Also better to do sorting before DFS.
LeetCode 417	Pacific Atlantic Water Flow	Medium	We can consider in a reverse way: this question requires to find out the grids which can both reach Pacific and Atlantic. So we can start from Pacific and Atlantic, then see which grids can be reached from Pacific and Atlantic respectively. Finally, collect the grids which can be reached both by Pacific and Atlantic.
LeetCode 547	Friend Circles	Medium	Find SCC in undirected graph. Use DFS to resolve it. (See the code) Note that we need to use Tarjan's algorithm to find SCC in directed graph. We can also use UNION-FIND to solve this question.
LeetCode 842	Split Array into Fibonacci Sequence	Medium	Do backtracking. Record the previous two numbers. Some cases are required to be handled: one is starting with0, 0 is valid, but 0112, 0000 are invalid; another is for integers that are of length 10 but still less than Integer.MAX_VALUE. The code is ugly, recommend to rewrite in the future.

Linked List

#	Title	Difficulty	Comment
LeetCode 160	Intersection of Two Linked Lists	Easy	Let the tail of List A point to the head of List B; if there's a circle, it means have intersection; otherwise, it has no intersection
LeetCode 143	Reorder List	Medium	1. find the mid 2. reverse the right part 3. merge two lists
LeetCode 287	Find the Duplicate Number	Medium	It's a problem on array, but it can be converted to a linked list problem similar to Linked List Cycle II. Use slow = nums[slow]; fast = nums[nums[fast]]; to move to the next node in the "linked list". It takes O(n) time. Another idea is to use Binary Search to check the number of elements which are less than and equal to mid (not nums[mid]) in the whole array is less than and equal to mid. If it's true, do recursively in the right part, otherwise do it in the left part.
LeetCode 430	Flatten a Multilevel Doubly Linked List	Medium	Good question. The key is to treat this linked list as a binary tree. child represents the left subtree, next represents the right subtree. And this question becomes a preorder traversal. The helper() function returns the tail of the flattened linked list.

Array

#	Title	Difficulty	Comment
LintCode 139	Subarray Sum Closest	Medium	subarray_sum(i, j) = prefix[j+1] - prefix[i]; find the least difference of two elements in the prefix array
LeetCode 42	Trapping Rain Water	Hard	For each element of the array, the water it contains is equal to $min(LeftMaxBar, RightMaxBar) - height(i))$; to speed up the process of finding leftMax & rightMax, we can store the result in the initialization stage by iterating the array from two ends twice.
LeetCode 238	Product of Array Except Self	Medium	Use a prefixProduct array and a suffixProduct array (rather than product[i][j], product[i][j] would take $O(n^2)$ time); Followup: To limit space complexity to $O(1)$; Just modify the rightProduct to a single variable (the space of answer array is not included as extra space)
LeetCode 840	Magic Squares In Grid	Easy	1. the center must be 5 2. the order must be 43816729 or 92761834 3. the even must be in the corner, the odd must be on the edge (only check one point is enough)
LeetCode 531	Lonely Pixel I	Medium	Use two arrays to record how many B occur in this row or col. If it's the first time it occurs, plus 1; if not, decrease by 1. After that, check all grids in the matrix whether there's a B in the rowCnt and colCnt equals 1 places (i.e. rowCnt[i] == 1 && colCnt[j] == 1 && picture[i][j] == 'B' )
LeetCode 1352	Product of the Last K Numbers	Medium	Prefix Product. If meeting a 0, clear the prefix product array and start from the beginning 1. When returning, we should compare the length of the prefix product array, if length < k, we should return 0, since we have a 0 in the k elements and the product must be 0. Another way is to use a List to compress consequent 1 and 0. Because the product is restricted within the integer range. That means the multiply over 2 can at most occur 32 times, otherwise it will over flow. So the other factors must be 0 and 1. So we can compress and every time just product the rightmost k.
LeetCode 846	Hand of Straights	Medium	Ordered Map question. Use an ordered map to collect the count of each card in the hand. Then iterate the non-zero elements in the map; check the later W-1 element, check whether they are greater or equal to the current; if not, that means its impossible. Then update the count by minus the current count. It takes O(M * log(M) + W*M). M is the number of the unique cards in the hand. See another O(M * log(M)) in the code.
LeetCode 243	Shortest Word Distance	Easy	Record the last occurrence of these two words respectively. Calculate the minimum distance every time when we meet a word1 or word2.
LeetCode 1144	Decrease Elements To Make Array Zigzag	Medium	Make all the elements in the odd indices less than its two neighbors or make all the elements in the even indices less than its two neighbors. Return the minimum decrement step number. And we can do it in one pass.

String

#	Title	Difficulty	Comment
LeetCode 157	Read N Characters Given Read4	Easy
LeetCode 165	Compare Version Numbers	Medium	Add 0 in the tail for the shorter version string: digit1 = (i < len1) ? Integer.parseInt(digits1[i]) : 0. Notice that do not try to trim tailing zero for the longer version string.
LeetCode 811	Subdomain Visit Count	Easy	How to get the suffix strings (e.g. "discuss.leetcode.com", "leetcode.com", "com") from a url "discuss.leetcode.com"
LeetCode 1023	Camelcase Matching	Medium	Just think about this three kinds of test casesqueries = [aFoB, aFaocBad, Fo], pattern = "FoB". Write a check function to handle this three kinds of cases using Two Pointers.
LeetCode 1002	Find Common Characters	Easy	Do bag intersaction for every letter in the given string set. We can use a integer array cnt[] to record the occurance for every letter in each string. Then we choose the minimum cnt of every letter for all strings as the final returned answer.

Heap

#	Title	Difficulty	Comment
LeetCode 347	Top K Frequent Elements	Medium	1. Count occurrences of all elements; 2. Use a min heap with k capacity to filter top k frequent elements; Note that the constructor parameter of PriorityQueue is only the initial capacity
LeetCode 767	Reorganize String	Medium	Select the most frequent letter then alternately place the selected letters. Notice that if there're some duplicates in a priority queue, it's not ensured that priority queue is FIFO. We need to manually poll one more element to check.
LeetCode 1086	High Five	Easy	Calculate the average score of each student's top five scores. Use Map + MinHeap(PriorityQueue) to implement. Note that the given students' IDs may not be continuous (e.g. 1, 2, 4, 8, ...). If the result is required to be sorted by students' IDs, use a TreeMap to maintain the order.
LeetCode 692	Top K Frequent Words	Medium	Similar to LC 347. Note that when writing the priority queue comparator, we should return b.getKey().compareTo(a.getKey()) instead of a.getKey().compareTo(b.getKey()) in the case of a.getValue() - b.getValue() == 0. Think about the following 3 strings in the min heap: "abc", "abd", "abz". We should poll them in the order: "abz", "abd", "abc". The lexicographically larger string should be at the bottom of the heap. Notice that ArrayList.set() will throw NullPointerException if there's no element in that index.

Stack

#	Title	Difficulty	Comment
LeetCode 1249	Minimum Remove to Make Valid Parentheses	Medium	Use a stack to keep the indices of the characters required to be removed. Then, remove them togeter.
LeetCode 155	Min Stack	Easy	Implement a stack which can return the min value of the current state. The key is to store the min value of each state. We can use a variable to cache the min for each stack node (define a custom class with fields: val, min, next). Then we can use next to connect this linked list to store stack.
LeetCode 150	Evaluate Reverse Polish Notation	Medium	Judge whether the current element is '+', '-', '*', '/' first. If not, it's an integer.
LeetCode 456	132 Pattern	Medium	Every time we read one letter, we need to maintain a structure which stores all min-max Interval pairs before. We will use a stack here to help merge min-max Interval pairs. See more details in the code. It's better to combine the code with examples. It's not a easy question.
LeetCode 388	Longest Absolute File Path	Medium	\n, \t, \r is a single character, not two characters. They are one of the ASCII characters!!! We can use a variable level and a stack to record the current prefix path length. Don't forget there's a slash between two subdirectories.
LeetCode 636	Exclusive Time of Functions	Medium	Use a stack to record the current non-finished functions and a variable prev to record the last switching timestamp. Note that the start and end timestamp are all inside an interval. That means for two consequent start or end, the length of this interval is time2 - time1, but for a consequent start, end pair, it's time2 - time1 + 1.
LeetCode 439	Ternary Expression Parser	Medium	Simlar to Reverse Polish Notation. But we can solve this question by iterating from the tail and every time we meet a ?, we pop two values from our stack and do calculation. Another way is to divide the original string into two blocks and get the answer recursively.
LeetCode 856	Score of Parentheses	Medium	Good Question: Only when we meet a ')', we need to calculate the score of this pair of parenthese. And if the current inner score is 0, that means there's no inner parentheses inside, we just increase by 1; if the current inner score is larger than 0, we know there're some terms inside, we need to double the score. And when we meet a '(', we should push a 0 into the stack. It just represents the score of its inner part.

Two Pointers

#	Title	Difficulty	Comment
LeetCode 83	Remove Duplicates from Sorted List	Easy	A pointer points to the tail of non-duplicate elements; the other pointer points to the current iteration index; Remeber to cut the tail in the end
LintCode 607	Two Sum - Data structure design	Medium	Use a hashmap to store the <val, cnt> pair and a list to store the distinct internal values; for find(int value) - take care of the case k + k = value. In this case, you need to check the count of k
LeetCode 15	3Sum	Medium	a+b = -c, then use twoSum(); Or fix one element, then use two pointers to iterate the other two elements
LintCode 31	Partition Array	Medium	Similar to the Partition process of Quicksort: Use two pointers; when left and right both point to an element which don't belong to its partition, swap.
LeetCode 215	Kth Largest Element in an Array	Medium	Use the Partition process of Quicksort to determine the i-th element, then drop a half, search for the Kth element in the left half recursively.
LeetCode 560	Subarray Sum Equals K	Medium	Use prefixSum array to present the sum of subarray: s[j] - s[i] = k; then the question is converted to 2sum; Note that nums[i] might be negative
LeetCode 76	Minimum Window Substring	Hard	Sliding window: 1. Use two pointers: start and end to represent a window; 2. Move end to find a valid window; 3. When a valid window is found, move start to find a smaller window.
LeetCode 680	Valid Palindrome II	Easy	To skip the useless character, we can't easily skip it by judge s[p+1] == s[q] or s[p] == s[q-1]. Instead, we need to check the inner substring using the original validPalindrome function.
LeetCode 986	Interval List Intersections	Medium	If the heads of the two sorted list are intersected, output the current intersection ( [maxStart, minEnd]). Then pop the interval with a less end (Because if the following interval will intersect with these two heads, it must intersect with the larger end)
LeetCode 1099	Two Sum Less Than K	Easy	Two pointers after sorting. Note that we can use the following way to get the closest maximum value to a target: maxSum = Math.max(maxSum, sum). There's no need to calculate the difference.
LeetCode 75	Sort Colors	Medium	Use two pointers to point to the next index for inserting 0 and 2 respectively. Then use another pointer to iterate the whole array. Note that after swapping with 2, we need move back i by 1, since for the index q it has not been scanned yet so it might be 0 or 2 and it's required to be checked while for the index p it must be 1, so it doest need any extra check.
LeetCode 826	Most Profit Assigning Work	Medium	Sort difficulty & profit pairs and worker. Then use one pointer to iterate the difficulty & profit pairs, another pointer to iterate worker. While iterating, use two variables sum and maxProfit to record the current profit sum and the current max profit.
LeetCode 633	Sum of Square Numbers	Easy	Calculate square value of every number less than sqrt(c). Then use two pointers approach to check whether there's a pair sum up to c.

Sliding Window

#	Title	Difficulty	Comment
LeetCode 76	Minimum Window Substring	Hard	Sliding window: 1. Use two pointers: start and end to represent a window; 2. Move end to find a valid window; 3. When a valid window is found, move start to find a smaller window.
LeetCode 239	Sliding Window Maximum	Hard	1⃣️ Use a Deque to store the index of elements in sliding window; the elements in Deque is descend, so the maximum occurs in the head, minimum occurs in the end; in each round of loop, we only keep the "promising" elements in the Deque. 2⃣️ Use a prefix max array with a boundary on index % k == 0
LeetCode 438	Find All Anagrams in a String	Medium	First expand the window to cover a possible answer, then shrink the window. Use a variable incomplete to record how many kinds of letters there're still not covered by the current window. When incomplete == 0, shrink and check whether the current window length is equal to q.length(). If it's equal, add the current start into the result set. Then destroy the state of incomplete == 0 by expanding end of the window.
LeetCode 713	Subarray Product Less Than K	Medium	the number of subarrays that ends at index end is just the window size. Therefore, the total number is just the sum of every valid window's size.
LeetCode 424	Longest Repeating Character Replacement	Medium	extend the window until the sum of all non-maximum cnt is greater than k, record the window length; shrink the window until it is valid again; Use a helper function to check it. Note that we can also check it by using end - start to represent the totalCnt, using maxCnt to record the maxCnt. Notice that here maxCnt is not an accurate max count, since we only care the longest window and when we shrink, the current window must not be able to be the longest window. So we only care the historical maxCnt, not the accurate current maxCnt.
LeetCode 845	Longest Mountain in Array	Medium	Extend the window until we get a valid mountain, then record the maximum length. One exception input case is all full of the same number, like [2, 2, 2, 2, 2, 2]. For this case, we must ensure that we have been ascending then descending. Another approach is to iterate the orignial array from the head to the tail and from the tail to the head by two-pass. Record two prefix length arrays in this way.

Bit Manipulation

#	Title	Difficulty	Comment
LeetCode 338	Counting Bits	Medium	Divide the number into 2 parts: 1⃣️ the last digit = i % 2; 2⃣️ the other digits = dp[i/2]; i/2 = i >> 1, i%2 = (i & 1)

Sort

#	Title	Difficulty	Comment
LeetCode 973	K Closest Points to Origin	Medium	Use the main idea of PARTITION in Quicksort to sort the first k-th smallest elements; it takes O(n) time.
LeetCode 252	Meeting Rooms	Easy	Sort by the left/right end of the interval, then compare the right/left end of the intervals. Followup: LeetCode 253
LeetCode 253	Meeting Rooms II	Medium	Add all left & right end points into an array, then sort by value (Note that we need to make right points before left points while they have same value); After that, iterating the points array; When we meet a left point, it means we are entering a new interval; otherwise, we are leaving an interval. (Just like using a vertical line to sweep from left to right)
LeetCode 56	Merge Intervals	Medium	Sort the segments by the left end. Then iterate all segments in the sorted array: if the current segment's left end is less than the last merged segment in the result set, then merge these two.
LeetCode 274	H-Index	Medium	We can use the idea of bucket to resolve this question instead of sorting the original array. Since h is in the range [0, n], we can count papers by citation. For papers with citation larger than n, we collect them in the bucket[n]. So we will have n+1 buckets in total. Then iterate the bucket from the tail and h from n decreased to 0 until the accumulative count sum is larger than h.
LeetCode 1366	Rank Teams by Votes	Medium	We have at most votes[0].length() rounds and it is less than 26. So we can use a 26 * 26 array to record the votes each letter gets in each round. Then we can use this array to sort the original character set.

Greedy

#	Title	Difficulty	Comment
LeetCode 406	Queue Reconstruction by Height	Medium	Descending sort array by height; for people having same height, ascending sort by index; Then, insert the elements of the sorted array; in each iteration, the current element must be the smallest element due to descending sorting, so just call the method add(p[i], p) of LinkedList
LeetCode 621	Task Scheduler	Medium	https://leetcode.com/problems/task-scheduler/discuss/104500/Java-O(n)-time-O(1)-space-1-pass-no-sorting-solution-with-detailed-explanation; https://github.com/tzheng/interviewprep/blob/master/SourceCode/TaskCoolDown.java
LeetCode 1167	Minimum Cost to Connect Sticks	Medium	Use a min heap to store the elements. Each time poll two minimal elements from the heap until there's only 1 element left in the heap. Return the total cost.
LeetCode 1024	Video Stitching	Medium	Similar to LeetCode 1326. But it's not that good to use DP to solve this problem. It takes O(nT) while greedy takes O(nlog(n)). See details in the code.
LeetCide 55	Jump Game	Medium	Use two pointers: cur represents the current index, end represents the current farthest index we can reach. If finally end can reach the tail of the array, return true.
LeetCide 45	Jump Game II	Medium	Greedy but actually is the transformation of BFS. Use a variable end to record the current end of this level of BFS; use another variable reach to record the current farthest index we can reach. Every time we scan to the index cur == end that means we finish one level of BFS, so we can increase ans by one and set the current end to the current farthest reachable index.
LeetCode 1353	Maximum Number of Events That Can Be Attended	Medium	Since there's no priority order among these events (i.e. any event can be selected in a specific day), we can solve this question by always selecting the most recently due event. We can first sort the original array by start date, so that when we iterate by days we can select the events that start from the current date easily. Then use a PriorityQueue to extract the event which dues first. Then every time, we push the events started from the current date into the PriorityQueue, extract one event ended first, and pop all events that due today. Note that the while loop can not end until both all events iterated and the PriorityQueue is empty.
LeetCode 1055	Shortest Way to Form String	Medium	Use greedy to expand each partition to the most. We can use two pointers, one to iterate source, another for target. We can use a dictionary of size 26 to record the occurrence of each letter (its index). When iterating target, we can use this dictionary to find the next in source by binary search since the indices will always occur in ascending order. It takes O(log(M/26) * N). Further, we can flat the value of the dictionary entry from a ->{1,3,7,11} to a ->{1,1,3,3,7,7,7,7,11,11,11, 11,0,0, 0} if the target is of length 15. If we need to get the next pos of a in source for the current index 8, we can just access dict[a][8]. It takes O(M+N).
LeetCode 991	Broken Calculator	Medium	DP doesn't work since the lower state will rely on the higher state. So we consider greedy. The decrement actions in the high value level must have less influence compared to doing decrement in the lower value level, since the double actions will amplify the decrement actions in the lower value level. See more explanation in the code.

Hash Table

#	Title	Difficulty	Comment
LeetCode 953	Verifying an Alien Dictionary	Easy	We can compare the first difference of two adjacency words in the List. For example, "applying" and "apples" have a first difference of y vs e. Then check wheter the character in first word is before that in the second word. Pay attention to this special case: apple <-> app.
LeetCode 387	First Unique Character in a String	Easy	One pass solution: Use a LinkedHashMap to store the unique <element, index> pairs and a HashSet to check whether this element has occurred before.
LeetCode 49	Group Anagrams	Medium	Count letters and then generate a key string using the count in the first step.
LeetCode 437	Path Sum III	Easy	PrefixSum on Binary Tree. Use DFS and a HashMap to record the prefix sums. Notice that HashSet may neglect some cases.
LeetCode 1152	Analyze User Website Visit Pattern	Medium	Use a hashmap to group elements by username. Then sort the elements in each group by timestamp. After sorting, iterate all possible 3-seqs in the brute-force approach and count the occurrence of each 3-seq. Finally, return the most frequently visited one. Notice that we need to use a hashset to remove duplicates inner the same user. (See more details in the code comment.)
LeetCode 409	Longest Palindrome	Easy	sum up all even counts and the (odd-1) counts. If there's any odd counts, increase the final result by 1. See how to use hashset to resolve this question in the code.

Dynamic Programming

#	Title	Difficulty	Comment
LeetCode 312	Burst Balloons	Hard	1. Denote dp[i][j] as the maximum gain for bursting the balloons from i to j; 2. Get recursive equation; 3. Iterate from length 0
LintCode 92	Backpack	Medium	Classical knapsack problem; denote dp[i][j] as the max weight for the first i items with backpack of j size; So for the i th item, it will have two cases: in or out; dp[i][j] = max(dp[i-1][j], dp[i-1][j-A[i]] + A[i]); space complexity can be O(V)
LeetCode 494	Target Sum	Medium	DFS or DP; just see as a knapsack problem; test cases should include [0,0,0,0,1], 1; map index [-sum, sum] to [0, 2*sum]; when initializing, ++ the dp[0][-num[i]] instead of assigning 1
LeetCode 279	Perfect Squares	Medium	problem of n can be divided into the subproblem of n-square[i] + 1; Time complexity is O(n*sqrt(n))
LeetCode 120	Triangle	Medium	Take care that how to represent the index relationship between the last level index and the current level index: dp[i][j] consists of dp[i-1][j-1] & dp[i-1][j]. To meet the O(n) space complexity requirement, we can maintain the dp[] in a bottom-to-top approach. In the end, return dp[0].
LeetCode 1223	Dice Roll Simulation	Medium	A little bit difficult. Notice that rollMax represents the max consecutive times. See comments.
LeetCode 1102	Path With Maximum Minimum Value	Medium	Dijkstra's algorithm. Use a max heap to store the fringes. Use a boolean array to restore whether a point is visited. Once a point is in tree, it will not be modified again. Then just return.
LeetCode 264	Ugly Number	Medium	Use 3 variables to store the current product for facter 2, 3, 5 respectively.
LeetCode 62	Unique Paths	Medium	dp[i][j] = dp[i-1][j] + dp[i][j-1]
LeetCode 63	Unique Paths II	Medium	The trasition equation is still dp[i][j] = dp[i-1][j] + dp[i][j-1]. The only difference is how to treat the obstacles.
LeetCode 516	Longest Palindromic Subsequence	Medium	Transition equation: dp[i][j] = dp[i+1][j-1] + 2 or max(dp[i+1][j], dp[i][j-1]). Start from len = 1 to len = n. We can also reduce the space from O(n^2) to O(n) by recording the last state's leftmost dp element. (The dp array is updated like a triangle)
LeetCode 1326	Minimum Number of Taps to Open to Water a Garden	Hard	1. DP: dp[i] = min(min(dp[start...i-1]) + 1 => dp[i]) = min(dp[start] + 1, dp[i]), since dp[] must be ascending, so dp[start] must be the smallest one among dp[start...i-1]. 2. Greedy: Sort the segments and then extend the possible maximal range step by step.(See the code.)
LeetCode 276	Paint Fence	Easy	Similar to 1223 Dice Roll Simulation . The transition equation is same[i] = diff[i-1] and diff[i] = k * sum(same[i-1], diff[i-1]) - same[i-1] - same[i] = (k-1) * sum.
LeetCode 416	Partition Equal Subset Sum	Medium	It's a knapsack problem. dp[i][j] => whether we can use the first i elements to sum up to j. The transition equation is dp[i][j] = dp[i-1][j-num[i]]. The initialization state is dp[i][j] = true, j = 0. And we can reduce the space complexity to O(sum). But notice that when iterating the states, we should start from the tail to the head, since if we update the lower elements first, it will impact the updatement of the higher elements.
LeetCode 718	Maximum Length of Repeated Subarray	Medium	State definition: dp[i][j] => the maximum length of the repeated subarray that ends at i for A, at j for B. State Transition: dp[i][j] = (A[i] == B[j]) ? dp[i-1][j-1] + 1 : 0. State initialization: ``dp[i][j] = 0, i = 0
LeetCode 712	Minimum ASCII Delete Sum for Two Strings	Medium	This question is equivalent to maximum ASCII sum common String. State definition: dp[i][j] => the maximum ASCII sum of common subsequence for s1.substring(0, i) and s2.substring(0, j). State transition: dp[i][j] = (s1[i] == s2[j]) ? dp[i-1][j-1] + ASCII(s1[i]) : max(dp[i-1][j], dp[i][j-1]). State initialization: ``dp[i][j] = 0, i = 0
LeetCode 651	4 Keys Keyboard	Medium	To maximize the total count of A, in the last series of actions we must do like this *A, *C, V, V, V,... . So we can get dp[i] = max(i, max(dp[k] * (i - k - 1))); k in [0, i-3] . And we initialize dp[0] = 0 . It takes O(n) time.
LeetCode 1140	Stone Game II	Medium	A question of game theory. The more scores Alex gets, the less scores Lee gets, since the total scores is fixed. Our task is to get the maximum scores Alex can get. So it's equivalent to get the maxium difference between Alex and Lee. See more details in the code.
LeetCode 650	2 Keys Keyboard	Medium	Similar to LC 651. State definition: dp[i] => the minimum steps to reach i. State transition: dp[i] => min(dp[j] + i/j), j is the factor of i. Initializing: dp[1] = 0. It can also be solved by greedy. Because copy the more As will always save more steps. So we can always choose the max factor to generate our result.
LeetCode 873	Length of Longest Fibonacci Subsequence	Medium	Good Question. This question's state definition is a kind of different. In order to infer the next item of the current Fibonacci Seq, we need to record the last two elements. Thus, the state definition of this question is: dp[i][j] => maximum length of the sequence ends with i and j. The state transition equation is dp[i][j] = dp[k][i] + 1 k, i in [0, j-1] and num[k] + num[i] = num[j]. The state initialization is dp[i][j] = 2, for every i < j.
Microsoft 2019 China Q2	Minimum Shooting	Hard	Similar to 317 Burst Balloons. State definition: state definition: dp[i][j] => the minimal cost of bursting all bottles from i to j. State transition: dp[i][j] = min(dp[i+1][j-1](if nums[i] == nums[j]), dp[i][k]+dp[k+1][j]). State initialization: dp[i][j] = 1, i = j. While updating states, we should start from the ones with shorter length.
Microsoft 2019 China Q1	Pass Ball	Medium	We solve this question by modifying the original DFS solution to the memoization search version. We always return the answer instead of void dfs() in memoization search.
LeetCode 294	Flip Game II	Medium	Game Theory. Use memorization to speed up. First write a function to generate possible candidates of next state. Then recursively call the helper function to get whether starting from the given pattern can win. The key condition is that if one candidate can not win, the current pattern can win.

Trie

#	Title	Difficulty	Comment
LeetCode 208	Implement Trie (Prefix Tree)	Medium	TrieNode(links[R], R = 26, isEnd).
LeetCode 642	Design Search Autocomplete System	Hard	Record the words and its times in each node. Then use a max heap to return top 3.
LeetCode 1268	Search Suggestions System	Medium	class Trie {private Trie[] links = new Trie[26]; List<String> suggestion = new ArrayList<>();}. Notice that we're required to return 3 candidates at most. This problem also can be solved using binary search.
LeetCode 421	Maximum XOR of Two Numbers in an Array	Medium	In order to get a maximum XOR, we need to get a most different prefix from the left. So we can use trie to get it. There're some tricks: 1. Use Integer.toBinaryString() to convert integers to a bit represented string. 2. use `Integer.toBinaryString(nums[i]
LeetCode 720	Longest Word in Dictionary	Easy	Trie + DFS
LeetCode 648	Replace Words	Medium	Contruct trie and then use the trie to filter words.
LeetCode 647	Palindromic Substrings	Medium	Use a boolean[][] array to record whether the substring from i to j is a palindrome. Then count the palindrome substrings from length of 1 to length of n. In total, it takes O(n^2) time.
LeetCode 361	Bomb Enemy	Medium	Like the game bomb man. We can use a rowCnt and an array colCnt[j] to record the enemies at the current coordinate we can kill. When we meet a "Wall" grid or it's at the start row or column (i == 0 or j == 0), we should initialize rowCnt and colCnt[j].

Math

#	Title	Difficulty	Comment
LeetCode 263	Ugly Number	Easy	Decomposing prime factor by 2, 3, 5
LeetCode 445	Add Two Numbers II	Medium	Add two numbers which are stored in two linked list. Use two stacks to solve it. Don't forget to check carry after while loop.
LeetCode 957	Prison Cells After N Days	Medium	Similar to Game of Life. But there must be a cycle in this question, since we only have 2^8 possible states. So if N is larger than 2^8, definitely it must have two same states and then it will lead to a cycle. Therefore, our problem now is becoming a question of finding a cycle. We can use a HashSet<String> to store the current states we have. The key is generated by Arrays.toString(). Note that we don't need to add the initial state into the hashSet, since we don't know whether the initial state is a part of the cycle. We can prove that not adding the initial state can calculate the cycle properly. (See comments)
LeetCode 204	Count Primes	Easy	The Sieve of Eratosthenes Algorithm. The core of this algorithm is to mark the numbers as non-primes starting from i*i. See Sieve of Eratosthenes Algorithm. Starting from 2 until sqrt(n), for each number, if it is prime, mark the number starting from *i to n as non-primes, in each step of the iterations, increase i by i. Finally, counting all the primes from 2.
LeetCode 866	Prime Palindrome	Medium	All even palindrome numbers are non-primes. See All Even Length Palindrome are Divisible by 11. Checking whether a number is prime takes O(sqrt(n)) time, while checking whether a number is palindrome takes O(log(n)) time. So we first form a palindrome greater than N, then check if it is a prime. We can form a odd palindrome number by forming a halve and reversing it (remove the first digit since we need a odd palindrome), then concatenating the two part. Finally, judge whether the gernated number is greater than N and whether it is a prime.
LeetCode 168	Excel Sheet Column Title	Easy	Similar to getting each digit in a decimal.
LeetCode 1323	Maximum 69 Number	Easy	One solution is to convert the integer to a String, then do modification. Another idea is to read the integer's digits from high to low. See how to do it in the code.
LeetCode 523	Continuous Subarray Sum	Medium	Find a subarray (size is at least 2) which sums up to k * n, n can be any integer (include e.g. -2, 0, 1, ...). The core idea is that first we get the moded prefix sum array since (sum + n * k) % k <=> sum % k , then if there's a pair that two prefix sums have the same value, return true. Note that the size of the subarray must be larger than 1, so we require a HashMap to record the sum and its first occurring index. And be careful to handle the corner cases (see code comments). Think about why we need to put a (0, -1) when initializing the hashmap.
LeetCode 537	Complex Number Multiplication	Medium	Split by `\+
LeetCode 1015	Smallest Integer Divisible by K	Medium	Why only iterating from [1, K]? Why not 2 and 5? - Suppose we have two 11..11 number a & b which have the same remainder by K, so a % k = b % k and a - b = 111..10000 (a-b ones & b zeros) => (a - b) % k = 0. Since we have iterated to a, a must be larger than a - b, so the left part 111...1 (a - b ones) in 11..000, can not be divided by K, so now we only remain the right part 1000..0 (b zeros). 1000..0 (b zeros) only have two factors: 2 & 5. So if K is not multiple of 2 and 5, there can not be the case that has same remainders.
LeetCode 202	Happy Number	Easy	Only have two cases for a happy number: one is having a cycle, the other is ending in 1. How to prove? Since the square of each digit can only be 81 at most (which is less than 100), the sum of all digits' square must be less than 100*n. For the numbers having 3 or more digits, the sum must be smaller than the number itself. So this transformation will reduce the original number. So it must have duplicate when the range shrinks.
LeetCode 1227	Airplane Seat Assignment Probability	Medium	Probability formula derivation.

Graph

#	Title	Difficulty	Comment
LeetCode 997	Find the Town Judge	Easy	The judge's out-degree must be zero and it's indegree must be N-1.
LeetCode 277	Find the Celebrity	Medium	Similar to LeetCode 997. Intuitively, we need to check whether there's a node whose in-degree is N-1 and out-degree is 0. It takes O(n^2). But we have a two-pass approach to solve this problem. In the first pass, we can record the one which isn't connected by any vertex. Then, in the second pass, we can check whether there's another vertex connecting to this candidate vertex. **Note that **a special case is that there're two candidates (e.g. there're two connected components), so in the second pass we need to check `knows(celebrity, i)
LeetCode 433	Minimum Genetic Mutation	Medium	Construct graph then use BFS to get the shortest distance. There's a trick in this question for getting neighbors in the graph. Instead of compare every string in the bank, since the letters for DNA can only by in A, C, G, T, we can use two sets bankSet & visitedSet to store the bank and the visited set. Then we start at the start string, change one letter in the string and check whether it is in the bank set. If exist, there's an edge.

System Design

#	Title	Difficulty	Comment
LeetCode 382	Linked List Random Node	Medium	Reservoir Sampling. We can use this algorithm without knowing the size of the dataset to randomly pick k elements. For the first k-th elements, we just put them into the reservoir directly. For the (k+1)-th to n-th elements, we will have a probability of k/(k+i) to select it and a probability of 1/k for each element already in the reservoir to be replaced by the (k+i)-th element. See the proof in the code.

Other

#	Title	Difficulty	Comment
LeetCode 418	Sentence Screen Fitting	Medium	Good Question. Precomputing that if a line started from sentence[i] in the begining of the line: 1. how many times the sentence can be filled in; 2. which word will be the beginning word for the next line.