Algorithm-Leetcode

#	Title	Solution	Basic Idea
255	Graph Valid Tree	Python	We want to use bfs to validate tree structure from the given undirected edges list. First we can check whether the graph has a cycle by checking if length of the edge list is not equal to the n-1 where n. We consider two ways to represent the graph either adjacency list or adjacency matrix. Since this graph is close to be a sparse graph, where the number of edges are much less than V^2 we would like to use the adjacency list. Therefore, first step is to convert the edges list to the adjacency list. We want to check if any part of vertex is disconnected and visited vertex. So we create seen hashset for this task with our first vertex in it Use Queue data structure for looping and enumerate the neighbors got from the adjacency list and if the neighbor not exist in the seen hashset, then we add the neighbor into seen hashset and queue, this way we don't visit the same vertex repeated. Finally return whether length of the seen hashset is equal to the n creating adjacency list takes Time O(v+e) and space O(v+e) looping the queue takes time O(v) by making sure we are not enquing the visited vertex and dequing take constant time. seen hashset takes O(v) space where v is the length of the vertexis and e is the length of the edges in the graph
254	Word Break	Python	We want to check every consecutive subset of the given string, i.e. l, e, le, e, lee, ec, e, leet, eet, et, t, ... , de, e. are possible to make it by using given word in wordDict. We want to create a dp table with a size of length given s + 1 and each position holds True or False based on whether it's possible to create the word is possible to create with wordDict. Initialize the dp table with False value and assign its first index True because an empty string is always possible to create. Now, we want to have two index (i,j) to find the current slice point to get every possible consecutive substring from s. We want to iterate i from 1 to length of the given string s + 1 and iterate j from 0 to i excluding. Now, we check if the current slice word (s[j:i]) is possible to make s[:i] word with the previous information that we found s[j]. If s[j] is true then it means that s[j] is made with a combinations of words in wordDict. Since we can make the word until j position, now we just need to know whether s[j:i] exists in wordDict, which determining s[:i] is possible to make. If yes, we can update dp[i] to be True. After ending the iteration, we can simply return the last value of the dp table, which tells us that if the given s was possible to make with comibations of wordDict. Creating the dp table taks O(n) time and O(n) space, and the nested for loops takes O(n^2) time and also we are slicing the word at every iteration. Therefore the total running time complexisty is O(n^3) and the total space is O(n) where n is the length of the given string.
253	House Robber	Python	1. Bruth-force: Expontntial time O(2^n) Space O(n) Find every possible subset of the combination not adjacent value each other. When we are traverseing the recursion, we could either include the current value in the nums or not including and pass. When we include the current value, we have to remove the next adjacent value to remove the adjacent value. 2. Talbuation: Time O(n) Space O(n) We want to create dp table to hold the current maximum profit can be made at the index with previous two values in dp. The first dp value is always 0 because we can't make any profit with an empty value and dp[1] value is the nums[0] value because it's the maximum profit can be made with nums[0] vs dp[0]. Now, we want to iterate from 2 to length of nums array + 1 and update the dp table at each iteration. dp[i] is either maximum value of the previous dp value or the one before the previous dp value plus previous nums value. 3. Tabulation Space Optimization: Time O(n) Space O(1) Since we only need two previous values from the dp table, we can eliminate the space and keep track of the values in variables to find the maximum profits can be made.
252	Palindromic Substrings	Python	1. Bruth-force, Checking all substrings: Time O(n^3) Space O(1) 2. Expending Palindrome: Time O(n^2) Space O(1) When we are checking if the string is palindrome, we have to check two conditions - odd length - even length. Iterate the given string, increment the count by 1. Then we will call recursive function findPalindrome twice, one for expending odd length and another one is for expending even length. Check if left and right index are in the bounds and the characters in the left and right are equal. Then increment the palindrome count and move the left and right pointer by one.
251	Longest Increasing Subsequence	Python	Tabultation: Time O(n^2) Space O(n) Iterate from the end of the nums array and at the each index, solve the subproblems by finding how many subsequence can be made at the each index. Then use the subproblem solution to solve the next subproblem until we finally solve the entire nums array elements and return the longest length.
250	Word Search	Python	GraphDFS: Time O(nm * 3^w) where n and m are the length of the row and colume in the board, and w is the length of the given word. The reason why we have 3 directions is because we don't go back to the place where we come from We want to iterate characters in the board and if the character is matching with the first character of the word, we want to traverse in dfs manner to find its neighbors to check if the word can be made. - Iterate the board characters and if the character is matched with the first character of the word, then create a visitedSet hashset and call a dfs function. Base case is when our visitiedSet length is equal to the length of the word, then set global variable found equal to true. Check if the row and col are in the bounds, current character in the board is matched to the word charaacter, and current row and col is not in visitiedSet, then we want to append the current row and col into the visitiedSet and traverse it neighbors(up, left, bottom, right), and at the end of the traverse, make sure to remove the row and col element from the visitiedSet.
249	Unique Paths	Python	1.Bruth-Force, Recursive: Time O(2^nm) Space O(nm) - TLE We want to create a unique path count as global vairable to keep track in the recursion. The base case is when we reach the n and m to the finish position, we increment our unique path count. if n is greater than the finisi row index or m is greater than the finish col index, then re simply return null value otherwise, we call the recursion one incrementing n and another one incrementing m. 2. Memoization: Time O(nm) Space O(nm) We want to count up the number of path on each (row, col) position and store the value into a hashmap to avoid recomputation. 3. Tabulation: Time O(nm) space O(nm) We want to solve the subproblems from the smallest and build way up to solve bigger and finally the original problem. Since we have two ways that we can move either bottom or right, we can find the current position's number of paths by adding the number of bottom paths and the number of right paths. Initially, we want to fill out our dp table with 1s, since every path has at least one path. Now, iterate the grid starting index from 1(0-indexed, position at 2x2) to fill up the table and return the last element in the grid.
248	Search In Rotated Sorted Array	Python	Binary Search: Time O(logn) Space O(1) Take advantage that the given array is sorted in an ascending order possibly rotated at unknown index k. Thus, that index k is the pivot point where every element on the right subarray is smaller than left subarray and both subarrays are sorted. - Use binary search to find the k position where previous value is greater than the current value. - Determine which subarray contains the target based on the k position we found. - Within the subarray, use binary search to find the index of the target, if the target does not exist, return -1.
247	Rod cutting	Python	Tabulation: Time O(n^2) Space O(n), Memoization: Time O(n^2) Space O(n) We want to solve smaller subproblems to solve next bigger subproblem. We know when the rod length is equal to zero, the profit is zero, which is our base case.
246	Construct Binary Tree From Preorder And Inorder Traversal	Python	DFS Recursion Preorder indicates the root of node in order and Inorder indicates each node's left subtree and right subtree. Use recursion with base case checking if the length of the inorder and preorder is 0, then return None, which means that the current child node is empty and also check if preorder length is equal to the one, then return the first index value in the preorder TreeNode. Now, pop the first value in the preorder and create a new node with that value and find the coordinate index from the inorder array. Now assign the new node left and right value by calling the recursion function and slice the inorder array to be subtree of left and right. Fianlly return the made root to combine them as a tree structure.
245	Maximum Subarray Divide and Conquer	Python	The greatest sum over all subarrays must be in these three options - A[low .. mid] - A[mid+1 .. high] - crossing the midpoint We can find maximum subarrays on the A[low .. mid] and A[mid+1 .. high] recursively because these two subproblems are smaller instances of the problem of finding a maximum subarray. Now, find maximum subarray in crossing mid point and take a subarray with the largest sum of the three. Find maximum subarray corssing the midpoint This problem is not a smaller instance of our original problem because it has the added restriction that the subarray it chooses must cross the midpoint. Any subarray crossing the midpoint is titself made of two subarrays A[i .. mid] and A[mid+1 .. high]. Therefore, we just need to find maximum subarrays of the form A[i .. mid] and A[mid+1 .. j] and then combine them. Analysing Running Time: the recursive call for finding maximum subarrays in A[low .. mid] and A[mid+1 .. high] takes 2T(n/2) and finding crossing subarray takes O(n) time. 2T(n/2) + O(n) = O(nlogn)
244	Top K Frequent Elements	Python	1.Heap(Priority Queue) and hashmap: Time O(nlogn) Space O(n) We want to create a frequency table of each number into hashmap. The key value is unique and store the key into an array, uniqueNums and use this array to create and populate a 2D array holding tuple of (uniqueNumCount, key). Now, call heapify function on this newly created 2D tuple array. This computation will give us the minimum count at the first array position. Now, pop out the n-k number of elements from the heap, which we are removing the smallest count. And we return the leftover unique number in the heap as an array. 2. Bucket Sort: Tiem O(n) Space O(n) Since the maximum number of the nums is unbounded, we want to make the bucket index with the count and values as an array. For example, i(count) [0,1,2,3,4,5,6] value [-,[1],[2],[3],-,-] Now, we want to find k number of the most frequenct elements. Iterate the array from the bucket from the behind since the highest frequent elements located at the last, and append the elements to the final result array. Once the length of the result array is equal to the k, then return the result array.
243	Set Matrix Zeroes	Python	1. Additional Memory:Time O(nm) Space O(n+m) Store the indices of the initial 0s to convert the row and column to zero while not effecting converted 0s. Then convert the entire row and column of the each 0s position from the created indices array. It's important to iterate the matrix from the top to bottom in order to reduce time complexity. - Create indices array to hold 0s - Iterate the indices array and call a function named, traverseNeighbors by passing matrix, i, and j indices - Store i and j into a stack - convert the current position value to 0 - store the neighbors only if it's in the boundry the value is not 0. 2. Space Optimized Solution: Time O(nm) Space O(1) Use first row cell and first colume cell as an indicator and two additional variables to flag firstRow and firstCol if we need to change the first cell to zeros. - Iterate the matrix and mark the indicator(first cells) and those two variable, firstRow and firstCol. - Iterate from 1 to the length of the matrix row and check the first column of each row has zero value, then iterate from 1 to the length of the matrix column and convert matrix value to 0 - We want to perform similarly from right above step but switch row and column. - check if firstCol and firstRow flag is on, then change the first cell value to zero.
242	Find If Path Exists In Graph	Python	Graph Traversal, DFS and BFS:Time O(e) Space O(v+e) Use either DFS or BFS to find a path from given start to end vertax. Since the graph is an unriected, we have to mark visited vertax to avoid infinite cycling. - Create a visited array initially false values with the number of vertaxies and adjacency list from the given edge list. - Call a DFS function with arguments, visited, adjacency list, start, and end. - Use stack to store initially start vertax and loop while the stack is not empty. - Pop the stack value into a node and continue if node is null or node is already visited. - Mark the current node visitied value to True - Return True only if the currnet node is equal to the end node, which means that we found a path - Otherwise, iterate the current node's neighbors and append it to the stack - After traversing all possible path from the start, if the path doesn't exist, return False
241	Clone Graph	Python	Recurisve DFS Hashmap Deep Clone: Time O(n) Space O(n) where n is v + e. We want to copy every node and connect the nodes in an unriected way. We use recursive function to clone each node and first we check if the current node is in the hashmap, means that we already made a clone and visited, then just return that node from the hashmap. Otherwise, we create a new copy node from the original node and store that node into our hashmap. Now iterate the all the neighbors from the original node and append it to the copied node's enighbors properties. And finally we return the copy of the node at the end of the recursive function.
240	Linked List Cycle	Python	Hashmap: Time O(n) Space O(n) Traverse the linked list and append each node into the hashmap. During the traversal, if we find a same node by checking the hashmap, then we found a cycle. Iterative Floyd's algorithm: Time O(n) Space O(1) Create slwo and fast pointers, where slow pointer increment the position by 1 and fast pointer increment the position by 2. If both pointers are not null and pointing to the same node, then we know that we found a cycle by the floyd's algorithm. Recurisve Floyd's algorithm: Time O(n) Space O(n)
239	Same Tree	Python	Recursive: Time O(n) Space O(logn) Iterative: Time O(n) Space O(logn)
238	Symmetric Tree	Python	Recursive: Time O(n) Space O(logn) Iterative: Time O(n) Space O(logn)
237	Subtree Of Another Tree	Python	DFS Recursion: Time O(n * m) Space O(h) First use DFS to find where two nodes have same value. Once we found it, not call another recurisve function to check if both of the trees have same strueture. If both of the nodes are null, then return True. After that check, now we check if either node has null, then we know the disequality, so return False. Otherwise, as long as the both nodes have the same value, keep traverse both nodes and finally return true if left and right result are all True.
236	Insert Interval	Python	Sort: Time O(nlog) Space O(n) Append the new interval into the given intervals array. Then sort the array by the starting time. Iterate the array and merge the overlapping intervals. Greedy algorithm: Time O(n) Space O(n) - Create a new array merged and append intervals where the start time is less the new interval. - If it merged array has at least one interval and the interval is overlapped with new interval, then merge with new interval. Otherwise, simply append new interval into the merged array. - Now, our merged array is needed to append the left over intervals and also check if the intervals are needed to be merged. Previously our initial loop to insert intervals before the new interval doesn't need to check if it's needed to merge because given intervals doesn't have overlapped intervals.
235	Meeting Rooms	Python	Bruth-force: Time O(n^2) Space O(1) Store the ith meeting interval into a variable pre, and jth meeting interval into a variable curr. If the pre meeting starting time is greater than the curr meeting starting time, we swap each other in order to have eariler meeting in a pre variable. Now, if pre meeting ending time is greater than the curr meeting starting time, we know there exists a conflict, so return False. Sort intervals by meeting starting time in the intervals: Time O(nlogn) Space O(1) Create a variable pre to store the previous meeting ending time in order to detect overlap, initially assign -inf value. Enumerate the intervals and if pre(previoud meeting ending time) is greater than the start(current meeting starting time), which means that we detect the time overlap, so return False. otherwise, assign the pre to the current ending time and keep iterate the intervals.
234	Kth Smallest Element in a BST	Python	Recursive DFS: Time O(n) Space O(h) We know that if we use in-order tree traversal, we know kth element is located at kth traversal position in in-order. Simply traverse the tree in-order and count the number of node to match with given k. We can return the node's value when k is equal to the count. Iterative DFS: Time O(n) Space O(h)
233	Lowest Common Ancestor Of a Binary Search Tree	Python	Traverse the tree in dfs manner and check if the current node is not empty and the current node's value is greater than equal to the p and smaller than equal to the q, or if the current node's value is greater than equal to the q and smaller than equal to the p. If this condition is true, then we found the lowest common ancestor. Time O(n) Space O(h)
232	Restore IP Addresses	Python	Given string length has to be greater than equal to the 4, otherwise it cannot make a valid ip addresses. We will use three for loops to create all possible ip addresses. In the first loop, create an address array with size of 4 to hold each valid ip address. Now we copy the first ip address with minimum length possible, then we conitnue if the current extracted address is valid. In another for loop, we extract second position address and conitnue validation. Lastly, we extrac both third and forth position addresses and if they are valid, then we append it to our final array Time O(1) Space O(1)
231	Permutations II	Python	Backtracking: Time O(n!n) Space O(n!) - Sort the given array to detect duplicates. - If given number array is empty, then append path to the final result array. - Iterate the number array and if index i is greater than 0 and nums[i] is equal to the previous value nums[i-1] then continue, which means that we detect duplicate so ignore it. Call recursion with new array and path.
230	Combination Sum	Python	Backtracking: Time O(n^(t/m - 1)) Space O(t/m) where n is the number of elements in the array, t is the target, and m is the minimum value among candidates. The execution of the backtracking is unfolded as a DFS traversal in a n-ary tree. The worst case will be n-ary tree's minimum times of tree height.
229	Combination Sum II	Python	Backtracking: Time O(2^n * n) Space O(n) - Sort the given candidates array and call a recursion function with a start index, path, and current sum. - If current sum is equal to the target, append the path to the final result array. - Iterate from the start index to the length of the given array candidates. - Calcultae the new current sum if it's greater than target, we can simply return since it's sorted array, we know that the all the later values in the ascending sorted array are greater. - Checking duplicates is check if the iteration i index is greater than start index and candidates[i] is eqaul to the the previous value, candidates[i-1]. If yes, we know we had this exact combination, so we can simply continue to the next iteration. - Call the recursion function with i+1 and new path and new current sum.
228	Subsets II	Python	Backtracking: Time O(2^n * n) Space O(n) This is similar problem with Subsets from the previous. Only difference is this problem may or may not have duplicate values in the given array. In order to solve, we sort the array first and then do the same algorithm from the subsets one problem while checking duplicate in the final result array.
227	Subsets	Python	Backtracking: Time O(2^n * n) Space O(n) We create a for loop in our subsets function to iterate the given array to n+1(n==len(array)). We call backtracking function in instide of this loop and the iteration index k, will acts as finding a valid solution, if len(path) == k, append to the final result. So we will find all subsets of every length k(0,1,2,...,n). The base case is when length of the current path is equal to k, then append the result to the final array. In recursion body, iterate the given array and in the loop, we append a current valid to the path to try a new partial solution. Then we call a recursion function with new i + 1 and the new path. After exploring the new candidate, we remove the last element from the path.
226	Spiral Matrix	Python	Two 4 pointers to traverse the matrix: Time O(nm) Space O(nm) While startRow less than endRow and startCol less than endCol, use for loop to traverse and handle the edge cases when we are traversing endRow of each colume and startCol of each row if we already traversed previously.
225	Product of Array Except Self	Python	Use one result array to calculate the the product of array except self: Time O(n) Space O(1) Create a variable running that holds the current left or right multiplication.
224	Min Heap Construction	Python	Construct min heap with a given array. implementation of following methods. 1. buildHeap Time O(n) Space O(1) We call siftDown method from every parent nodes, which takes O(logn) times. This can represent the run time of the buildHeap method in a sort of methematical Taylor series that converges to O(n). 2. siftUp Time O(logn) Space O(1) 3. siftDown Time O(logn) Space O(1) 4. Insert Time O(logn) Space O(1) 5. Remove Time O(logn) Space O(1)
223	Binary Tree Level Order Traversal	Python	1. Recursive DFS: Tme O(n) Space O(h) Create a global hashmap to store the each level's node and create dfs helper function passing node and height. If current node is null then return null as the base case. We used preoder traversal here, which we simply store the node value with the current height while traversing. After storing the values into the hashmap, traverse left and right subtree by passing height + 1. 2. Iterative Traversal: Time O(n) Space O(h) Use stack to store the node and the height as a tuple and same process as recursion.
222	Diameter OF Binary Tree	Python	Recursion DFS: Time O(n) Space O(h) The longest path must be between two leaf nodes. We know that in a tree, nodes are only connected with their parent node and 2 children. Therefore we know that the longest path in the tree would consist of a node, its longest left brand, and its longest right branch. So, our algorithm to solve this problem will find the node where the sum of its longest left and right branches is maximized. Use a recursion function dfs to calculate the maximum diameter. Initialize diameter globally and base case is where node is null, return 0. Get left path and right path recursively, and the diameter = max(diameter, leftPath + rightPath). And return max(leftPath, rightPath) + 1
221	Convert Sorted Array To Binary Search Tree	Python	Recursive BST construction: Time O(n) Space O(logn) - Call a helper function with the nums array, start, and end index. - Use a binary search to pick the mid value and construct left and right subtrees.
220	Perfect Squares	Python	1. Memoization Recursion We start from n to reach to base cases where n is less than 0 then return maximum int value, and if n is equal to the 0 then we return 0 as the current height. Create a variable height with a positive infinity value and a square with 1 for subtract each perfect square value. - While n is greater than 2 power of square, get the height of minimum of either returned recursion value with passing n - 2 power of square, or height. Increment square by 1. Store the the height result into memo map and return the height. 2. Tabulation: Time O(nm) Space O(n) - Create an array consists of square numbers with perfect square numbers of less than n. For example, 1, 4, 9, 25, ..., sqrt(n)+1. Create a dp initially filled with maximum integer value size of n+1, and dp[0] to 0. dp table used to count the minimum of the perfect square numbers at i - Iterate i to n+1 times and also iterate square numbers array. Until the end of the square number or i is less than square number, update dp[i] to minimum of either dp[i] or dp[i-square]+1.
219	Maximal Square	Python	1. Bruth Force: Space O((nm)^2) Space O(nm) 2. Tabultation: Time O(nm) Space O(nm) - Create dp table with a size of (m+1) * (n+1) initially filled with 0s. - Iterate the matrix(0-indexed) from 1 to m+1 and n+1. If we found '1' in the matrix, then perform a recurrence relation dp[i][j] with a minimum value from the dp surrounding dp value(top, topleft, left) plus one, and also keep track of the maximum length. - return sqaured value of the maximum length. 3. Space Optimized from Tabulation: Time O(nm) Space O(m) - Create 1-D dp array with a size of m+1, initially filled with 0s and prev valuable to keep track of previous(left) dp value. - Iterate matrix same as above and store current dp[j] value to temp variable to assign this later to prev variable after performing the recurrence relation. - if a current matrix has '1' then, perform a recurrence relation dp[j] with a minimum value from the dp[j-1], dp[j], and prev, also update the maximum length. If the current matrix is not '1', then, assign dp[j] to 0. - Now, we are done with recurrence relation, so assign temp value to prev variable.
218	Find the Duplicate Number	Python	1. Set: Time O(n) Space O(n) - If we can modify the given array, we can simply use set to find the duplicate. 2. Mark As Negative Number in Mutable Array: Time O(n) Space O(1) - If we can modify the given array, we can multiply the visited value with negative one and if we encounter a negative number during the iterations, that means that we found the duplicate value. 3. Floyd's Algorithm(Tortoise and Hare, cycle detection): Time O(n) Space O(1) in immutable array - Use two pointers, slow and fast. Slow moves one element at a time and fast move two elements at a time. When both of the pointers meet at the first meeting point, we will move one pointer to the beginning of the starting point. - Now, we move both pointers by one element at a time. The second meeting point will be the first duplicate value, which the answer and the enterance of the cycle.
217	Merge Two Binary Trees	Python	Recursive: Time O(n) Space O(n) n is a maximum number of nodes between the two trees and for the space complexisty, average case would be logm which is the depth of the tree. - If both of the current nodes exist, then we sum up the node values into root1 node. Then assign the return node of recursion call traversing left subtrees result to the root1.left, and assign the return node of recursion call traversing right subtrees result to the root1.right. At the end of the recursion in this block, return root1, which we made changes and it will be reutnred to the root node of the left or right. - If either of the nodes have null values, simply return root1 or root2.
216	Flatten Binary Tree To Linked List	Python	1. Recurisve DFS: Time O(n) Space O(n) - Base case where current node is none return nothing, and where it's leaf node, return current node. - For a given node, we recursively flatten out the left and right subtrees and store their corresponding tail nodes in leftTail and rightTail respectively. - If there is a left child for the current node, conduct following reconnection. leftTail.right = node.right, node.right = node.left, node.left = null. - Next we have to return the tail of the final, flattened out tree rooted at node. So, if the node has a right child, then we will return the rightTail, else we return leftTail. 2. Morris Traversal: Time O(n) Space O(1) but slidely more time than recursive DFS. - In a pre-order traversal of a binary tree, each vertex is processed in (node, left, right) order. This means that the netire left subtree could be placed between the node and its right subtree. - First, we need to locate the last right node in the left subtree while keeping track of the current node. So, whenever we find a left subtree, we can dispatch a runner(right most in one left from current), then stitch together both ends of the left subtree into the right path of current, takign head to sever the left connection at current. - Once that's done, we can continue to move current to teh right, looking for the next left subtree. When current can no longer move right, the tree will be successfully flattened.
215	Remove All Adjacent Duplicates In String	Python	Use a stack to find the non-duplicate characters. Iterate the characters in the given string and store each character one by one, and check if current character is equal to the last element appended in the stack. If true, pop the last element. At the end of the loop, simply return the stack. Time O(n) Space O(n-d) where n is the length of string and d is total length for all duplicates.
214	Minimum Path Sum	Python	1. Tabulation: Time O(nm) Space O(nm) - Create a matrix same size as given grid. - Traverse grid i as row, j as colume. - Fill the index [0][0] with grid[0][0], and first row with a sum of current grid value and previous matrix value, and first colume with a sum of current grid value and previous matrix value. Lastly, all the other matrix value is a sum of current grid value and minimum of previous grid colume value or previous grid row value. 2. Space Optimized Tabulation By Mutating Given Grid. - Instead of creating a new auxiliary data structure matrix, mutate given grid as we go, which will optimize space complexisty to constant value. 3. Memoization In order to find the minimum path from the top left to the bottom right, we can use backtracking. Backtracking method syas that each and every cell has two methods, either right or down. So, the recursive solution will try all possible ways and the most optimal one return as an answer. Base cases are when i is equal to m and j is equal to n where i and j starts from 0 to n and m, and n is the length of grid row - 1, and m is the length of grid colume -1, which current grid value. If i is greater than m or j is greater than n return max infinity. Recurrence relation is a sum of current grid value and either minimum of mathPath(i+1, j) or mathPath(i,j+1).
213	Min Cost Climbing Stairs	Python	1. Tabulation - Create an array, minCost with size as the length of cost array + 1, which holds a minimum cost to reach ith index. Iterate cost array from index 2 since we can take step either 1 or 2, which means reaching index 0 and 1 would cost 0. The recurrence replation to find ith minCost is the minimum cost of either minCost[i-1] + cost[i-1] or minCost[i-2] + cost[i-2]. 2. Space Optimized Tabultaion: Time O(n) Space O(1) Since we are only using two previous minCost values to get the current minimum cost, we can optimize space to constant space by using just two variables, downOne and downTwo. 3. Memoization - Recursion will take length of cost (i) as an argument and work its way down to the base case where i is equal to 0 or 1 returning 0. The recurrence relation is same as tabulation. Minimum of either minCost(i-1, cost, memo) + cost[i-1] or minCost(i-2,cost, memo) + cost[i-2].
212	Dyanmic Programming Question Set	Python	Five hours of lecture from freeComeCamp.org including both Memoization and Talbulation approach for variaous questions. 1. Fiboanacci 2. GridTraveler 3. CanSum 4. HowSum 5. BestSum 6. CanConstruct 7. AllConstruct
211	Validate Binary Search Tree	Python	- Traverse DFS manner and once we reach the leaf node check if it's valid. - While traversing the tree, keep track of the max and min bounds and check bounds on each. - If any node contains failed the bound check, return false. Time O(n) Space O(d)
210	Lowest Common Ancestor	Python	1. Recursive or Iterative solution Time O(n) Space O(n) - Start traversing from the root node. - If the currNode is none return None - If the currNode itself is either p or q, return node itself. - Store left and right result into variables of recursion. - If left and right are both have nodes, then we found the LCA. Return node. Otherwise, return left or right.
209	Count Good Nodes in Binary Tree	Python	DFS inorder traverse Time O(n) Space O(d) - Count the node where has greater value than any of the previous node values. - Create a dfs function with node and parentVal, where initial parentVal is -inf. - Traverse left and right subtree and keep count the number of count and update the parentVal on each iteration.
208	Path Sum III	Python	1. Bruth Force: Time O(n^2) Space O(n) - Create global variable, count - 1st layer DFS, Use recurisve traverse to go through each node in any order manner - 2nd layer DFS, for each node, walk all path. If the pathSum is eqaul to the target, increment the count. 2. Memoization: Time O(n) Space O(n) - Same as from previous question Subarray Sub Equals K, we create cache dictionary to count up the path. - One difference is after the left and right traverse, which is when we move to a different branch, the currPathSum is no longer available, hence remove one. cache[currPathSum] -= 1
207	Subarray Sum Equals K	Python	1. Bruth Force: Time O(n^2) Space O(1) - Use two loops to calculate currSum and if currSum is equal to the targetSum, increment the count. 2. Memoization of Path Sum: Time O(n) Space O(n) - In order to optimize from the bruth force solution, we will have to think of a clear way to memoize the intermediate result. - Create a dictionary, cache to saves all the pathSum and their frequency. Loop through the array and we can get the currPathSum. If there exist a valid soltuion, there must be a oldPathSum such taht currPathSum - oldPathSum = targetSum. Add the frequency of the oldPathSum in the dictionary to the result.
206	Path Sum II	Python	Binary Tree Recursive DFS. - Base case 1. where node is none, return empty array. - Append the current node into the path and add up the currentSum. 2. If it's leaf node and the currentSum is equal to the targetSum, then append the path to the result array. Otherwise iterate left and right node. - Remove the last the element from the path array. Time O(n^2) for the worst case where the tree is complete tree and has n/2 number of leaf nodes. Copy operation takes extra n time complexsity verses, the best case is where the tree is leaner and has single node. Space O(n) to store the path.
205	Path Sum	Python	Binary Tree Recursive DFS and Iterative Solutions. 1. Recursive DFS - Base case 1. where node is none, return False. 2. where it's leaf node and currentSum is equal to the targetSum, return True. - Compute left and right subtree and if that return value is true, then return true. Time O(n) Space O(d) where n is the number of the nodes in tree and d is the depth of the tree. 2. Iterative - Initially store the root node and curerntSum(0) into a stack data structure. - While stack, if node is empty, simply continue next iteration. - Add up the currentSum and check if it's leaf node and currentSum is equal to the targetSum, return True. Otherwise, append child node from the currentNode and continue the iteration. Time O(n) space O(d)
204	Coin Change	Python	Dynamic Programming Memoization and Tabulation. 1. Memoization Base cases 1. where amount is eqaul to zero, retrun 0. 2. where amount is negative, return -1. - Create a minCount variable and on each iteration, get the returned value into count. If the count is eqaul to the -1, then simply continue to the next iteration. Otheriwse, update minCount = min(minCount, count+1) Time O(nm) Space O(nm) 2. Tabulation Create a ways array filling with -infinity and the first index value is eqaul to 0. Iterate and if current coin is less than equal to the capacity, then update ways[i] = min(ways[i-coin]+1, waqys[i]). Return the value -1 if the last element of the ways is -infinity else last element. Time O(nm) Space O(nm)
203	Partition Equal Subset Sum	Python	Dyanmic Programming Memoization - Calculate total sum of the array and get subsetTotal Recursively chec kwhether there exists a subset with target sum. There are three base cases. 1. where subsetTotal in memo dictionary. 2. where sum is equal to zero then return true. 3. where n == len(nums)-1 and subTotal is negative value. - Store the result of recursion call where one is including and another one is not including with or operation. Time O(nm) Space O(nm) where n is the length of the nums and m is the subTotal.
202	Best Time To Buy And Sell Stock	Python	- Calculate minValue and maxProfit on each iteration and itearte through the prices array. Time O(n) Space O(1)
201	Knapsack Problem	Python	Dynamic Programming Tabulation - Create a matrix (m+1) x (n+1) to evaluldate the current maximum capacity - Iterate the matrix and if currentItemWeight is less than equal to the currentCapacity, then append eother maximum of currentItemValue + matrix[i][currentCapacity-currentItemWeight] or right above value into the current matrix. Otherwise, append above value. Finally return the sequence of the indices that creating the currentMamimumCapacity. Time O(nm) space O(nm) where n is the length of the items and m is the capacity.
200	Longest Common Subsequence	Python	Dynamic Programming Tabulation(Bottom-up) Time O(nm) Space O(nm)
199	Course Schedule II	Python	Topological Algorithm with DFS Topological algorithm determines the ordering we should enroll in classes s.t. we never enroll courses which we do not have prerequisites for. Top algorithm is an ordering of the nodes in a directed graph where for each directed edge node A to node B, node A appears before node B in ordering. Note that top ordering are not unique list and directed graph containing a cycle cannot have top order. Therefore, Directed Acyclic Graph(DAG) is the only graph that can have top order. - Use color(1,2,3) to indicate current state and create stack structure to store topological orderings. Time O(v+e) Space O(v+e) where v is the number of vertex and e is the number of edges.
198	Course Schedule	Python	1. Graph Traversal Backtracking - Create a graph structure and adopt an adjacency list structure from the given course list. - Enumerate each node(course) in the constructed graph, to check if we could form a dependency cycle starting from the node. - Start checking the cycle via backtracking, where we breadcrumbs our path to detect visitied node. Also at the end of the each interation, remove the mark. Time O(v^2+e) where v is the vertex(number of courses) and e is the edge(number of dependencies). 2. Postorder Depth First Search. - Add one more data structure from backtracking to check the processing node in stack. If we find a node that is in the process, we return False. Time O(v+e) Space O(v+e)
197	Median of Two Sorted Arrays	Python	Time O(logn) Space O(1) Partition these two arrays into two halfs s.t. the number of elements on each side are exactly same and every element on left side is less than equal to every element on right side but if it's odd number than left side will have one more element. Check if maxLeftX <= minRightY and maxLeftY <= minRightX than calculate the median and return based on the the odd or even number of x+y. Otherwise move the high and low position accordingly.
196	Merge Two Sorted Lists	Python	Recurisve Time O(n) Space O(n) Iterative Time O(n) Space O(1) - Create a dummy node to keep track of the head. while l1 and l2 are not None, insert the smaller value node to the mergedList. After the while loop, insert the left over either l1 or l2 list to the mergedList and return dummy.next.
195	Valid Parentheses	Python	- Create an empty stack to keep track of parens and create hashmaps for parens mapping. - Iterate each value of given string and if char is open paren, then append to the stack, else check if closing paren is matching with the open paren, otherwise return false. return True if stack is empty at the end. Time O(n) Space O(n)
194	Reverse Integer	Python	- Keep track of a symbol as -1 or 1 to multiple at the end. - Convert x value to positive if it's negative Iterate until x == 0 and extract last digit fot each iteration by module of 10 and result value is eqaul to result * 10 for each iteration as well. - Return the value with multiple of symbol if result is in the bound pow(2,31) otherwise return 0. Time O(n) Space O(1)
193	Longest Common Prefix	Python	Horizontal Comparison Edge case 1. when len(strs) == 0: return "" - Hold first word and iterate rest of the words one by one. - Compare the each word char by char and find the min endPoint. Return the word[0:endPoint] Time O(n) space O(1) where n is the total number of characters from given strs array.
192	Fibonacci Number	Python	1. Recursion Time O(2^n) Space O(n) 2. Memoize Recursion Time O(n) Space O(n) 3. Iterative with Sliding Window Time O(n) Space O(1)
191	Containger With Most Water	Python	The water area will always be limited by the height of the shorter line. Futher, the father the line, the more will be the water area obtained. Use two pointers, one at the beginning and one at the end. Calculate the water area and keep track of the most water area. Move shorter height line toward other end by one step Time O(n) Space O(1)
190	Longest Palindromic Substring	Python	1. Longest Common Substring -> fails e.g. s=abdgfdcba 2. Bruth Force, Time O(n^3) Space O(1) Dyanmic Programming Time O(n^2) Space O(1) - Check two conditions 1. s[i-1] and s[i+1] 2. s[i] and s[i+1] If it's palindrom, then expan both left and right to find the longest palindrome.
189	Find Leaves Of Binary Tree	Python	DFS and Hashmap Key point here is to find and mark the height of each node. Use DFS to traverse the node and keep track of the currentHeight When we reach the base case, calculate currentHeight and store as follow hashmap{currentHeight: [node.val]}
188	Car Fleet	Python	- Create a data array of tuple to hole position and speed with the same index position - Sort that array based on the position in descending order because the cars are not allowed to pass a car in front. So we will start looking at the car positioned at the closest to the target. - If the arrival time to the target conflict with the previous car, than it's combined as one fleet. So if it's not conflict, then we will count the number of fleet. In order to do that, keep track of the previousFinishTime. If previousFinishTime is smaller than currentFinishTime than update the previousFinishTime and increment fleet. It means that a car behind couldn't catch up the car in front, so it's arrived seperately. Time O(nlogn) Space O(n)
187	Letter Combinations of a Phone Number	Python	Recursive Backgracking with Hashmap - Base case, i.e. to terminate the recursion is when len(currentString) == len(digits) - Get the letters that the current digit maps to, and loop through them Add the letter to our currentString, move on to the next digit, and backtrack by removing the letter before moving onto the next. Time O(4^n * n) Space O(n) where n is the legth of digits.
186	Minimum Number of Vertices to Reach All Nodes	Python	Track of all the vertices from which we start traversing, and if we found vertex which is already in result set and reached by other vertex then we will remove it from result set because vertex and all the vertices that can be reached from that vertex can also be reached from other vertex. Time O(n) Space O(n) n is number of the edges.
185	Swap Nodes in Pairs	Python	Recursive Backgrack - Base case, i.e. the moment to terminate the recursion is when head or head.next is pointing to Null. - Store nodes to be swapped and swap then return the new head Time O(n) Space O(n) Iterative soltuion, we swpa the node as we go through the nodes. Time O(n) Space O(1)
184	All Paths From Source To Target	Python	Directed Acyclic Graph(DAG) backgrack - Baes case, i.e. the moment to terminate the recursion is when currNode == len(graph)-1 Iterate all neighbor nodes and mark the choice by appending the nieghbor node to the path on each iteration. - Then invoke backgrack() recursive function to explore deeper. Time O(2^n * n) Space O(2^n * n)
183	My Calendar I	Python	1. Binary Search Tree structure - Find the correct index of the interval - Make sure that the left and right intervals don't intersect Time O(logn) Space O(h)
182	Zigzag Conversion	Python	- 1. Read Zigzag row. Base condition: if numRow is less than equal to 1, return original string - Increment the pointer to find the correct position to append - First and last row has one jump, in other words, it has one element to append - All the other rows in between first and last have two elements to append - Increment value can be calculated by (numRows - 1) * 2 - Increment value in between first and last can be calculated by (increment + currentPosition - (2 * currentRow)) -> and make sure to check the bounds 2. Create an empty string array with the number of rows and read each char in s and append to corresponding index. Time O(n) Space O(n)
181	Shortest Diatnace To Target Color	Python	1. Burth-Force - Iterate queries enumerate(i, color) - Call getShortestDistance function to iterate leftSubarray and rightSubarray to calculate shortest distance to the color, if there is no color than return -1, or return the shortest distance index - append the shortest distance index 2. Hashmap with Binary Search - Create hashMap {color: [index]} - Iterate queries and get the shortest distance - Find the color and call binary search to find the index where can insert number - Calculate the shortestDistance on current, left, and right
180	Alphabet Board Path	Python	1. Hashmap and an array - Create a hashmap where alphabet as a key and (r,c) position as a value with loop - iterate char in given target string - Call movePositionAndUpdateString function where take currentIndex and targetIndex as arguments - Calculate movements(ups, lefts, rights, downs) and add the number of "U","L","R","D" char * movements - append "!" at the end return that string - Add the returned string to the result
179	Maximum Binary Tree	Python	- No duplicates, if there is a duplicate, we can use the first occured value since the array is not sorted but ask to the interviewer for the confirmation of their thoughts - Find index of the maximum value in nums array - Create a new node to insert with the max value from the array - Slice the nums into leftSubarray and rightSubarray The first largest number is the root node where we start [3,2,1,6,0,5] ------p---- [0,5] right ---p [0] left -p- [3,2,1] left -p--- [2,1] right -p-- [1] right -p-
178	High Five	Python	1. Hashmap with Array - create hashmap to store id as a key and scores as value of an array. - Sort each array of the scores in descending order Store result in an array with id and average of the top five scores. Time O(nlogn) Space O(n)
177	Quick Sort	Python	- Pick a pivot number on left, right, or random. - Iterate rest of the array and sort numbers with respect to the pivot value. Time Worst O(n^2) when every iteration keeps dividing subarrays one with largest and antoher slide is smallest. Time Best O(nlogn) When every iteration divides subarray exactly half. Average Time O(nlogn) Space O(logn) In the recursion, it requires to apply the Quick Sort technicque first on the smallest of the two subarrays.
176	Employee Free Time	Python	- Sort the intervals by starting time - Merge the busy overlapping time(same as a merge interval question) - Find differences between merged[i-1].end and merge[i].start for every employees to have common free time.
175	Meeting Rooms II	Python	1. Hashmap key as the meeting room and value as an array of intervals. Time O(n + w * logn) Space O(n) where n is the legnth of the intervals and w is the number of min meeting rooms 2. Optimal Checking how many meetings begin before the earliest ended meeting ends. For example, if 3 meetings have started before the earliest possible meeting end, than we need 3 rooms. Sorting helps in two things. - Find what's the earliest meeting ends time - It allows you to start looking for meetings ends only from next element in the ends array when you find some meeting start that is after the current end, because all other meeting ends before the current in the sorted array will also be before the current meeting start. So you just have to run 1 time over each array. Time O(nlogn) Space O(n) where n is the length of the intervals.
174	Minimum Difference Between Largest and Smallest Value in Three Moves	Python	- First sort the given nums - Let's say k is the number of moves that we can do - And for this specific question, the k is 4 for 3 moves(0, 1, 2, 3) - If the len of nums is <= k(4) then we can return 0 - We have 4 plans 1. nums[-4] - nums[0] -> remove 3 smallest 2. nums[-3] - nums[1] -> remove 2 smallest and 1 largest 3. nums[-2] - nums[2] -> remove 1 smallest and 2 largest 4. nums[-1] - nums[3] -> remove 3 largest
173	Logger Rate Limiter	Python	1. One Hashmap (Simpler but disadvantage of managing growing memory 2. Two Hashmap can manage the memory usage latest is last time that cacheNew is created(and first log inserted at the same time). We don't insert message into cacheOld. - All of the messages in cacheOld have older timestamp than latest. - All of the messages in cacheNew have newer timestamp than latest, but older timestamp than latest + 10. We compare the current timestamp with latest, - If timestamp >= lastest + 20, then all messages in both cacheNew and cacheOld have older timestamp than timestamp - 10, we can clean them all. - If timestamp >= latest + 10, then all messages in cacheOld have older timestamp than timestamp - 10, we can clean messages in cacheOld. - Otherwise, we need to check if either cacheNew or cacheOld contains the message.
172	Integer To Roman	Python	Greedy with Hashmap The roman numeral is consisted with largest possible symbols, working from the left. Therefore, we use a greedy algorithm to choose the best possible decision at the current time; in this case taking out the largest possible symbol at each iteration. - Create a hashmap as {index:[romanChar, value]} - While the num is not equal to 0, subtract the largest roman value possible and append the roman character to the final result string. Time O(1) Space O(1)
171	Roman To Integer	Python	Hashmap Left-To-Right Pass - Create a hashmap for the roman to integer value. - Two condition either current roman character is a special character with a consist of two characters or a one roman character. Time O(1) Space O(1)
170	Longest Substring Without Repeating Characters	Python	Use hashmap to store each character as a key and its index to a value as a pair. Also, we will keep track of the longestLengthOfSubstring and currentStartingIndex. Enumerate the given string and store the current character and the index to the hashmap. If we detect a repeated character, then we will update currentStartingIndex with either maximum of a index from the detected character from hashmap + 1 or currentStartingIndex. The reason why we update the currentStartingIndex is because we want to start a new count at a point where doesn't have a repeated character. However, in order to know what's our maximum length for a result, on each iteration we need to update the the longestLengthOfSubstring with a maximum of either longestLengthOfSubstring or currentIndex - currentStartingIndex + 1.
169	Number of Islands	Python	Iterative DFS with queue structure - This method directly mutate grid to mark for visiting - If mutation is not allowed, create a new matrix to check the visiting Time O(n * m) Space O(n * m)
168	Build Array From Permutation	Python	- Create an array with None value with the length if nums array - Iterate value in nums and assign the value by using ans[i] = nums[nums[i]]
167	Binary Search Tree To Greater Sum Tree	Python	Time O(n) Space O(h)
166	Range Sum of BST	Python	Iterative DFS Time O(n) Space O(n)
165	Sum of Nodes With Even-valued Grandparent	Python	1. DFS Iterative and add grandchild value 2. DFS iterative, check parent and add currNode value 3. DFS recurisve
164	Find Corresponding Node Of Binary Tree in Clone of That Tree	Python	Find and store the target node from original And find the node from cloned
163	Deepest Leaves Sum	Python	1. DFS inorder traversal, stack and iteratively Time O(v+e) Space O(d) 2. BFS, queue and iteratively
162	Flipping an Image	Python	1. bruth force and two pointers - swap the value at each row(reverse row) - invert 0 to 1 and 1 to 0 Time O(nm) Space O(1)
161	Reverse String	Python	1. Recursion Time O(n) Space O(n) 2. Two pointers Time O(n) Space O(1)
160	Reverse Prefix Of Word	Python	1. Pointer - Iterate word with enumerate and find the index of given ch. - Reverse word by slicing and return the result.
159	Minimize Maximum Pair Sum in Array	Python	1. Sort and two pointers Time O(nlogn) Space O(1)
158	Dot Product of Two Sparse Vectors	Python	Spare Vector is a vector that has mostly zero values, while a dense vector is a vector where most of the elements are non-zero. It's ineifficient to store a sparese vector as a one-dimentioanl array. Instead, we can store the non-zero values and their corresponding indices in a dictionary, with the index being the key.
157	Print Immutable Linked List in Reverse	Python	1. Recursion Time O(n) Space O(n) 2. Divide and conquer Time O(nlogn) Space O(logn) 3. Two pointers, print from the back Time O(n^2) Space O(1)
156	Peak Index in a Mountain Array	Python	1. Bruth force Time O(n) space O(1) 2. Binary search Time O(logn) Space O(1)
155	The K Weakest Rows in a Matrix	Python	1. Linear searching and sorting - Calculate Strengths and store in a tuple of strength and index. - Sort the tuple and return the indices. Time O(nm) + O(mlogm) = O(m * (n + logm)) Space O(m) 2. Binary searching and sorting/map - Find the number of 1s with binary search and same process from the above. Time O(m * (n + logm)) Space O(m)
154	Count Negative Numbers in a Sorted Matrix	Python	1. Bruth Force. - Count all the negatives and return the count. Time O(nm) Space O(1) 2. Take advantage of the fact that it's sorted in non-increasing order. - Staircase. Start from left bottom and count the negatives. Time O(nm) Space O(1)
153	Find Smallest Common Element in All Rows	Python	1. Bruth-Force Hashmap 2. Binary Search
152	Intersection of Three Sorted Arrays	Python	1. Binary Search Time O(nlogn) Space O(logn) 2. Bruth-Force HashMap Time O(n) Space O(n) 3. Three Pointers Time O(n) Space O(1)
151	Remove Kth Node From End	Python	- Create 2 pointers, first and second. - Move second pointer to kth times - And move both of pointers until second is pointing to None - Now remove the node where first pointer is pointing to Time O(n) Space O(1).
150	Valid Starting City	Python	Greedy Algorithm: Time O(n) Space O(1) - Keep track of minGas and minCity. - Calculate milesLeft on each city and returns the city where has a minimum milesLeft.
149	Task Assignment	Python	Greedy Algorthim: Time O(nlogn) Space O(n) - Create a dictionary with an array as a value holding indicies. - Sort the given tasks and iterate k times
148	Minimum Passes Of Matrix	Python	Find positive value index - From that index, find and update neighbors where has negative values. - Keep those updated neighbors for the next queue to update. Time O(w * h) SpaceO(w * h)
147	Disk Stacking	Python	Dyanmic Programming: Time O(n^2) Space O(n) - Sort the disks by height and keep track of the tallest heights on each index - Use two for-in loop to find stackable disks and store the heights and sequences.
146	Reverse Linked List	Python	Create 3 pointers. prev, curr, and next. Time O(n) Space O(1)
145	Remove Islands	Python	Iterate the edges of the matrix and mark all of the connected 1s by converting it to the 2 - Iterate the entire matrix and change left 1s to the 0 and 2s to the 1 Time O(wh) Space O(wh) width and height.
144	First Non-Repeating Character	Python	- Create a frequency table for each char in string. - And iterate string index and compare to the frequency table. - If the frequency value is equal to 1, return the current index. Time O(n) Space O(1) Space is constant because lowercase English alphabet letters are constant.
143	Selection Sort	Python	Divide into two sections into sorted and unsorted. - Find the smallestIndex and at the end of each iteration, swap the value to the left. Time O(n^2) Space O(1)
142	Insertion Sort	Python	Time O(n^2) Space O(1)
141	Bubble Sort	Python	- i, j pointer moves together until j < len(array) - i - Check if there is a change happended each loop, if not, break and return. Time O(n^2) Space O(1).
140	Youngest Common Ancestor	Python	- Given two descendatns have different level in the tree - In order to find the common ancestor, we need to make those two decendants at the same level. - Calculate both of depth in the tree and move lower decendant to the same level of higher decendant. - Now, two decendants are at the same level. - Move both of decendants until they are pointing to the same node.
139	River Sizes	Python	- Create an array to hold the result sizes - Copy the matrix and assign initial value of False to mark if we visited or not - Use two for loops - If visited, then continue, otherwise call traverseNode function - Use BFS and queue to traverse the adjacent nodes - Check if current position's status is true or not, if yes, continue, if not then set the current position's visit status True - getUnvisitiedNeighbors and append those neighbors to the queue - If currentRiverSize > 0, then append that into the result sizes array.
138	Breath-first Search	Python	Time O(v + e) Space O(v) Use a queue data structure.
137	Single Cycle Check	Python	- Handle the index that exceed the len(array) - Handle a negative index While we're iterating the array, if we come back to the starting index, we know it fails the condition. Time O(n) Space O(1)
136	Kadane's Algorithm	Python	Dynamic Programming Kadane's algorithm is used to find the maxmimum adjacent sum in the given integer array including negative values. Time O(n) Space O(1) - Keep track of two variables, currentMaxEnding and maxSoFar.
135	Levenshtein Distance	Python	Dynaimc Programming Solution 1 - Create two dimentional array size of (n+1) * (m+1) to keep track of the minimum editions. Time O(nm) Space O(nm) where n is the length of str1 and m is the length of the str2 Optimal Solution - Create only two smaller length of rows to keep track the minimum editions. Time O(nm) Space O(min(n, m)).
134	Min Number Of Coins For Chnage	Python	Dynaimc Programming - Create an array with Nth number filled with float("inf") in Python and set array[0] = 0. - Each array position represetns the minimum number of ways to make the given change and we will build it with each iteration of denoms. Time O(nd) where n is the given target amount and d is the number of elements in denoms array. Space O(n).
133	Number Of Ways To Make Change	Python	Dynamic Programming - Create an array with Nth number filled with 0 and set array[0] = 1 - Each array position represents the number of ways to make the change and we will build with each iteration of denoms. If denom <= ways: then ways[amount] += ways[amount - denom] Time O(nd) where n is the given target amount and d is the number of elements in denoms array. Space O(n).
132	Max Subset Sum No Adjacent	Python	Dynamic Programming solution 1. Using a new array space solution Time O(n) Space O(n) 2. Using two temp variables first, second to keep track of current sum. - Optimal Solution Time O(n) Space O(1).
131	Invert Binary Tree	Python	1. Breath First Search (Iterative Solution) Time O(n) Space O(n) 2. Recursive Solution - Time O(n) where n is the number of the nodes in the tree - Space O(d) where d is the depth of the tree.
130	Min Height BST	Python	Either write a function by using given insert method -> Time O(nlogn) Space O(n) Or write a function manually constrcuting the min height bst with given sorted array consisting of distinct integers -> Time O(n) Space O(n).
129	BST Traversal	Python	Use recursion to create inOrderTraverse, preOrderTraverse, and postOrderTraverse. Time O(n) and Space O(n) where n is the number of the nodes in the BST.
128	Validate BST	Python	Use recursion, divide and conquer algorithm. Find out if each subtree is valid BST. Time O(n) and Space O(d) where n is the number of the nodes and d is the depth of the tree.
127	BST Construction	Python	insert, contains, and remove methods
126	Merge Overlapping Intervals	Python	- Sort the array based on the startInterval in the given intervals array - Create a mergedIntervals array to store the result, and append the first interval from the sorted intervals - Iterate range from 1 to end of the array - - Get the currentStartInterval and previousEndInterval value - - If currentStart is less than or equal to the previousEndInterval - - - True, update the mergedIntervals's last interval's endInterval to max value of sortedInterval end or mergedIntervals end - - - False, append the sortedIntervals to mergedIntervals - return mergedIntervals as the result
125	First Duplicate Value	Python	1. HashMap Time O(n) Space O(n) - Create a hashmap to store the value that we found and mark it. - Iterate the array and check if the value exist in our hashmap. 2. Array Munipulation Time O(n) SpaceO(1) - Since the given prompt indicates that an array of integers between 1 and n, inclusive, where n is the length of the array and we can mutate the given array, we can use this method. - Iterate array and create seenIndex by abs(value) - 1 to mark by negative value the found value on that index. - If the value from seenIndex is negative, return that abs(value).
124	Array Of Products	Python	- Create a new array with value 1 on each position - Use for-in loop to store a current leftRunningProduct value into the new array products - Use another for-in loop to multiple the current products[i] with a current rightRunningProduct value into products array. - Return products array as the result.
123	Longest Peak	Python	- Start from index 1 and check if current position is a peak - If it's a peak then calculate left and right length to find currentPeakLength - Update the longestPeakLength if currentPeakLength is greater - Update index to right pointer.
122	Spiral Traverse	Python	Time O(n) and Space O(n) where n is the total number of the two dimential array elements.
121	Monotonic Array	Python	1. check if len(array) <= 2, then return true. 2. get first direction by array[1] - array[0]. 3. loop through the array from range 2. 4. check if the direction is meaningful(if direction == 0, then update the direction by array[i] - array[i-1]. 5. check if current direction is broken from previous direction then return False. Otherwise return True.
120	Move Element To End	Python	1. Use left and right pointers. 2. While left < right 3. while left < right and left value is not toMove value update the left and while left < right and array[right] is equal to toMove value, update the right pointer. Swap the values.
119	Smallest Difference	Python	Use two pointers to compare the difference. Keep track of smallest and current differences. Loop while any of them doesn't exceed their array index. Keep track of a current difference and check if smallest > current than, update the smallest variable.
118	Permutations	Python	Time O(n!n) Space O(n!) Building permutation takes n! time and space complexisity. If we think about building a set of permutations where the n is 3, at our first position we have the n number of cases. For next position we take away 1. Now we have n-1: 2 number of cases. Finally we take away 1 more and we have 1 number of cases left. For the time complxisty at each iteration we also have a copy operation, which take another n time complexisty. - We will call a recursion function named constructPerms with nums, current perm, len(nums), and result array permutations. - When the current permutation's length is equal to the length of the given nums array, we want to append the permutation into the final array. - Iterate the nums array in the recursion and append the current number into the current perm and build a new number array with the left side and right side of the numbers from current given number, and call the recursion function with the new number array. At each end of the iteration of recursion, we want to make sure to pop the perm so that it doesn't carry previous numbers.
117	Palindrome Check	Python	1. Create two pointers, one on the left and one on the right. 2. While left < right: check if the char is the same or not. If it's not same, return False. Otherwise, increment both of the pointers.
116	Find Three Laregest Numbers	Python	Time: O(n) and Space: O(1) Set a result array with 3 given array values and sort it. and iterate rest of the array and swap the values depends on large numbers.
115	Binary Search	Python	Use 3 pointers, left, right, mid. 1. left = 0 2. right = len(array) - 1 3. mid = (left + right) // 2 Iterate the sorted array and find the target with 3 pointers.
114	Nth Fibonacci	Python	Create a temp array to hold two values, lastTwo = [0,1]. And update the value. lastTwo[1] = lastTwo[0] + lastTwo[1] lastTwo[0] = lastTwo[1]
113	Remove Duplicates From Linked List	Python	Start from the head and check if nextDistinctNode.value is not none and equal to currentNode.value, if yes, then keep move the nextDistinctNode to next and finally move currentNode pointer to the nextDistinctNode to remove duplicates until we reach the end of the sorted singly linked list.
112	Tandem Bicycle	Python	1. Sort the speeds based on fastest value 2. iterate through speeds array and add up the max speeds
111	Class Photo	Python	1. Sort the array in reverse order 2. Find the group where has tallest student and place that color student group to back row 3. Compare each value in the array if back row students are strictly greater than front row students
110	Minimum Waiting Time	Python	1. Sort the array 2. Create two variables waitingTime, minimumTotal 3. Iterate array - 4. MinimumTotal += waitingTime - 5. WaitingTime += n
109	Merge Overlapping Intervals	Swift	1. Sort by start time 2. Create an empty mergedIntervals for result 3. Create currentInterval variable 4. Insert first interval into the result array 5. Loop the intervals. - 6. Get currentIntervalEnd, nextIntervalStart and nextIntervalEnd - 7. If overlapping -> get the max from currentEnd & nextEnd and update existing merged result array. - 8. if not overlapping -> assign nextInterval to currentInterval and append the updated currentInterval to the result array
108	Three Number Sum	Swift	1. Sort given array 2. Create an empty triplets array 3. for pivot in 0..<array.count-2 - 4. Create two pointers, left and right. Left = pivot + 1, right = array.count - 1 - 5. while left < right -- 6. Sum up 3 numbers and move the pointer accordingly depends on the comparison.
107	Minimum Characters For Words	Swift	O(n * I) time, O(c) space- where n is the number of words, I is the length of the longest word, and c is the number of unique characters across all words.
106	Height Balanced Binary Tree	Swift	Recursively calculate the left and right subtree heights from each node. determine if the subtree rooted at that node is balanced. If you make it through the entire tree without finding any unbalanced subtrees, and if you determine that the heights of the main two subtrees aren't more than 1 apart, then the entire tree is balanced.
105	Non-Constrcutible Change	Swift	Create a variable to store the amount of change that you can curerntly create up to. Sort all of your coins, and loop through them in ascending order. At every iteration, compare the current coin to the maount of change that you can currently create up to.
104	Tournament Winner	Swift	1. Create a map [String: Int] 2. Loop each competitions and increase winner's point at the map 3. Return the highest score of the team
103	Sorted Squared Array	Swift	2 methods are available and the optimal solution. 1. Create array with the same length of the given array 2. Create pointers for left, right and index 3. Loop while left <= right. - Fill the array from the back with larger number. - Move the pointer and index accordingly
102	Validate Subsequence	Swift	1.Set sequence index = 0 and final index = sequence.count 2. Increment index - If sequence == array -> increment both - If sequence != array -> increment array only 3. If sequence index == sequence.count -> true Time O(N), Space O(1)
101	Two Number Sum	Swift	1. HashMap. Time: O(n), Sapce: O(n) 2. Sort and search with two pointers O(n) and O(1) space