Algo Advance

Sweep (or scanning) line algorithm is very efficient for some specific questions involving discrete intervals. The intervals could be the lasting time of events, or the width of a building or an abstract square, etc. In the scanning line algorithm, we usually need to distinguish the start and the end of an interval. After the labeling of the starts and ends, we can sort them together based on the values of the starts and ends. Thus, if there are N intervals in total, we will have 2*N data points (since each interval will contribute 2). The sorting becomes the most time-consuming step, which is O(2N*log(2N) ~ O(N*logN). After the sorting, we usually can run a linear sweep for all the data points. If the data point is labeled as a starting point, it means a new interval is in the processing; when an ending time is reached, it means one of the interval has ended. In such direct way, we can easily figure out how many intervals are in the processes. Other related information can also be obt...

Binary Search - Hard Level - Question 1 Leetcode 410  Split Array Largest Sum Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays. Constraints: 1 <= nums.length <= 1000 0 <= nums[i] <= 10^6 1 <= m <= min(50, nums.length) Analysis: This question seems not to be related with binary search, actually it does! The key argument is: if there is a value, say X, is the minimum of the largest sum among these m non-empty subarrays.  Then all the values below X cannot divide the array into m non-empty subarrays (should be larger than m).  Why? We can proof it by contradiction: if a value smaller than X, say Y, can be the minimum of the largest sum among these m non-empty subarrays, then X is NOT the minimum as claimed in the first sentence. Thus, there is no such Y existed. If all the values smaller than X ca...

Binary Search - Hard Level - Question 2 Leetcode 727 Minimum Window Subsequence Given strings S and T, find the minimum (contiguous) substring W of S, so that T is a subsequence of W. If there is no such window in S that covers all characters in T, return the empty string "". If there are multiple such minimum-length windows, return the one with the left-most starting index. Note: All the strings in the input will only contain lowercase letters. The length of S will be in the range [1, 20000]. The length of T will be in the range [1, 100]. Analysis: The first step to think about this question may be how to determine a string is a subsequence of another string?  We can use the two-pointer method: one is a pointer to the beginning of the first string and the other one is a pointer for the second string (to be matched). Once the second pointer can reach the end of the second string, it means we have found a subsequence in the first string. The time complexity for this step is O(...

 Question List: Question 1: Minimum Window Substring More Questions Upper Layer

Leetcode 76. Minimum Window Substring Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string. Constraints: m == s.length n == t.length 1 <= m, n <= 10^5 s and t consist of uppercase and lowercase English letters. Analysis: The first step to do is to count the letters in string t, since the relative order of chars does not matter. After the counting, we can use two pointers method on string s: starting with beginning of the string s, the second pointer can continue to move until the sub-string [i, j) has all the chars in t, where i the index of the first pointer, and j is the index of the second pointer. We are looking for the sub-string with the minimum leng...

Sliding window is one common trick used in coding, which may not be counted as one "algorithm" by itself. Nevertheless, this trick is popular in tech code interviews, perhaps due to its relative "short" length (?). The size of the window could be either fixed or non-fixed, depends on the questions. When the size is non-fixed, two pointers are usually used to maintain the size of the window. Thus, the "two-pointer" method may be considered as a variant of the sliding window trick. The first point stands for the starting side of the "window" and the second one represents the ending side of the "window". When does the sliding window trick work? Usually string matching, or sub-array / sub-sequences may be considered to use the sliding window trick. The key point is that the question can be gradually solved by the evolution of the sliding window from the beginning of a string/array to the end. To sum up, sliding window 1. is a common trick i...

Graph - Example Leetcode 133 . Clone Graph Given a reference of a node in a connected undirected graph. Return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. class Node {     public int val;     public List<Node> neighbors; } Test case format: For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph. The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph. Constraints: The number of nodes in the graph is in the range [0, 100]. 1 <= Node.val <= 100 Node.val is unique for each node. Th...

Graph is a very useful data structure which has versatile applications in many fields. It is impossible to cover all the aspects of graph-related algorithm, (the same as all the other topics in the posts), we will focus on some basics, especially that may be useful in code interview. The two basic components of a graph is vertex (or node) and edge. Vertices are connected by edges. Graph can be directed graph or un-directed graph. The directed graph has directed edges; the undirected has undirected edges. The common representation of a graph can be adjacent matrix or list. If use adjacent matrix, the element is usually set as 0 or 1. 0 means there is no edge, and 1 mean connected. If use adjacent list, usually the index of the list is the source node, and the elements in the list is the connected nodes from the source. Other important concepts are the indegrees and outdegrees.  The indegree of a node means the number of edges pointing to it; the outdegree of a node means the number ...

Leetcode 37 . Sudoku Solver Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells. Constraints: board.length == 9 board[i].length == 9 board[i][j] is a digit or '.'. It is guaranteed that the input board has only one solution. Analysis: This is a another classic backtracking question. We can try to solve the Sudoku row by row. Base case: if finish the last row, then we find a one solution, done; if finish one row, we can move onto the next row; if the current position is a number, move onto the next position; if not a number, we can make nine trials: 1 - 9. If one of them can reach the end and return true, we find one solution, done; if none of the...

 Leetcode 52 . N-Queens II The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle. Constraints: 1 <= n <= 9 Analysis: The answer to the previous question can be used directly: just need to return the size of it. For the coding part, we do not need to record the actual solution, so simplification of code can be done. The idea is the same as the previous question: try to place a queen for each row .  And we just removed the previous vectors to record the solution. Instead, we just count the number of solutions. See the code below: class Solution { public: int totalNQueens(int n) { ps.resize(n); fill(ps.begin(), ps.end(), -1); bt(0, 0); return res; } private: int res = 0; vector<int> ps; void bt(int r, int ct) { if(r == ps.size()) { if(ct == ps.size()...

Leetcode 51 . N-Queens The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively. Constraints: 1 <= n <= 9 Analysis: For each row, we can only put one queen, so we can make the trial row by row. For each row, every position is possible to place the queen. Once the queen is set, the position should be recorded, since this information has limitations on new queen's position. To simply the record and also the check, we can use a one dimensional array for this: the index is for the row, and its value for the column. Both information determines the position of the queen placed. Once reached the last row, we can check how many queens ha...

 Question List: Question 1: N Queens Question 2: N Queens II Question 3: Sudoku Solver More Questions Upper Layer

Backtracking may be one of the most "brute-force" algorithm. When all the other algorithms, such as, breadth-first-search (bfs), depth-first-search(dfs), and others, do not work, we can consider backtracking. With backtracking, the problem will be solved incrementally. One of key features of backtracking is that we will do a "try step" first. Then we continue the search. If eventually the result is not valid, we have to back-track the "try step". And then make a second "try step", and so on, until make all the possible try steps. If there are N steps in total, and for each step, there are M possible trials, then the overall complexity is (M^N), which increases really fast as a function of M or N. The trial structure is layer by layer: once you make a trial, then based on this trial, you may continue to make the next trial on the "next layer", since we do not know yet whether the trials is a valid one or not. So we may have a chain of tr...

Depth-first-search - Medium Level - Question 1 Leetcode 113 . Path Sum II Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where each path's sum equals targetSum. A leaf is a node with no children. Constraints: The number of nodes in the tree is in the range [0, 5000]. -1000 <= Node.val <= 1000 -1000 <= targetSum <= 1000 Analysis: If the root is null, we can stop searching. Starting with the root, we only have two ways to go: the left child and the right child. Once we move on to the next step, we need to update the conditions: the sum and the path. When the node is a leaf, we should check the sum, to see whether it reaches 0 or not (here we use the targetSum - node.val. You can use the sum of all the nodes on the path, but need one more variable). If the sum is 0, then we find one path, so we can save it in the final answer; if not, we will stop this route and continue the search with other routes. Since we switch from on path to ...

Depth-first-search - Easy Level - Question 1 Leetcode104 . Maximum Depth of Binary Tree Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Constraints: The number of nodes in the tree is in the range [0, 10^4]. -100 <= Node.val <= 100 Analysis: A binary tree has a recursive structure in nature: the left child is the root of the sub binary tree on the left; the right child is the root of the sub binary tree on the right. So we can apply DFS to this question:  1. the base cases: if the node is null, return 0; if not 2. the maximum depth should be 1 + max(Maximum Depth of the left sub tree, Maximum Depth of the right sub tree). See the code below: /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode...

  Leetcode 200  Number of Islands Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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. Constraints: m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] is '0' or '1'. Analysis: The DFS can also be used to solve this problem: once we find an element of 1, we can expand the searching in four directions. To avoid redundant scans, we need to label the positions visited. Once the search is done, the count of island is updated by adding one. Similar to the BFS, a trick is used in the for loop for the four direction expansion, to short the code. See the code below: class Solution { public: int numIslands(vector<vector<char>>& grid) { if(!grid.size() || !grid.front().size()) re...

As discussed in the previous posts about the breadth-first-search (bfs), the Depth-first-search (dfs) is another common brute-force searching algorithm. In the dfs, we start with an initial condition for one route, then gradually reach the end of one route; then we repeat the searching on the second route, the third route, ... Therefore, we can make the following summary: 1. a dfs is one kind of recursion. When search from the current step to the next one, we will call the same function again; 2. the end condition (or base case) should be defined; 3. when the same function is called, the parameters should be updated converging to the end conditions; 4. a dfs should cover all the possible routes; One possible optimization could be memoization, to record the result once a route is finished; then if we have the change to meet with the same route again in the searching, we could use the saved results directly without reaching the end. In short this method is usually called as dfs + memo, w...

Leetcode 407 . Trapping Rain Water II Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining. Constraints: m == heightMap.length n == heightMap[i].length 1 <= m, n <= 200 0 <= heightMap[i][j] <= 2 * 10^4 Analysis: If you have a bucket built with pieces of woods, then the amount of water is determined by the wood with the lowest height. So we view the two D matrix as a square bucket.  The first step is to put all the elements in the peripheral into a reversed prority_queue (pq), which serves as the "wall" of the bucket. Then start with the smallest elements, we can do a bfs search; 1. all the smaller elements should have contributions, the magnitude is the height diff; 2.  all the larger or equal elements become the "new walls", so keep them in the pq. In step 1, we can do a second bfs, to make sure all the connected lower elements are counted. The highe...

Leetcode 42 . Trapping Rain Water Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Constraints: n == height.length 1 <= n <= 2 * 10^4 0 <= height[i] <= 10^5 Analysis: This a classic question for interview. If the water can be trapped at one position, then it requires there are two higher integers on its both side. So the question becomes how to decide the two sides. We can use two vectors to record the largest integer so far: one is vector<int> left and the other is vector<int> right, 1. left[i] represents the largest elements so far from the left side; 2. right[i] represents the largest elements so far from the right side; (Note: this is a very common trick used in dynamic programming .) After having this information, we can do a third scan: for each element, just need to pick up the difference between nums[i] and the min(left[i], right[i]). The time complexity is O(3...

 Question List: Question 1: First Element Larger Question 2: Trapping Rain Water 1D Upper Layer

Questions: We have an integer array with size n. The index of the first number is 0, and the last one is n-1. For each number, please find the index of the first number higher than it on the right side. If there is no such number, return -1. Constains: 1 <= n <= 10^5 Analysis: If we fix each number, then run a for loop for all the numbers on its right side in the array, we can find the first number that is larger. But the time complexity would be O(N^2) overall. We need to find a solution that runs faster. A stack can be used for this: since we are looking for the first element higher on the right side, we can maintain a monotonically decreasing order inside the stack. When scanning to a new number,  1. if the stack is empty or the top element (the end of the numbers in the stack) is larger, just put the new number in the stack. Since the new number is smaller, the numbers in the stack still decreases; 2. if the stack is not empty and the top element is smaller than the new n...

Stack is a common data structure that is used in many circumstances. The most distinct feature is that the element coming first will be popped out last, or in short "first in last out". Besides this, we can always know the size and the top element of a stack in constant time. If we just look at the properties of a stack, it seems pretty simple. However, the "first in last out" feature turns out to be very powerful, especially when solving some trick programming questions, which can be found in the example questions below. Some declaration of stacks are shown below: stack<int> sk1; stack<double> sk2; stack<string> sk3; stack<pair<int, int>> sk4; if(sk1.size()) { int first = sk1.top(); sk1.pop(); } if(!sk2.empty()) { double d = sk2.top(); sk2.pop(); } Question List Upper Layer

 Leetcode 211 . Design Add and Search Words Data Structure Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter. Constraints: 1 <= word.length <= 500 word in addWord consists lower-case English letters. word in search consist of  '.' or lower-case English letters. At most 50000 calls will be made to addWord and search. Analysis: This question asks to build a word dictionary, which essentially a trie. So we can define a node structure which has 26 children and a Boolean to label whether a string (or prefix) a word or not. With this node structure, we can build a trie contai...

 Question List Question 1:  Maximum XOR of Two Numbers in an Array Question 2: Design Add and Search Words Data Structure More Questions Upper Layer

 Leetcode 421 Maximum XOR of Two Numbers in an Array Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n. Constraints: 1 <= nums.length <= 2 * 10^5 0 <= nums[i] <= 2^31 - 1 Analysis: The naïve method is to use a two-layer for loop, to check every pair of numbers. The total time complexity is O(N^2), which  is too large since N could be 2*10^5. There are methods to using the bit-wise operations directly, which will be discussed in the Bit Manipulation post. Here we will focus on the method using trie. The key ideas are: 1. for each number, there are 32 bits. For each bit, only two possible values are available; thus we can build a binary trie to store all the numbers; 2. once the trie is built (the height is 32), we can iterate array, for each number we can check its 32 bits along with the trie layer by layer (32 layers). If the bit for the number is 1, we want to find the node with a bit value of 0 (why?...

Trie is a data structure belonging to n-ary trees, which is designed for some specific questions, such as, prefix of strings. (If you have never known what binary tree is, maybe you can check binary tree first before read more about Trie). The fact that there are only 26 different letters greatly reduce the possible choices for each position. Or to make it clear, for each position, there are 26 different choices. In mathematics, it seems to be very large (height^26 for the full tree), but in reality, it is rare to be a full tree for the set of meaningful strings (needs at least height^26 strings to be a full tree!), since the height or length of English words are less than 10 in most cases. Therefore, it is popular in string matching or related operations. Please be noted that the trie structure is not only limited to strings, the same idea can be extended to other data types, such as integer (then it becomes a binary tree, since for bit, there are only two possible values). In the cod...

 Leetcode 416 Partition Equal Subset Sum Given a non-empty array nums 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. Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Analysis: There are different ways to solve this problem, such as dp with a time complexity of O(N^2). Since N is small to this question, so it is Okay to pass OJ. Besides the small N, the value of each element is also very small. So this gives us some chance to use "space to trad off time". The data structure to be used is bitset. For bitset, each bit can be either 0 or 1. The index of that bit can be used as the corresponding sum. When the bit is 1, means there is a sum with the value of its index. When a new number comes, this number needs to be added to all the previous sums, to form new "previous" sums. Thus for each number, we need to go through all the previous sums, the time co...

  Leetcode 136 Single Number Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space. Constraints: 1 <= nums.length <= 3 * 10^4 -3 * 10^4 <= nums[i] <= 3 * 10^4 Each element in the array appears twice except for one element which appears only once. Analysis: If there is no space limitation, this question can be solved by counting easily. But counting requires additional space. Here we can use xor (^) operation based on some interesting observations:  A^A = 0, here A is any number A^0 = A, here A is any number Since all the number appears twice except one, then all the number appear even numbers will be cancelled out, and only the number appears one time is left, which is what we want. See the code below: class Solution { public: int singleNumber(vector<int>& nums) { int res = 0; for(auto ...

Bit manipulation represents the elegant and concise facet of algorithms. Apparently, it is based on how the computer stores the information. With such down-to-the-bottom level data structures or operations, the space usage is usually the minimum. The least usage of space makes the speed fast as well. The unit is bit, which only has two possible values, 0 or 1 (which is exactly the reason that the base is 2, or binary). For the integer data type (int) in most computer system nowadays, there are 32 bits.  Byte is different from bit. Each byte has 8 bits (so one integer has 4 bytes in size). Thus, the value range of a byte is in [0, 2^8 = 256) (if you know ACII code before, have you ever ask why the range is [0, 256)?). This connects to some very common words used daily,  1 KB is (2^10 = 1024 ~ 10^3) byte  1 MB is (2^10 = 1024 ~ 10^3) KB  1 GB is (2^10 = 1024 ~ 10^3) MB  1 TB is (2^10 = 1024 ~ 10^3) GB If we have an integer array with a size of 10^6, the total size...

 Question List: Question 1: Non-overlapping Intervals Question 2: Longest Increasing Subsequence More Questions Upper Layer

 Leetcode 435  Non-overlapping Intervals Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Constraints: 1 <= intervals.length <= 10^5 intervals[i].length == 2 -5 * 10^4 <= starti < endi <= 5 * 10^4 Analysis: This question is equivalent to a classic question: interval scheduling, which searches for the maximum number of un-overlapping intervals. Once this number is found, then it is straightforward to calculate the minimum number of intervals to be removed. When all the intervals are sorted with the ending time, then we can always pick up the first interval as the first step. Why does this always give the optimal result? Because this interval ends the earliest! Just because it ends the earliest, choosing it cannot be worse than choosing other intervals. Thus we can greedily choose the first one. After the first one is chosen, we c...

Greedy Algorithm is one of the intuitive algorithms that appear not complicated to understand. As indicated by its name, greedy algorithm picks up the extreme values for each step since the beginning. Thus, greedy algorithm is only valid when the optimal of every step, or the optimal on the fly, is guarantee to be true, which is usually not. The interesting part is that, when the greedy algorithm is valid to a question, it is usually not difficulty to "find it". However, it is not rare that the proving of the valid is not straightforward. One of the ways to prove the correctness is proof by contradiction. To make a brief summary: 1. greedy algorithm requires the correctness to pick up the extreme value for each step; 2. the proof of the validity of greedy algorithm usually is not easy. Question list Upper Layer

 Question List: Question 1: Minimum Cost to Hire K Workers Question 2: The Number of the Smallest Unoccupied Chair Question 3: Trap Rain Water II Question 4:  K Closest Points to Origin Question 5: Top K Frequent Words More Questions Upper Layer

 Leetcode 1942  The Number of the Smallest Unoccupied Chair There is a party where n friends numbered from 0 to n - 1 are attending. There is an infinite number of chairs in this party that are numbered from 0 to infinity. When a friend arrives at the party, they sit on the unoccupied chair with the smallest number. For example, if chairs 0, 1, and 5 are occupied when a friend comes, they will sit on chair number 2. When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair. You are given a 0-indexed 2D integer array times where times[i] = [arrivali, leavingi], indicating the arrival and leaving times of the ith friend respectively, and an integer targetFriend. All arrival times are distinct. Return the chair number that the friend numbered targetFriend will sit on. Constraints: n == times.length 2 <= n <= 10^4 times[i].length == 2 1 <= arrivali < leavingi <= ...

Dynamic Programming - Hard Level - Question 1  Leetcode 1937  Maximum Number of Points with Cost You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix. To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score. However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c1) and (r + 1, c2) will subtract abs(c1 - c2) from your score. Return the maximum number of points you can achieve. abs(x) is defined as: x for x >= 0. -x for x < 0. Constraints: m == points.length n == points[r].length 1 <= m, n <= 10^5 1 <= m * n <= 10^5 0 <= points[r][c] <= 10^5 Analysis: Based on the description, we can define dp[i][j] as the maximum number of points wit...

Dynamic Programming - Hard Level - Question 2 Leetcode 1931  Painting a Grid with Three Different Colors You are given two integers m and n. Consider an m x n grid where each cell is initially white. You can paint each cell red, green, or blue. All cells must be painted. Return the number of ways to color the grid with no two adjacent cells having the same color. Since the answer can be very large, return it modulo 10^9 + 7. Constraints: 1 <= m <= 5 1 <= n <= 1000 Analysis: One of the difficulties is how to define the state. In the process of defining a state, we need to consider two questions: 1. is the state defined a full description of the problem asked? 2. how can we derive the transition formula from the previous calculated states? For this question, it is a matrix, so a natural choice is to use the index i and j. But this is not enough, since at each position we have three choices, (and its color should be different from its neighbors). So a third parameter is ne...