Coding Challenges Collection

Solutions to coding challenges and algorithm and data structure building blocks

Data Structures

Linked List
Queue
Dequeue
MinHeap
Union Find
Binary Search Tree
- BST Node
- BST Utils
Trie
- Prefix Trie

Nodes

Singly Node - use to implement Linked List
Doubly Node - use to implement a Queue
Graph Node - use in Graph problems
BST Node - use in Binary Search Tree problems
Tree Node - use in Tree problems

LeetCode

TOC

Coding Challenges Collection

1 - Two Sum

problem
solution
@xiaoyunyang/1-two-sum">repl
O(N) solution using one pass hash table storing the index of the complement number Complement is defined as target - nums[i].

3 - Longest Substring Without Repeating Characters

problem
solution
@xiaoyunyang/3-longest-substring-without-repeating-characters">repl
O(N) solution using dynamic programming (kadane’s algorithm). Keep track of the last time you saw the character in a hash table.

20 - Valid Parentheses

problem
solution
@xiaoyunyang/20-valid-parentheses">repl
O(N) solution using a stack to make sure every type of open bracket is immediately followed by a close bracket of the same type.

39 - Combination Sum

problem
solution
@xiaoyunyang/39-combination-sum">repl
O(N^T) solution using recursive backtracking.

40 - Combination Sum II

problem
solution
@xiaoyunyang/40-combination-sum-ii">repl
O(N^T) solution using recursive backtracking.

41 - First Missing Positive

problem
solution
@xiaoyunyang/leetcode-first-missing-positive">repl
hash table, O(N) solution

42 - Trapping Rain Water

problem
solution
@xiaoyunyang/leetcode-trapping-rain-water">repl
while-loop, two pointers, O(N) solution

43 - Multiply Strings

problem
solution
@xiaoyunyang/leetcode-multiply-strings">repl
nested for-loops, O(N^2) solution

129 - Sum Root to Leaf Numbers

problem
solution
@xiaoyunyang/129-sum-root-to-leaf-numbers">repl
O(Log N) solution via tree traversal

135 - Candy

problem
solution
@xiaoyunyang/135-candy">repl
O(N) Solution using Greedy algorithm. Evaluate left2right and right2left, then combine solution via max of the two.

146 - LRU Cache

problem
solution
@xiaoyunyang/146-lru-cache">repl

300 - Longest Increasing Subsequence

problem
solution
@xiaoyunyang/300-longest-increasing-subsequence">repl
O(N^2) solution using LIS dynamic programming or O(N logN) solution greedy algorithm.

347 - Top K Frequent Elements

problem
solution
@xiaoyunyang/347-top-k-frequent-elements">repl
O(N log N) Solution by creating a frequency table.

452 - Minimum Number of Arrows to Burst Balloons

problem
solution
@xiaoyunyang/452-minimum-number-of-arrows-to-burst-balloons">repl

594 - Longest Harmonious Subsequence

problem
solution
@xiaoyunyang/594-longest-harmonious-subsequence">repl
O(N) Solution by creating a frequency table and updating a global maximum subsequence length in the loop.

690 - Employee Importance

problem
solution
@xiaoyunyang/690-employee-importance">repl
O(V*E) Solution by first creating a hash table for easy indexing of nodes in a graph, then traverse that graph via BFS.

721 - Accounts Merge

problem
solution
@xiaoyunyang/721-accounts-merge">repl
Solution using graph search. emails are the vertices. create bi-directional edges from first email to every other email of each account

820 - Short Encoding of Words

problem
solution
@xiaoyunyang/leetcode-short-encoding-of-words">repl
whiteboarding
Solution using trie of the reversed strings

945 - Minimum Increments to Make Array Unique

problem
solution
@xiaoyunyang/945-minimum-increments-to-make-array-unique">repl
O(N logN) solution using greedy algorithm.

953 - Verifying An Alien Dictionary

problem
solution
@xiaoyunyang/953-verifying-an-alien-dictionary">repl
O(N) solution using hash map to translate from alien alphabet to normal alphabet, then do a simple comparison in a loop to verify ascending order.

1138 - Alphabet Board Path

problem
solution
@xiaoyunyang/1138-alphabet-board-path">repl
Solution by solving a system of equations

1276 - Number of Burgers With No Waste Of Ingredients

problem
solution
@xiaoyunyang/1276-number-of-burgers-with-no-waste-of-ingredients">repl
whiteboarding
Solution by solving a system of equations

1386 - Cinema Seat Allocation

