My solutions to coding interview problems on LeetCode, AlgoExpert, Codewars, EPI book, Pramp, Codility and other interview preparation resources. I will be adding my solutions to this repository every day starting September 15, 2019.
Difficulty Levels solved
⚪ Easy: 50
🔵 Medium: 96
🔴 Hard: 24
⚫ Very Hard: 5
⭐ Good to review
Total: 175
Adding solutions to all problems I have already completed
- 🔵 ⭐ 5-longest-palindromic-substring.cpp
- 🔵 ⭐ 19-remove-nth-node-from-end-of-list.cpp
- ⚪ 21-merge-two-sorted-lists.cpp
- ⚪ ⭐ 101-symmetric-tree.cpp
- ⚪ 104-maximum-depth-of-binary-tree.cpp
- ⚪ 110-balanced-binary-tree.cpp
- ⚪ 118-pascals-triangle.cpp
- ⚪ ⭐ 206-reverse-linked-list.cpp
- ⚪ ⭐ 226-invert-binary-tree.cpp
- ⚪ ⭐ 572-subtree-of-another-tree.cpp
- ⚪ 617-merge-two-binary-trees.cpp
- ⚪ 917-reverse-only-letters.cpp
- ⚪ bubble-sort.cpp
- ⚪ caesar-cipher-encryptor.cpp
- 🔵 ⭐ longest-palindromic-substring.cpp
- ⚪ palindrome-check.cpp
- 🔵 remove-kth-node-from-end.cpp
- 🔴 reverse-linked-list.cpp
- 🔵 ⭐ smallest-difference.cpp
- ⚪ two-number-sum.cpp
Focus for today: Heaps/Priority Queues
Focus for today: Heaps/Priority Queues
- 🔴 ⭐ 23-merge-k-sorted-lists.cpp Hint: No need to add entire lists to heaps at first!
- 🔵 invert-binary-tree.cpp Hint: You can't invert right if you've already invert left.
- ⚪ binary-search.cpp Hint: Helper helps!
Focus for today: Heaps/Priority Queues/Mock Interview Practice
- ⚪ 796-is-rotation.cpp Hint: Don't try anything fancy! Think about how strings wrap around.
- 🔵 ⭐ 229-majority-element-ii.cpp Hint: How many elements can be in the solution if majority is defined by having
floor(n/3)elements?
- 🔴 ⭐ contiunous-median.cpp Hint: Remember to rebalance the heaps!
Focus for today: Heaps/Priority Queues, Common LeetCode questions
- ⚪ ⭐ 1-two-sum.cpp Hint: Think about what data structure to use. Don't try regular iteration!
- 🔵 ⭐ 2-add-two-numbers.cpp Hint: Recall elementary math! Also don't forget about the carry!
Focus for today: Common LeetCode questions, Heaps/Priority Queues
- ⚪ 20-valid-parentheses.cpp Hint: Compare chars instead of strings!
- ⚪ 937-reorder-data-in-log-files.cpp Hint:
find_first_ofmethod can be used to find first space in a string! - ⚪ 973-k-closest-points-to-origin.cpp Hint: Heap is your friend!
- 🔵 ⭐ bst-traversal.cpp Hint: Don't append to the array, replace it!
- 🔵 10-4-k-closest-stars.cpp Hint: Don't load everything into memory, use interators to point from beginning to end of stars list.
Focus for today: Pramp interview
- 🔵 ⭐ decode-variations.cpp Hint: Iterate backwards, don't actually create the variations.
- 🔵 busiest-time-in-mall.cpp Hint: Time stamps can be repeated! What happens at the last one?.
Focus for today: Heaps, Graphs
- 🔵 ⭐ 215-kth-largest-element-in-array.cpp Hint: Use a heap, but see if you can find a way to NOT include all elements in a heap.
- ⚪ depth-first-search.cpp Hint: Use recursion!
- 🔵 ⭐ has-single-cycle.cpp Hint: Make sure index is already corrected at the end of the for loop!
- 🔵 breadth-first-search.cpp Hint: Iterate and think about what data structure to use.
- 🔵 ⭐ river-sizes.cpp Hint: Use DFS/BFS as soon as you find a river. Keep track of already visited ones.
Focus for today: Graphs
- 🔵 200-number-of-islands.cpp Hint: Recursive DFS is much faster!
Focus for today: Graphs
- 🔵 ⭐ youngest-common-ancestor.cpp Hint: Get to the same depth!
- 🔴 ⭐ lowest-common-manager.cpp Hint: Don't forget about the edgecase where one of the reports could be the manager!
Focus for today: Graphs
- ⚪ 661-image-smoother.cpp Hint: Dont' over complicate it.
- ⚫ ⭐ rectangle-mania.cpp Hint: What do diagonals tell you? Can a datastructure give you better lookup than the
vector?
Focus for today: Arrays and Strings
- 🔵 362-design-hit-counter.cpp Hint: What data structure helps you to remove older values easily?.
- 🔵 ⭐ getting-a-different-number.cpp Hint: There are 3 ways to do it! O(N) is possible but not intuitive.
Practiced but did not have any answers completed.
Focus for today: Arrays and Strings
- 🔵 ⭐ 785-is-graph-bipartite.cpp Hint: Any neighbor of a node cannot have the same color as itself.
- 🔵 364-nested-list-weight-sum-ii.cpp Hint: Iterate through, add an integer as many times as there are levels below it.
- 🔴 word-count-engine.cpp Hint: You cannot do sorting and counting at the same time.
Focus for today: Arrays and Strings
- ⚪ 268-missing-number.cpp Hint: What was gauss's formula? Use it!
- 🔵 ⭐ 15-3sum.cpp Hint: Remember to skip the repeated ones!
- 🔵 ⭐ three-number-sum.cpp Hint: Two loops is okay.
- 🔴 ⭐ four-number-sum.cpp Hint: Can you divide this into a two sum problem with 2 loops? Only store the tuple of values AFTER you have visited the first.
- 🔴 ⭐ subarray-sort.cpp Hint: Find the smallest and largest out of order numbers. Where will you place them now?.
Focus for today: Arrays and Strings, Graphs
- 🔴 ⭐ largest-range.cpp Hint: Store everything in a data structure, and search forwards and backwards. Mark numbers you've already seen before.
60a. 🔴 ⭐ min-rewards.cpp (Naive) Hint: While going backwards, make sure to keep track of previous reward for that student! Choose the larger.
60b. 🔴 min-rewards.cpp (Peaks and Valleys) Hint: Find valleys and iterate outwards incrementing rewards as you go. Don't forget to choose the larger between the previous and the new reward!
60c. 🔴 min-rewards.cpp (Two sweep) Hint: Sweep once from either direction, increment rewards only on positive slope! Don't forget to choose the larger between the previous and the new reward!
-
🔵 ⭐ 994-rotting-oranges.cpp Hint: Use a datastructure to store depth for each newly rotten orange.
-
⚪ ⭐ 121-best-time-to-buy-and-sell-stock.cpp Hint: Store the minimum so far and keep maximum difference at every time step.
-
⚪ 88-merge-sorted-array.cpp Hint: Do the merge step from mergesort from the back!.
-
⚪ 283-move-zeroes.cpp Hint: Use the fast/slow pointer approach! Keep track of where the last non-zero element was seen.
-
🔵 ⭐ 11-container-with-most-water.cpp Hint: Traverse from both ends.
Focus for today: Arrays, Pramp interview
- 🔴 ⭐ zigzag-traverse.cpp Hint: Pay attention to the conditions when you need to NOT go diagonally. Keep track of the direction.
Focus for today: Arrays
- 🔵 59-spiral-matrix-ii.cpp Hint: Keep track of beggining and ending indices of rows and columns as you rotate around the matrix. Increment or decrement as you finish any row or column.`
- 🔵 54-spiral-matrix.cpp Hint: Keep track of beggining and ending indices of rows and columns as you rotate around the matrix. Increment or decrement as you finish any row or column. Have you violated the constraints while inside the loop?`
Focus for today: Arrays
- 🔵 ⭐ 161-one-edit-distance.cpp Hint: Iterate over both and keep account of differences.
Focus for today: Arrays
- 🔵 48-rotate-image.cpp Hint: Keep track of row and column limits and go around in a circle. Make the circle smaller once all are done.
Skipped, other priorities for the day.
Focus for today: Dynamic Programming
-
🔵 ⭐ maximum-subset-sum-with-no-adjacent-elements.cpp Hint: Iterate looking backwards. The current max is the max of either the max at previous index, or sum of current index and the max and previous to previous index.
-
🔵 ⭐ number-of-ways-to-make-change.cpp Hint: For d in denominations, check each amount 0-n and add ways possible.
-
🔵 ⭐ min-number-of-coins-for-change.cpp Hint: Make a list from 0-n, and at each index find the min number of coins for change. Choose min of current value, and 1 + min ways to make change of the remainder after using a denomination
- ⚪ ⭐ 53-maximum-subarray.cpp Hint: Maximum subarray at i is max of current number or sum of previous max and current number.
Focus for today: Dynamic Programming, Mock interview
-
🔵 ⭐ 91-decode-ways.cpp Hint: Iterate backwards and count number of ways to decode if you combine two adjacent characters. Add up to index 0 and that's your answer.
-
⚪ 561-array-partition-i.cpp Hint: What does sorting tell you?
-
⚪ ⭐ 7-reverse-integer.cpp Hint: Remember that current digit comes from modulo operator. How do you check whether your current answer has overflowed, either in positive or negative directions?
Focus for today: Dynamic Programming, Mock interview
- 🔵 ⭐ 322-coin-change.cpp Hint: Make a list from 0-n, and at each index find the min number of coins for change. Choose min of current value, and 1 + min ways to make change of the remainder after using a denomination.
- 🔵 levenshtein-distance.cpp Hint: Remember to consider empty spaces at the beginning of strings. Initialize the first row and column. If current character in str1 is not equal to that in str2, add 1 to min of surrounding three. Else, copy the diagonal value as if the new character did not exist.
Focus for today: Graphs and review
-
🔴 ⭐ topological-sort.cpp Hint: Do recursive DFS and add each node after all of its pre-requisites are already in the list. To deal with cycles, keep track of nodes that are currently in the DFS stack.
-
🔵 ⭐ kadanes-algorithm.cpp Hint: Maximum subarray at i is max of current number or sum of previous max and current number.
-
⚪ 541-reverse-string-ii.cpp Hint: Swap from
0-k, then jump to index2k. -
⚫ ⭐ 1192-critical-connections-in-a-network.cpp Hint: (Tarjan's) Do DFS, and convert undirected edges to directed in the order of DFS. Keep track of node ids and lowest id traversable from a node. Bridge occurs when id of current node is less than lowest node that can be found by the neighbor.
-
🔵 ⭐ 207-course-schedule.cpp Hint: Topological Sort. Keep track of cycles in pre-requisites by checking if the node you're currently checking is in the stack already. Remember to visit the node AFTER visiting all its neighbors.
Focus for today: Coding challenge from a Company
Skipped. Midterm at school.
Focus for today: Dynamic Programming
-
🔴 ⭐ max-sum-increasing-subsequence.cpp Hint: At
i, iterate from0 to i-1and check what the max sum increasing subsequence up until that point is. To build array, keep track of the previous index. -
🔴 water-area.cpp Hint: At every index, find the left max pillar and the right max pillar, then calculating area at that level is easy.
- 🔴 ⭐ 42-trapping-rain-water.cpp Hint: Extension of water-area.cpp Use only one array for holding the min if left max pillar and right max pillar.
Focus for today: Dynamic Programming
- 🔴 ⭐ knapsack-problem.cpp Hint: Use a 2D array tracking maxValue possible with given items and given capacity size. Current max value is comes from either using the previous max value, or adding the current value with the max value obtained from adding the remainder into the knapsack. Build resulting array by backtracking from max value.
Skipped. Preparing for midterm.
Skipped. Preparing for midterm.
Focus for today: Dynamic Programming
- 🔴 ⭐ longest-common-subsequence.cpp Hint: Create a 3D array to keep track of common subsequences between arrays ending at each index. If current characters match, use the diagonal value and append current character to it. Else, use the longer of top or left.
-
⚪ 70-climbing-stairs.cpp Hint: To get to the current step, you can either take a single 1-step from the previous one, or a single 2-step from the previous to previous one.
-
⚪ 746-min-cost-climbing-stairs.cpp Hint: Cost of climbing to current step is sum of cost of being on this step and minimum of either the cost of coming from previous step or previous to previous step.
Focus for today: Dynamic Programming
- ⚫ ⭐ max-profit-with-k-transactions.cpp Hint: Come back to this problem! Max profit at current transaction and day is obtained by either selling the stock or by not selling the stock and keeping the previous maximum. Keep track of max profit obtained thus far for each transaction.
- 🔵 matrix-spiral-copy.cpp Hint: Keep track of left, right, top and bottom boundaries and increment/decrement them as you go along.
Focus for today: Dynamic Programming and Graphs
-
🔵 ⭐ 1042-flower-planting-with-no-adjacent.cpp Hint: Do not overthink this one! Look at neighbors and assign yourself the first color available.
-
🔵 1079-letter-tile-possibilities.cpp Hint: First create a map with character counts. Then do recursive DFS and count by removing one character at a time and one length at a time.
Focus for today: Common Google problems
-
🔵 394-decode-string.cpp Hint: Use two stacks, one for string and the other for numbers. Do the necessary things when you encounter a number, either of the brackets or just a character.
-
🔵 ⭐ 139-word-break.cpp Hint: Think of it in terms of segmentation. A string can be segmented into words from dictionary if a part of it can be segmented, and the remaining directly exists in the dictionary.
Focus for today: Common Google problems
-
🔵 ⭐ 743-network-delay-time.cpp Hint: Remember to check if the delay at any node can be updated to a smaller one!
-
⚪ 551-student-attendance-record-i.cpp Hint: Don't need one.
-
⚪ 359-logger-rate-limiter.cpp Hint: Just what it sounds like.
-
🔵 1055-shortest-way-to-form-string.cpp Hint: Use a pointer each for both strings, compare characters and move accordingly. Keep track of how many characters you skip, if you skipped all of source string, return -1.
Focus for today: Common Google problems
-
🔵 ⭐ 253-meeting-rooms-ii.cpp Hint: How can I use a min-heap for this? Use ending times in the heap to check what the earliest end time is.
-
🔵 ⭐ 221-maximal-square.cpp Hint: Brute force: When you find one, assume square starts at top-left, keep expanding diagonally and record how many levels are valid (i.e., don't have a 0). Dynamic Programming: For the current index to be part of a square, which previous conditions need to be true?
-
🔵 ⭐ 56-merge-intervals.cpp Hint: Be careful in selecting what to compare the next index in the array with!
-
🔵 ⭐ 939-minimum-area-rectangle.cpp Hint: Brute force: Create a map from string to Point and for each point, search for points in top-right and attempt to create a rectangle. If it forms, calculate its area.
-
🔵 1007-minimum-domino-rotations-for-equal-row.cpp Hint: Choose first values and iterate through the lists, first checking how many rotations would be needed for making row A equal to
A[0]and then row B equal toA[0]. If not possible, try withB[0]. -
⚪ 867-transpose-matrix.cpp Hint: Copy from
[r][c]to[c][r].
- 🔵 ⭐ powerset.cpp Hint: Iteratively append the current element to all previously added subsets in the result.
Focus for today: Common Google problems
- ⚪ 299-bulls-and-cows.cpp Hint: You can do it without
O(N)additional space! Can you mark the already chosen ones?
Skipped, preparing for project assignment.
Skipped, preparing for project assignment.
Focus for today: Mock interview
- 🔵 281-zigzag-iterator.cpp Hint: You don't need two pointers.
Focus for today: Common questions
-
⚪ ⭐ find-largest-three-numbers.cpp Hint: Use a min-heap to keep track of largest three.
-
🔵 search-in-sorted-matrix.cpp Hint: At each iteration you can ignore either a row or column if it is not equal to target.
Skipped: Attending CalHacks
Skipped: Attending CalHacks
Skipped: Attending CalHacks
-
🔵 ⭐ 240-search-a-2d-matrix-ii.cpp Hint: Which corner do you want to start at? A corner that tells you more about which row or column you can ignore.
-
🔵 74-search-a-2d-matrix.cpp Hint: Find the correct row to search!
-
🔵 531-lonely-pixel-i.cpp Hint: Two passes are fine!
-
⚪ 141-linked-list-cycle.cpp Hint: Make two pointers race.
-
⚪ 198-house-robber.cpp Hint: What is the max profit at second position?
-
🔴 124-binary-tree-maximum-path-sum.cpp Hint: Keep a global max.
- 🔵 balanced-brackets.cpp Hint: What are the cases when brackets are not balanced?
-
🔵 ⭐ 79-word-search.cpp Hint: (1) Iterative: What happens if you go down the wrong path and need to reset back to the valid path? Backtracking! (2) Recursive: Don't need to worry about backtracking. How would you keep track of the path you're on?
-
🔴 308-range-sum-query-2d-mutable.cpp Hint: There is a dynamic programming way to do later.
-
⚪ 26-remove-duplicates-from-sorted-array.cpp Hint: Use two pointers and keep the slow pointer as the end of the array you return.
- 🔵 sales-path.cpp Hint: Same as finding min cost path.
- 🔵 105-construct-binary-tree-from-preorder-and-inorder-traversal.cpp Hint: Identify which nodes belong to the right and left subtree in both traversals.
Skipped, working on assignment.
- 🔵 array-of-array-products.cpp Hint: Forwards and Backwards pass.
- 🔵 ⭐ 238-product-of-array-except-self.cpp Hint: Forwards and backwards pass.
-
🔴 ⭐ find-loop.cpp Hint: Do the math! Find the relation between where you are and where the intersection is. Then move one of the pointers to the head and traverse both at the same speed.
-
🔴 shifted-binary-search.cpp Hint: Add an extra condition to choose where to perform binary search.
-
🔴 ⭐ min-number-of-jumps.cpp Hint: Keep track of
maxReachandstepsavailable to take with the given number of jumps. -
🔴 ⭐ longest-substring-without-duplication.cpp Hint: Keep last seen index of each character in an
unordered_mapand update thestartIdxwhen the current character already exists in the map.
Skipped, midterm at school.
-
🔵 ⭐ 3-longest-substring-without-repeating-characters.cpp Hint: Check for
maxLenat every index, and update thestartIdxevery time you find a character that already exists in the map. -
🔵 289-game-of-life.cpp Hint: How can you encode the transitions between states in place?
-
🔵 ⭐ 33-search-in-rotated-sorted-array.cpp Hint: If left array is not sorted, right must be sorted, and vice versa!
- 🔵 string-match.cpp Hint: How can you use hashing?
- 🔵 ⭐ 81-search-in-rotated-sorted-array-ii.cpp Hint: Think about what you should do when left index and middle index are the same value.
- 🔵 ⭐ rook_attack.cpp Hint: Two passes are fine.
-
🔵 ⭐ 841-keys-and-rooms.cpp Hint: Can you find a path to all rooms?
-
🔵 560-subarray-sum-equals-k.cpp Hint: Keep track of sums from 0 to i.
- 🔴 ⭐ max-path-sum-in-binary-tree.cpp Hint: Need to keep track of multiple things at every recursive call.
-
⚪ 953-verifying-an-alien-dictionary.cpp Hint: Store the order in a map.
-
⚪ 997-find-the-town-judge.cpp Hint: Find incoming and outgoing degrees.
-
🔵 ⭐ 277-find-the-celebrity.cpp Hint: Find a candidate and verify, else cannot be found.
- 🔵 ⭐ 261-graph-valid-tree.cpp Hint: Use union find and check for cycles when adding an edge.
-
⚪ branch-sums.cpp Hint: Read the definition of branch sum carefully.
-
🔵 group-anagrams.cpp Hint: Sort each word and then use a hashmap to add them to the same vector.
- 🔵 ⭐ permutations.cpp Hint: (1: Better) With the first number fixed, create permutations for all other numbers by swapping them. Once you're at the end of the list, you have found one permutation. (2: Worse) Take an element out of the array, create permutations of all others, and append element to each permutation.
-
🔵 ⭐ 22-generate-parentheses.cpp Hint: Recursively add either '(' or ')' depending on which one is available. Add to the result once the length of current permutation hits 2*n.
-
⚪ 14-longest-common-prefix.cpp Hint: Compare until not equal.
-
🔵 49-group-anagrams.cpp Hint: Sort each word and use a hashmap to add them to the same vector.
-
🔵 ⭐ 17-letter-combinations-of-a-phone-number.cpp Hint: Iterative + Recursive: Iterate over all possible next characters and recursively build up the solutions. Once you reach the end of the digits string, you have found one combination.
-
⚪ 840-magic-squares-in-grid.cpp Hint: What should sum of each row and column be equal to?
-
⚪ product-sum.cpp Hint: How do you handle the level?
-
⚪ find-closest-in-bst.cpp Hint: Can you do it both recursively and iteratively?
- 🔵 ⭐ 159-longest-substring-with-two-distinct-chars.cpp Hint: Find a way to not have to clear the entire map when map size becomes greater than 2.
- 🔵 find-the-duplicates.cpp Hint: Make use of the sorted nature.
- 🔵 move-element-to-end.cpp Hint: Use two pointers.
- 🔵 ⭐ 98-validate-binary-search-tree.cpp Hint: What are the limits for each BST nodes' values?
- 🔵 ⭐ validate-bst.cpp Hint: Make sure you keep track of the limits of the BST nodes' values.
- 🔵 681-next-closest-time.cpp Hint: Simulate time forwarding.
- 🔵 ⭐ 904-fruit-into-baskets.cpp Hint: Similar to longest substring with 2 distinct elements.
- 🔵 ⭐ 399-evaluate-division.cpp Hint: What datastructure can be best used to describe this problem?
-
⚫ ⭐ knuth-morris-pratt-algorithm.cpp Hint: Build the pattern for the substring first, then start comparing. During comparison, instead of going back to the front of the string at failure, go to the previously found pattern that matches.
-
🔴 ⭐ quick-sort.cpp Hint: Choose a pivot and move smaller elements to its left and larger to its right.
- 🔵 ⭐ 286-walls-and-gates.cpp Hint: Multi-start BFS.
- ⚪ 100-same-tree.cpp
- 🔵 ⭐ 323-number-of-connected-components-in-undirected-graph.cpp Hint: Use Union-Find, and make sure to combine parents of parents in a component as well.
- 🔵 ⭐ 1102-path-with-maximum-minimum-value.cpp Hint: Can a path finding algorithm work?
- 🔵 ⭐ 1135-connecting-cities-with-minimum-cost.cpp Hint: Use Union-Find.
- 🔵 ⭐ 983-minimum-cost-for-tickets.cpp Hint: What should you iterate over?
- ⚫ ⭐ 297-serialize-and-deserialize-binary-tree.cpp Hint: What order traversal would you use to serialize?
- 🔴 ⭐ palindrome-partitioning-min-cuts.cpp Hint: (1): For all substrings check if it is a palindrome. Then iterate over the string to develop dp logic.
- 🔵 ⭐ 46-permutations.cpp Hint: For each element in the array, swap it to the front and permute the rest. Then prepend it back.
- 🔴 132-palindrome-partitioning.cpp Hint: For all substrings check if it is a palindrome. Then iterate over the string to develop dp logic.
- ⚪ ⭐ 136-single-number.cpp Hint: Can you just use math? Can you go even lower to bit manipulation?