AlgoExpert Easy Flashcards
Two Number Sum
Run Time
O(n^2) time and O(1) space
Pattern
- Create a hashtable
- Loop through array, finding the complement of the target
- If target in hashtable, return it
- Add it to hashtable
Validate Subsequence
Run Time
O(n) time and O(1) space
Pattern
- Have two indexes
- Loop through the index while less than both their lengths
- If they match, then add seqIndx
- Return true if the seqIndx is the length of sequence, where we know it has traversed the entire array
Sorted Squared Array
Run Time
O(n) time and O(1) space
Pattern
- Create an 0s array, and left and right idx at beg and end.
- Use reversed(range(len(arr))) to compare and append the largest ab() value.
- Decrement based on left or right and update in 0s array.
Tournament Winner
Run Time
O(n) time and O(k) space
Pattern
- Invert the results list, and start with an obj of currently best team = 0
- Loop through the array of comps
- get loser and winner
- compare the results, and select winner.
Find Closest Value in BST
Run Time
O(n) time and O(n) space
Pattern
- Uses a helper function with the closest heuristic
- The base case returns the closest
- Finds closeset by taking the abs(target-tree.value) < abs(target-closet)
- Returns left or right or closest based upon closest
Branch Sums
Run Time
O(n) time and O(k) space
Pattern
- Main function creates list and calls helper function with list and runningSum
- Recursive call in helper.
- If node is none return nothing, else add the value
- If there is no left node or right node, append runningSum to the array
- Traverse left and right
Node Depths
Run Time
O(n) time and O(k) space
Pattern
- Get a sumOfDepth and a stack with root node and depth obj
- Pop obj and assign to node and depth
- Check if node is empty, if so continue
- add depth to sums and then add left node and right node to stack
Depth First Search
Run Time
O(n) time and O(k) space
Pattern
- Append the node value to array
- DFS on all children node
- returns the array
Minimum Waiting Time
Run Time
O(nlogn) time and O(1) space
Pattern
- Since its best to have shorter queue times go first, sort the queue and create total wait time
- Enumerate the queue
- calculate queries left by minus len(queries) to (idx+1) (this is to incremenet from currIdx)
- get the totalWaitTime by mult duration with queries left
Remove Duplicates From Linked List
Run Time
O(n) time and O(1) space
Pattern
- set a pointer to current node
- Loop and set a pointer to next distinct node
- Loop #2 forward if current node and next distinct node values are equal
- Set the current pointer’s next to next disctint node
- Move pointer
Nth Fibonacci
(Dynamic Programming)
Run Time
O(n) time and O(1) space
Pattern
- Save the known answers 0, 1 into a list, and set a counter variable to 3
- Loop while counter is less than Nth
- next fib = list ele 1 + list ele 2
- replace ele 1 with ele 2
- replace ele 2 with next fib
- increment counter
- return ele 2 if Nth is bigger than 1 else return 0
Product Sum
Run Time
O(n) time and O(d) space
Pattern
- Recursive approach, add depth parameter = 1
- Set each depth’s sum to 0
- loop through element in array:
- If it is a list, recursive call with depth + 1 and add to sum
- else add number to sum
- return sum * depth
Binary Search
Run Time
O(log(n)) time and O(1) space
Pattern
- Set left = 0 and right = len(list) -1
- Loop while left ≤ right:
- Set mid as left + right // 2
- if the target is mid return it
- else if target is bigger than set left to mid + 1
- else set right to mid - 1
- return -1 if you cant find the results
Find Three Largest Number
Run Time
O(n) time and O(1) space
Pattern
- Create an array with three Nones, and loop through nums in array
- Check if num is none or is bigger than largest
- If not check second largest, and then third
- If it larger, update the item at the idx and shifting all other number left by one. (or this idx = value at next idx)
- Best sorting algos are (nlogn)
Palindrome Check
Run Time
O(n) time, O(1) space
Pattern
- Using sliding window, set left idx at beginning arr, and set a right idx at the end of the arr.
- Loop while left idx < right idx:
- if str[left] ≠ str[right], return false
- increment left, decrement right
- return True if everything passes
Caesar Cipher Encryptor
(Shifting existing char in alphabet)
Run Time
O(n) time, O(n) space
Pattern
- Create a new list, newKey that is moded by 26, so it returns within the range of 26, and a list(alphabet)
- loop through each of the char in string, find the index, add new key, and mode it again.
- Add the new char into the list
- return the list with .join method
Run-Length Encoding
(AAAAAAAAAAAAaB → 9A1A1B)
Run Time
O(n) time, O(n) space
Pattern
- Create a return list, and a current char count = 1
- loop from the 2nd idx to end
- compare the curr idx and prev idx or if the curr char count == 9. If so append them to the list.
- increment the currCharCount
- handle the last run, because the prev char technique cant compare the last run
aGenerate Document
(If random string makes document, return True)
Run Time
O(n+m) time, O(c) space
Pattern
- Create a hashTable, and include all of the chars within the random string
- Loop through all the char in document string
- If it doesn’t exist or that the count for char in the hashTable is 0, return False
- Decrement the count at char in hashTable
- Return True
First Non-Repeating Character
Run Time
O(n) time, O(1) space
Pattern
- Put all of the characters into a hashtable
- Loop through the hashtable, return the first idx that has a value of 1
Non-Constructible Change
Run Time
O(nlogn) time, O(1) space
Pattern
- Sort the coins and set a change variable to 0.
- Loop through coins:
- As long as current coin cannot make the sum of the previous change + 1, this means that we have skipped one of the sums.
- We compare if current coin is larger than current change + 1, if yes return change + 1
- Increment change with coin
- return change + 1 (because there is some coin later that we cannot change)