problem
solution
@xiaoyunyang/1386-cinema-seat-allocation">repl
O(N) solution using bitmask, where N is the number of reserved seats.

1464 - Maximum Product of Two Elements in an Array

problem
solution
@xiaoyunyang/1464-maximum-product-of-two-elements-in-an-array">repl
O(NlogN) solution by sorting the array.

1465 - Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

problem
solution
@xiaoyunyang/1465-maximum-area-a-piece-of-cake">repl
O(N+M) solution by keeping track of the maximum gaps made by the horizontal and vertical cuts. Then multiple these max gaps.

1470 - Shuffle the Array

problem
solution
@xiaoyunyang/1470-shuffle-the-array">repl
O(N) solution by merging two arrays.

1471 - The k Strongest Values in an Array

problem
solution
@xiaoyunyang/1471-the-k-strongest-values-in-an-array">repl
O(N logN) solution by pre-sorting the array and using a while-loop and two pointers.

1472 - Design Browser History

problem
solution
@xiaoyunyang/1472-design-browser-history">repl
Solution using a stack and a pointer for supporting forward operations.

Leetcode 2020 04 Challenge

136 - Single Number

problem
solution
@xiaoyunyang/136-single-number">repl
O(N) solution and O(N) space using a set. O(N) solution and O(1) space using XOR and reduce.

202 - Happy Number

problem
solution
@xiaoyunyang/202-happy-number">repl
O(N) solution and O(N) space using a set for cycle detection.

53 - Maximum Subarray

problem
solution
@xiaoyunyang/53-maximum-subarray">repl
O(N) solution using Kadane’s Algorithm (DP)

283 - Move Zeroes

problem
solution
@xiaoyunyang/283-move-zeroes">repl
O(N) solution using a while-loop and two pointers

122 - Best Time to Buy and Sell Stock II

problem
solution
@xiaoyunyang/122-best-time-to-buy-and-sell-stocks-ii">repl
O(N) solution by adding to result if current price is greater than previous price.

Leetcode 2020 05 Challenge

278 - First Bad Version

problem
solution
@xiaoyunyang/278-first-bad-version">repl
O(logN) solution using binary search.

771 - Jewels And Stones

problem
solution
@xiaoyunyang/771-jewels-and-stones">repl
O(N) solution using a Set.

383 - Ransom Note

problem
solution
@xiaoyunyang/383-ransom-note">repl
O(N) solution by repeated updates to array. Faster than frequency table.

476 - Number Complement

problem
solution
@xiaoyunyang/476-number-complement">repl
O(k) Solution using while loop and xor to toggle bits. k is the most significant bit that’s a one.

387 - First Unique Character

problem
solution
@xiaoyunyang/387-first-unique-character">repl
O(N) solution using JS built-in array methods indexOf and lastIndexOf to find if char is unique. Use Set to store the duplicates.

169 - Majority Element

problem
solution
@xiaoyunyang/169-majority-element">repl
O(N) and constant space solution using Boyer-Moore majority vote algorithm.

993 - Cousins in Binary Tree

problem
solution
@xiaoyunyang/993-cousins-in-binary-tree">repl
O(logN) solution via 2 tree traversals.

1232 - Check If It Is a Straight Line

problem
solution
@xiaoyunyang/993-cousins-in-binary-tree">repl
O(N) solution via comparison with a reference slope.

367 - Valid Perfect Square

problem
solution
@xiaoyunyang/367-valid-perfect-square">repl
O(log N) solution using binary search. Conditional guard return true if input is 0 and 1.

997 - Find the Town Judge

problem
solution
@xiaoyunyang/997-find-the-town-judge">repl
O(N) solution using an easier version of union-find disjoint set

733 - Flood Fill

problem
solution
@xiaoyunyang/733-flood-fill">repl
O(N+M) Solution using BFS and DFS

540 - Single Element in a Sorted Array

problem
solution
@xiaoyunyang/540-single-element-in-a-sorted-array">repl
O(logN) solution using binary search

402 - Remove K-Digit

problem
solution
@xiaoyunyang/402-remove-k-digits">repl
O(N * K) solution using greedy algorithm.

208 - Implement Trie (Prefix Tree)

problem
solution
@xiaoyunyang/208-implement-trie-prefix-tree">repl
Each node is an object with key being the letter and value being a node or end boolean, marking where that this is the end of a word.

918 - Maximum Sum Circular Subarray

problem
solution
@xiaoyunyang/918-maximum-sum-circular-subarray">repl
O(N) solution using Kadane’s algorithm to find Min subarray and max subarray.

