C++ solutions for the leetcode problem list https://seanprashad.com/leetcode-patterns and some other good problems.
-
Prefix search using a Trie, collect all words with matching prefix using BFS (Queue), search for suffix individually. Need to store index and the final word in TrieNode for matching suffix.
-
Make paired Trie, each node represents 2 letters one from the word one from reversed word, TrieNode.children[a][b] tranitions to next node. Search by jumping to [i][j] th child where i, j are characters of prefix and reversed suffix in sync. Then BFS to collect all candidates.
- Standard problem, for each cell look at max height to the left and the right. The min of those would be height of cell + water, subtract height of cell. Sum over all cells.
- Let k = (n + m) / 2 + 1, the median is the last or avg of last 2 values of the first k elements of the merged list.
- Partition one of the arrays at i, s.t. first i elements of this array and j = k - i elements of other array are the smallest k elements if the lists were merged.
- This is same as choosing the maximum i s.t. A[i - 1] <= B[k - i]. This can be done via binary search.
- Solution Video.
- Maintain a min-heap and max-heap s.t. all elements in min-heap >= all elements in max-heap.
- Maintain 0 <= len(min-heap) - len(max-heap) <= 1
- Both will have almost same elements so computing median is trivial.
- While adding new element x, if it's smaller than max heap's top, then pop max heap and push x. Now x = max(max_heap.top(), x).
- If both have same size, add x to min heap.
- If min heap has more elements, push x in min heap, pop min_heap() and push the value in max_heap() to maintain equal size.
- Make a heap of ListNode* with custom comparator.
- Keep popping from heap and if next node is present, push it in the heap. -> O(n log(k))
- Problem is equivalent to 2 people walking from top left to bottom right.
- x1 + y1 = x2 + y2 always => we can use a 3D DP with states (x1, y1, x2).
- Count cherry only once if they both land at same place.
- Make sure all answers are being memoized (the -1 case when path is invalid).
- DFS on the tree, return the max sum including the root and one side. Calculate the sum of both sides within the function and track using global max.
- Make Trie from words and then DFS.
- User BFS / DFS.
- 1D DP: dp[i] = length of LIS including i'th element is arr[:i]. -> O(n^2)
- There is a O(nlog(n)) solution explained here.
- Use Union Find with path compression, if any neighbors are encountered, union them. Count the max size of a connected set. -> O(N * alpha(N)) (Not sure of compexity, need to confirm).
- As in the leetcode dicussion, just walk each streak. Make a set from the array and count the max length of streak we can get starting from each element. If i-1 is in set for an elemnent i, dont count from i. -> O(n)
- For all the below methods : if using heap / set, work with tuple<int, int, int> of (value, row, column).
- Add all elements to heap and pop k times -> O(n^2 + klog(n)) = O(n^2)
- Maintain size of heap at k by adding and popping min element after each add. -> O(n^2)
- For a value x, write countLessThan(x) which return number of elements less than x. It can be done in nlog(n) time by just binary search inside every row. Then binary search the value of x for which function returns countLessThan(x) = k. -> O(nlog(n)log(range(matrix)))
- Use BFS. If there is a set S of possible elements for m'th position and let x_m be the m'th smallest element, the possible elements for m+1'th position would lie in (S \ {x_m}) U (Neighbors of x_m). Iterate until k, for each position pop the min element from a heap, update the frontier set. -> O(klog(k))
- Just use recursive merge sort for O(log(n)) space. Use iterative for O(1).
- Use DFS to check islands and increment the counter.
- Reverse from left node, keep a counter for number of reversals. special case when left = 1.
- Count the elements and replace.
- Keep track of farthest reachable index from current index. Iterate as far as reachable. If last index is reachable, return true.
- Use Trie to store dictionary. BFS to search.
- Build a DP from bottom up. amount = 0 takes 0 coins, for all amounts, iterate over all coins and add them once. Skip if the current amount is unreachable. Sorting the coins may give slight speedup.
- Straightforward if concept is known. Playlist for understanding Tries
- Basic dfs is accepted, there is decent speedup with memoization. The optimal solution uses subset sum and should be studied here.
- For n > 0, there will always be an opening bracket left most. If the expression inside the leftmost bracket and its complement has i pairs, there'll the n-i-1 pairs outside. Just use recursion to find these sets and take product.
-
Use hashmap of pointers to nodes.
-
For O(1) space, mark visited on input.
-
If input is non mutable, then use 2 pointers to find intersection, then move the slow pointer and a new pointer from head together, they'll meet at start of cycle.
-
When the fast and slow pointers meet, the slow pointer has movec m steps = length of cycle.
-
Just use 2 dimensional DP. Keep track of carry.
- Simple DFS / Backtracking algorithm.
- Can save space by marking visited notes inplace using special char instead of maintaing a boolean 2d array.
- Transpose then Flip in place.
- Can do it in almost half the operations by replacing values in circular order.
- Push all in a heap (priority_queue) and pop k elements. Note the details of overloading the comparator.
- Kadane's Algorithm.
dp[i] = (i % 2) + dp[i / 2];
- Iteratively reverse direction of each 'arrow'.
- Recursively swap left and right subtrees.
- Simple recursion. Solve subproblems for both child trees.
- Use hash table (unordered_set in C++).
- Use property of XOR.
- Find the nth fibonacci number.
- Make a Trie and add all the words and the string made till that word too. Perform dfs for the longest string under any TrieNode with all isWord values being true. Call dfs(root).
- Use property of XOR.
- Easy recursion. Edge case of NULL root node.
- Binary Search
- Binary Search