328 - Odd Even Linked List

problem
solution
@xiaoyunyang/328-odd-even-linked-list">repl
O(N) solution using by maintaining a pointer to the end of the odd list and the beginning of the even list.

438 - Find All Anagrams in a String

problem
solution
@xiaoyunyang/438-find-all-anagrams-in-a-string">repl
O(N) solution using the sliding window technique to update a 26-length array to keep track of the character frequency.

567 - Permutation In String

problem
solution
@xiaoyunyang/567-permutation-in-string">repl
O(N) solution using the sliding window technique to update a 26-length array to keep track of the character frequency.

901 - Online Stock Span

problem
solution
@xiaoyunyang/901-online-stock-span">repl
O(N) solution using two stacks to keep track of the prices and the previous results of next. The top of the prices stack is always the minimum price seen so far.

94 - Kth Smallest Element in a BST

problem
solution
@xiaoyunyang/230-kth-smallest-element-in-a-bst">repl
O(logN) solution using In-order Traversal.

1277 - Count Square Submatrices with All Ones

problem
solution
@xiaoyunyang/1277-count-square-submatrices-with-all-ones">repl
O(N * M) solution using dynamic programming. Create a sum matrix to keep track of number of ones seen in a row from top, left, and left diagonal

451 - Sort Characters By Frequency

problem
solution
@xiaoyunyang/451-sort-characters-by-frequency">repl
O(N) solution using hash table

986 - Interval List Intersections

problem
solution
@xiaoyunyang/986-interval-list-intersections">repl
O(N) solution one while loop and two pointers

1008 - Construct Binary Search Tree from Preorder Traversal

problem
solution
@xiaoyunyang/1008-construct-binary-search-tree-from-preorder-traversal">repl
O(N) solution by recursively building the sub-tree if the sub-tree falls within a range.

1035 - Uncrossed Lines

problem
solution
@xiaoyunyang/1035-uncrossed-lines">repl
O(A * B) solution using dynamic programming. Create a sub-problem solution matrix to keep track of the max uncrossed lines for the sub-arrays. The sub-problem is whether to include the current two items from A and B in the solution or not.

525 - Contiguous Array

problem
solution
@xiaoyunyang/525-contiguous-array">repl
O(N) dynamic programming solution using a variation of Kadane’s algorithm and a hash table.

886 - Possible Bipartition

problem
solution
@xiaoyunyang/886-possible-bipartition">repl
O(N) solution using BFS and node coloring technique

338 - Counting Bits

problem
solution
@xiaoyunyang/338-counting-bits">repl
O(N) solution using dynamic programming

207 - Course Schedule

problem
solution
@xiaoyunyang/207-course-schedule">repl
O(N) solution using DFS cycle detection

973 - K Closest Points to Origin

problem
solution
@xiaoyunyang/973-k-closest-points-to-origin">repl
O(N) solution by sorting the input array

973 - K Closest Points to Origin

problem
solution
@xiaoyunyang/72-edit-distance">repl
O(N * M) solution using dynamic programming

Leetcode 2020 06 Challenge

520 - Detect Capital

problem
solution
@xiaoyunyang/520-detect-capital">repl
Solution by finding all the capital letters in the word

237 - Delete Node in a Linked List

problem
solution
O(1) Solution

1029 - Two City Costs

problem
solution
@xiaoyunyang/leetcode-1029-two-city-scheduling">repl
whiteboarding
Solution using a while loop with two pointers to go through a sorted list of cost difference between the cities

344 - Reverse String

problem
solution
O(N) solution using two pointers and a while loop to swap front and back elements of the array.

528 - Random Pick with Weights

problem
solution
@xiaoyunyang/528-random-pick-with-weight">repl
O(logN) solution by binary search over cumulative probability densities.

406 - Queue Reconstruction by Height

problem
solution
@xiaoyunyang/406-queue-reconstruction-by-height">repl
O(N logN) solution by pre-sorting the array by descending height and ascending K, then repeatedly update the result array.

231 - Power of Two

problem
solution
@xiaoyunyang/231-power-of-two">repl
O(logN) solution by repeatedly mod and divide the number by 2.

392 - is Subsequence

problem
solution
@xiaoyunyang/392-is-subsequence">repl
O(N) solution by traversing all the characters of the longer string once and deleting the head character of the shorter string whenever it matches a character from teh longer string.

35 - Search Insert Position

problem
solution
O(N) solution.

75 - Sort Colors

problem
solution
@xiaoyunyang/75-sort-colors">repl
Dutch national flag problem. Solution using two pointers to keep track of the boundaries of the outer colors.

380 - Insert Delete GetRandom O(1)

problem
solution
@xiaoyunyang/380-insert-delete-getrandom-o1">repl
Solution using a map and an array in the datastructure to achieve O(1) delete and getRandom, respectively.

787 - Cheapest Flight with K Stops

problem
solution
@xiaoyunyang/787-cheapest-flight-with-k-stops">repl
Solution by BFS in a graph while keeping track of distance and k

700 - Search in a Binary Tree

problem
solution
Solution by standard tree traversal

468 - Valid IP Address

problem
solution
@xiaoyunyang/468-valid-ip-address">repl
Solution by regex and many if-statements.

130 - Surrounded Regions

problem
solution
@xiaoyunyang/130-surrounded-regions">repl
Solution using BFS and a set for keeping track of Os connected to any O on the edge.

275 - H-Index II

problem
solution
@xiaoyunyang/275-h-index-ii">repl
O(logN) solution using binary search

137 - Single Number II

problem
solution
@xiaoyunyang/137-single-number-ii">repl
O(N) and constant space using bitwise operation.

Leetcode 2020 07 Challenge

441 - Arranging Coins

problem
solution
@xiaoyunyang/441-arranging-coins">repl
O(N) solution using while loop with early return.

107 - Binary Tree Level Order Traversal II

problem
solution
@xiaoyunyang/107-binary-tree-level-order-traversal-ii">repl
O(N) solution using tree traversal while incrementing level and reverse the result array in a post-processing step.

66 - Plus One

problem
solution
@xiaoyunyang/66-plus-one">repl
O(N) solution using unshift to add new digit to the front of the array and use carry. Need to have a post processing step to add the extra one to the front as necessary.

Leetcode 2020 08 Challenge

226 - Invert Binary Tree

problem
solution
O(log N) Solution. 2 recursive calls per level for logN levels.

705 - Design HashSet

problem
solution
Solution using a JS object.

125 - Valid Palindrome

problem
solution
@xiaoyunyang/125-valid-palindrome">repl
Solution two pointers and a while loop.

342 - Power of Four

problem
solution
@xiaoyunyang/342-power-of-four">repl
O(log_4 N) solution by recursively dividing the number by 4 until the number is equal to 1.

442 - Find All Duplicates in an Array

problem
solution
O(N) solution using the repeated array update strategy. As we loop, we can negate the elements at index j where j=Math.abs(nums[i])-1. This works because the constraint: 1 ≤ a[i] ≤ n (n = size of array). If anytime we detect that element at index j is negative, that means the current element is a duplicate.

Leetcode 2020 09 Challenge

949 - Largest Time for Given Digits

problem
solution
@xiaoyunyang/949-largest-time-for-given-digits">repl
Solution using one loop and process of elimination. Pro-tip: Make A lot of helper functions.

220 - Contains Duplicate III

problem
solution
@xiaoyunyang/220-contains-duplicate-iii">repl
O(N logN) solution by sorting the array first and using two pointers and one while loop.

459 - Repeated Substring Pattern

problem
solution
@xiaoyunyang/459-repeated-substring-pattern">repl
O(N ^2) solution using a sliding window

1305 - All Elements in Two Binary Search Trees

problem
solution
@xiaoyunyang/1305-all-elements-in-two-binary-search-trees">repl
Solution using two in-order traversals (time complexity O(N)) to create two sorted arrays from the BSTs, then loop through both arrays at the same time in one while-loop (time complexity O(N)) to merge the two sorted arrays, similar to the merge step of merge sort.

290 - Word Pattern

problem
solution
@xiaoyunyang/290-word-pattern">repl
O(N) solution using two hash maps.

1022 - Sum of Root To Leaf Binary Numbers

problem
solution
@xiaoyunyang/1022-sum-of-root-to-leaf-binary-numbers">repl
O(logN) solution using binary tree traversal and helper function to convert binary to a decimal number.

165 - Compare Version Numbers

problem
solution
@xiaoyunyang/165-compare-version-numbers">repl
O(N) solution using the weighted sum approach.

299 - Bulls and Cows

problem
solution
@xiaoyunyang/299-bulls-and-cows">repl
O(N) solution using one frequency table and “cancel out” the matches.

152 - Maximum Product Subarray

problem
solution
@xiaoyunyang/152-maximum-product-subarray">repl
O(N) solution using Kadane’s algorithm and tracking both minimum and maximum local solutions.

216 - Combination Sum III

problem
solution
@xiaoyunyang/216-combination-sum-iii">repl
O(10^k) solution using Backtracking (DFS).

57 - Insert Interval

problem
solution
@xiaoyunyang/57-insert-interval">repl
O(N) solution using interval covering technique.

198 - House Robber

problem
solution
@xiaoyunyang/198-house-robber">repl
O(N) solution using DP Table.

58 - Length of Last Word

problem
solution
@xiaoyunyang/58-length-of-last-word">repl
O(N) solution using basic loop and String.prototype.split method.

421 - Maximum XOR of Two Numbers in an Array

problem
solution
@xiaoyunyang/421-maximum-xor-of-two-numbers-in-an-array">repl
O(N^2) solution using two loops.

1041 - Robot Bounded in Circle

problem
solution
@xiaoyunyang/1041-robot-bounded-in-circle">repl
O(N) solution which stepping through the entire array of moves to calculate the robot’s final direction and location.

121 - Best Time to Buy and Sell Stocks

problem
solution
@xiaoyunyang/121-best-time-to-buy-and-sell-stocks">repl
O(N) solution by updating the min, max, and maxProfit as you step through the array.

1291 - Sequential Digit

problem
solution
@xiaoyunyang/1291-sequential-digit">repl
O(N) solution by setting the limits of loops to min number of digits to max number of digits.

Leetcode 2020 11 Challenge

1290 - Convert Binary Number in a Linked List to Integer

problem
solution
@xiaoyunyang/1290-convert-binary-number-in-a-linked-list-to-integer">repl
O(N) solution. Trick is to use Number.parseInt() using 2 as the radix.

1446 - Consecutive Characters

problem
solution
O(N) solution. Update a globalMax every time you loop.

1217 - Minimum Cost to Move Chips to The Same Position

problem
solution
@xiaoyunyang/1217-minimum-cost-to-move-chips-to-the-same-position">repl
O(N) solution. Keep track of the parity of each number as you loop through the array.

1283 - Find the Smallest Divisor Given a Threshold

problem
solution
@xiaoyunyang/1283-find-the-smallest-divisor-given-a-threshold">repl
O(log N) solution using binary search.

445 - Add Two Numbers II

problem
solution
O(N) solution using two stacks.

563 - Binary Tree Tilt

problem
solution
@xiaoyunyang/563-binary-tree-tilt">repl
O(logN) solution by tree traversal.

1026 - Maximum Difference Between Node and Ancestor

problem
solution
O(logN) solution by tree traversal. The solution is the max of the left subtree solution and right subtree solution.

832 - Flipping an Image

problem
solution
@xiaoyunyang/832-flipping-an-image">repl
O(N * M) solution by traversing the matrix. Use two pointers in a while loop method for optimization.

593 - Valid Square

problem
solution
@xiaoyunyang/593-valid-square">repl
Solution using the geometric property of a square: find distances between all the points and check that there exists two unique non-zero distances. Optimization using a set (cleaner code).

47 - Permutations II

problem
solution
@xiaoyunyang/47-permutations-ii">repl
Solution using recursion (dfs). Keep track of nodes we have visited. Sort the nums to make sure we skip the same value. When the current value is equal to the previous value, we only use this value if the previous is used.

116 - Populating Next Right Pointers in Each Node

problem
solution
@xiaoyunyang/116-populating-next-right-pointers-in-each-node">repl
O(N) solution using BFS. The trick is to recognize the number of nodes to at each level doubles.

845 - Longest Mountain in Array

problem
solution
@xiaoyunyang/longest-mountain-in-array">repl
O(N) solution using the range splitting method.

858 - Mirror Reflection

problem
solution
Solution using modulo to calculate ratio of p and q.

56 - Merge Intervals

problem
solution
@xiaoyunyang/56-merge-intervals">repl
O(N) solution using a stack to keep track of the previous interval

394 - Decode String

problem
solution
@xiaoyunyang/394-decode-string">repl
O(N) solution using a stack and while loops inside a for-loop.

804 - Unique Morse Code Words

problem
solution
@xiaoyunyang/804-unique-morse-code-words">repl
O(N) solution using set to keep track of unique morse code patterns.

337 - House Robber III

problem
solution
@xiaoyunyang/337-house-robber-iii">repl
O(logN) solution using tree-traversal and divide and conquer algorithm.

239 - Sliding Window Maximum

problem
solution
@xiaoyunyang/239-sliding-window-maximum">repl
O(N) solution using Dequeue. Keep track of indices in dequeue. Prune the dequeue of out of range indices and indices whose associated number is less than the current num.

1306 - Jump Game III

problem
solution
@xiaoyunyang/1306-jump-game-iii">repl
O(N) solution using DFS.

Leetcode 2020 12 Challenge

104 - Maximum Depth of Binary Tree

problem
solution
O(logN) solution using tree traversal

605 - Can Place Flowers

problem
solution
@xiaoyunyang/605-can-place-flowers">repl
O(N) solution by counting zeros and using a function to map number of zeros to number of flowers that can be planted. Alternatively, use greedy algorithm.

117 - Populating Next Right Pointers in Each Node II

problem
solution
@xiaoyunyang/117-populating-next-right-pointers-in-each-node-ii">repl
O(N) solution by keeping track of level in the queue and BFS

59 - Spiral Matrix II

problem
solution
@xiaoyunyang/59-spiral-matrix-ii">repl
O(N^2) solution using switch statements and index math.

1010 - Pairs of Songs With Total Durations Divisible by 60

problem
solution
@xiaoyunyang/1010-pairs-of-songs-with-durations-divisible-by-60">repl
O(N) solution and constant space complexity algorithm using hash table to count the frequency of the complements of each time.

941 - Valid Mountain Array

problem
solution
@xiaoyunyang/941-valid-mountain-array">repl
O(N) solution using two while loops to walk the array once from left to right in two phases.

80 - Remove Duplicates from Sorted Array II

problem
solution
@xiaoyunyang/80-remove-duplicates-from-sorted-array-ii">repl
O(N) solution using a while-loop, splice to modify the array in place, and no data-structure (taking advantage of the fact that the array of nums is sorted in ascending order).

865 - Smallest Subtree with all the Deepest Nodes

problem
solution
@xiaoyunyang/865-smallest-subtree-with-all-the-deepest-nodes">repl
O(logN) solution using tree traversal.

312 - Burst Balloons

problem
solution
@xiaoyunyang/312-burst-balloons">repl
O(N^2) solution using DP table. Each entry of the DP table stores the max coins we get from bursting bubbles between left and right.

977 - Squares of a Sorted Array

problem
solution
@xiaoyunyang/977-squares-of-a-sorted-array">repl
O(N) solution using a stack to keep track of the squares of the negative numbers and perform a merge operation similar to merge sort.

98 - Validate Binary Search Tree

problem
solution
@xiaoyunyang/98-validate-binary-search-tree">repl
O(N) solution tree traversal and composition.

334 - Increasing Triplet Subsequence

problem
solution
@xiaoyunyang/334-increasing-triplet-subsequence">repl
O(N) solution by updating first and second in a loop.

880 - Decoded String At Index

problem
solution
@xiaoyunyang/880-decoded-string-at-index">repl
O(N) and O(1) solution using index math.

110 - Balanced Binary Tree

problem
solution
@xiaoyunyang/110-balanced-binary-tree">repl
O(log N) tree traversal.

24 - Swap Nodes in Pairs

problem
solution
@xiaoyunyang/24-swap-nodes-in-pairs">repl
O(N) linked list traversal using three pointers prev, curr, and next.

Leetcode 2021 01 Challenge

1640 - Check Array Formation Through Concatenation

problem
solution
@xiaoyunyang/1640-check-array-formation-through-concatenation">repl
O(N) solution using a hash table and two pointers.

1379 - Find a Corresponding Node of a Binary Tree in a Clone of That Tree

problem
solution
O(logN) solution using tree traversal.

21 - Merge Two Sorted Lists

problem
solution
@xiaoyunyang/21-merge-two-sorted-lists">repl
O(N) solution using while-loop to only increment one list node at a time. For the interim data structure for merged list, use array instead of linked list for better space performance

88 - Merge Sorted Array

problem
solution
@xiaoyunyang/88-merge-sorted-array">repl
O(N) solution using while-loop.

2 - Add Two Numbers

problem
solution
O(N) solution using while-loop, carry, and keeping track of the tail of the result linked list.

Cracking the Coding Interview

Arrays and Strings

1.1 - isUnique

Problem: Determine if string contains unique characters. What if you cannot use additional data structures?
solution
@xiaoyunyang/CTCI-1-1-is-unique">repl
O(N) solution with hash table or O(NlogN) with sorting.

1.2 - checkPermutation
Problem: given two strings, determine if the second string is a permutation (anagram) of the first string.
solution
@xiaoyunyang/CTCI-1-2-check-permutation">repl
O(N) solution with hash table or O(NlogN) with sorting. Optimization up-front: if lengths of the strings are different, return false immediately.

1.3 - URLify
Problem: given a string, replace all the whitespaces with “%20”.
solution
@xiaoyunyang/CTCI-1-3-URLify">repl
O(N) solution. Use regex /^\s$ to test each character to see if it is a whitespace. Need to handle edge cases such as if there are mutiple whitespaces in a row or whitespaces at the end of the string.

1.4 - Palindrome Permutation
Problem: Given a string, determine if the string is a permutation of a palindrome.
solution
@xiaoyunyang/CTCI-1-4-palindrome-permutation">repl
O(N) solution using a hash table. Use str.replace(/\s/g, '') to get the string without whitespaces.

1.5 - One Away
Problem: Given s1 and s2, determine if s1 and s2 differ by one edit away. Define edit as inserting a char, deleting a char, or replacing a char.
solution
@xiaoyunyang/CTCI-1-5-one-away">repl
O(N) solution. Modularize the solution by writing helper functions.

1.6 - String Compression
Problem: Given a string with a number of characters in a row, compress the string by replacing the repeated characters with the character, followed by the number of occurrences. For example, aabcccccaaa becomes a2b1c5a3. If the compressed string would not be smaller than the original string, the function shall return the original string.
solution
@xiaoyunyang/CTCI-1-6-string-compression">repl
O(N) solution. Make sure to check edge cases. There is an optimization we could do to break from the loop operation when a condition is met.

Linked List

See JavaScript Implementations of LinkedList (also available in @xiaoyunyang/LinkedList">repl).

2.1 - Remove Dups

Problem: Remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?
solution
@xiaoyunyang/CTCI-2-1-remove-dups">repl
O(N) solution using a hash table and using the curr and prev pointers. With no buffers, we use the “runner technique” where we iterate through the linked list using curr pointer while we have another pointer called runner that goes through the rest of the list which comes after curr to check and remove any duplicates.

Stacks and Queues

See JavaScript Implementations of Queue using Doubly Linked List (also available in @xiaoyunyang/Queue">repl).

Graph

4.1 - Route Between Nodes

Problem: Given a Directed Graph, design an algorithm to find out whether there is a route between two nodes.
solution
@xiaoyunyang/CTCI-4-1-route-between-nodes">repl
We can use either BFS or DFS for this problem. BFS is more efficient. Make sure we set graph node state to UNVISITED, VISITED, VISITING as we traverse through the graph.

4.2 - Minimal Tree
Problem: Given a sorted (increasing order) array with unique elements, write an algorithm to create a Binary Search Tree (BST) with minimal height.
solution
@xiaoyunyang/CTCI-4-2-minimal-tree">repl

Math and Logic Puzzles

6.1 - The Heavy Pill

Problem: You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.
solution
@xiaoyunyang/CTCI-6-1-the-heavy-pill">repl

Moderate Problems

16.10 - Living People

Problem: Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive.
solution
@xiaoyunyang/CTCI-16-10-living-people">repl

16.20 - Phoney Words
Problem: On old cellphones,users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0 - 4 letters. Implement an algorithm to return a list of matching words, given a sequence of digits representing a phone number. You are provided a list of valid words (provided in whatever data structure you’d like).
```
1     2     3
      ABC   DEF
4     5     6
GHI   JKL   MNO
7     8     9
TUV   WXYZ  PQRS
      0
```
solution
@xiaoyunyang/CTCI-16-20-phoney-words">repl
Note: O(M * N) where M is number of valid words in the dictionary and N is the length of the phone number. Because N is a small number (phone numbers are usually length 10), we can treat this as a constant. Therefore, the runtime is O(M).

16.21 - Sum Swap
Problem: Given two arrays of integers, find a pair of values (one value from each array) that you can swap to give the two arrays the same sum
solution
@xiaoyunyang/CTCI-16-21-sum-swap">repl

Hard Problems

17.26 - Sparse Similarity

Problem: Print out the documents IDs and their similarity score iff the similarity score is greater than 0. We define similarity score as the result of dividing the number of intersections with the number of unions. For example:

Input:
```
const input = {
  13: [14, 15, 100, 9, 3],
  16: [32, 1, 9, 3, 5],
  19: [15, 29, 2, 6, 8, 7],
  24: [7, 10],
};
```
Output:
```
13,16 : 0.25
19,24 : 0.14285714285714285
13,19 : 0.1
```
solution
@xiaoyunyang/CTCI-hard-sparse-similarity">repl
My solution involves building two hash tables.

Misc

Flood Fill

Problem:

Given grid and point:

let grid = [
  // grid could be any size
  ["blue", "blue", "red", "red", "red"],
  ["pink", "pink", "red", "red", "red"],
  ["red", "pink", "green", "green", "red"],
  ["red", "red", "green", "red", "green"],
  ["red", "green", "red", "red", "red"],
];
let p = [4, 2]; // a valid location in the grid

find all the locations which has the same color as the given location return the location (indices) in ascending order. For example, given the grid and point above, you should return:

[
  [3, 3],
  [4, 2],
  [4, 3],
  [4, 4],
];

solution
@xiaoyunyang/flood-fill">repl
The key to solving this problem is you can use depth-first-search (DFS) or breadth-first-search (BFS) and maintain a list of explored nodes. I solved the problem using both DFS with recursion and BFS using queue + while loop. Both provide the same result. For printing out the list of points in ascending order, I had a separate function that sorted the result using JavaScript’s built-in sort (quicksort), which has O(NlogN) runtime. A potential optimization for the overall algorithm is to maintain the result as a heap rather than an array. Using an array, insert is O(1) as we use the Array.prototype.push method; however, the tradeoff is we need to run the O(N logN) algorithm at the end. However, if we use a min heap, inserting into a min heap is O(logN). The advantage is we don’t have to sort afterwards, rather, we extract the min from the min heap (runtime O(1)) until the heap is empty. In a min heap, the parent is guaranteed to be smaller than its children so we could recursively extract elements in increasing order from the min heap starting from the root of the heap and working our way down the children.
The recursion approach is also called the implicit stack-based approach because we are creating call stacks when we recurse. This is less memory efficient than a real stack.
For more on the flood fill problem, read the wiki article

Deserialize-1

Problem:

Given:

const locations = [
  { id: 1, name: "San Francisco Bay Area", parent_id: null },
  { id: 2, name: "San Jose", parent_id: 3 },
  { id: 3, name: "South Bay", parent_id: 1 },
  { id: 4, name: "San Francisco", parent_id: 1 },
  { id: 5, name: "Manhattan", parent_id: 6 },
  { id: 6, name: "New York", parent_id: null },
  { id: 7, name: "Menlo Park", parent_id: 1 },
  { id: 8, name: "Brooklyn", parent_id: 6 },
  { id: 9, name: "Alphabet City", parent_id: 10 },
  { id: 10, name: "East Village", parent_id: 13 },
  { id: 11, name: "Greenpoint", parent_id: 8 },
  { id: 12, name: "Williamsburg", parent_id: 8 },
  { id: 13, name: "Lower Manhattan", parent_id: 5 },
  { id: 14, name: "Soho", parent_id: 13 },
  { id: 15, name: "Financial District", parent_id: 13 },
];

Print out:

New York
-Brooklyn
--Greenpoint
--Williamsburg
-Manhattan
--Lower Manhattan
---East Village
----Alphabet City
---Financial District
---Soho
San Francisco Bay Area
-Menlo Park
-San Francisco
-South Bay
--San Jose

Rules: (1) Child locations should be immediately after their parent, with an extra dash prepended. (2) Locations of the same level of depth should be alphabetically sorted. (3) Assume that the actual list of location will be longer (up to 100 locations), and have max up to 5 levels of depth

solution
@xiaoyunyang/AngelList-coding-test">repl
My solution involves recursively building a tree where each node is a general TreeNode and nodes are inserted into an ordered array of children using a insertIntoSortedArr function.

Shuffle

Problem: Shuffle an array.
solution
@xiaoyunyang/knuth-shuffle-and-sort">repl
Note: Use the Knuth Shuffle (aka Fisher-Yates shuffle)

Sort 2D Array

Problem: Sort a 2D array of pairs. The rule is we want to sort by the first elem, then the second elem.
solution
@xiaoyunyang/knuth-shuffle-and-sort">repl
Note: Write custom compare function to pass into Array.sort.

Array

Least Frequent Array Elements

Problem: Given an array of integers, return an array containing the integer that occurs the least number of times. If there are multiple answers, return all possibilities within the resulting array sorted in ascending order. When no solution can be deduced, return an empty array.
```
Example
Input: [10, 941, 13, 13, 13, 941]
Output: [10]
```
solution
@xiaoyunyang/least-frequent-array-element">repl