LC Study Flashcards
- Word Break
to get runtime complexity, count non-leaf nodes similar to decode ways, easier tho runtime recursion brute-force: 2^n. with memo: O(n)
- Maximum Product Subarray
holy fuck… i got
- Set Matrix Zeroes
look at submission
- Find K Closest Elements
e
237 Delete Node in a Linked List
have to set the next to null, if you want to remove a node. “node = null” does not work bc “node” is just a var and doesn’t alter the actual object, ~duh~. Could have used only two lines and no loop… silly boy..
- Path Sum
DEFINITION OF ROOT-LEAF. IF THERE EXISTS ANOTHER CHILD, IT IS NOT A LEAF
- Permutation in String
e
- Task Scheduler
2 diff ways with pri queue Do the calculation way
- Combination Sum
-best way to find how to get to target
- Binary Tree Level Order Traversal
bfs
- Sort List
e
- Maximum Binary Tree
difficult
- K Closest Points to Origin
e
- The Skyline Problem
e
- House Robber II
e
- Sort Characters By Frequency
e
- Binary Search Tree Iterator
e
- Merge Intervals
interesting, reference the result array to make decisions and update, idk nothing to say
- Decode Ways
the zero case is absolute asshole not dealing with this,….. you need to have the index represent the length or you will kys aids
- Alien Dictionary
e
- Intersection of Two Arrays
e
- Fizz Buzz
e
- Reverse Nodes in k-Group
Use ‘nxt’ for next node name!
- Clone Graph
submitted: both dfs and bfs solutions
- Verifying an Alien Dictionary
e
- Concatenated Words
e
- Critical Connections in a Network
e
- Longest Substring Without Repeating Characters
sliding window try optimized version heuehuehue
- Valid Parentheses
wrong data structure, hubris thought i remembered soln, didn’t check given test cases against my soln ;/
- Linked List Cycle
Object equivalencies! use “==” and it will check if its the same object Make it nice, easier to just have more null checks than to do something fancy.
- Find the Duplicate Number
constraints are for hard question
- Subtree of Another Tree
e
101 Symmetric Tree
e
- Word Search
dfs, not looking at already used letters just have dfs go to all neighbors, and have a general check for if it is correct char or out of bounds
- Remove Duplicates from Sorted List
e
- Implement Queue using Stacks
e
- Longest Common Prefix
edge case of single element. Think of these things pls vertical scanning fastest, do it next time
- Palindrome Partitioning
2 parts: longest palindorme dp array and then backtracking with partitions
- Serialize and Deserialize Binary Tree
Do iterative, learned iterator
- Substring with Concatenation of All Words
see sliding window notes
- Target Sum
dynamic programming good problem, indexing
- Move Zeros
e
- IPO
e
- Binary Tree Maximum Path Sum
e
- Diagonal Traverse
e
- Reorder Data in Log Files
e
- Divide Two Integers
e
- Sliding Window Maximum
e
- Jump Game
simple soln
5 Longest Palindromic
rly good and hard, 2 methods, DP and expand from middle I did a shitty implementation of DP, try expand from middle Update: actually not so shitty after all, looks good for DP
- Interval List Intersections
The interval with the shortest end point for sure doesn’t have any further overlap in the array. The one with shortest start point might very well have more overlap…
- Reverse Words in a String II
e
121 Best time to buy and sell stock 1
I got it right but I needed to increment at the end. I used a roundabout whileloop way, but should use the more efficient forloop one-pass
- Queue Reconstruction by Height
insert() behavior important
- Word Ladder
e
242 Valid Anagram
sorting is actually longer than mapping to array sorting nlogn
- Kth Smallest Element in a Sorted Matrix
heap and binary search
- Flatten Nested List Iterator
didnt understand q, DO AGAIN
- Design In-Memory File System
e
- Find K Pairs with Smallest Sums
e
- Maximum Width of Binary Tree
recursive and iterative
- Range Sum of BST
e
- Search Suggestions System
e
- Minimum Height Trees
e
11 Container with Most Water
traverse width dimension
- Excel Sheet Column Number
understand the problem better
- Spiral Matrix
main learning: just check if len(res) is less than number of elements in matrix every time look at most recent submission
- Kth Largest Element in an Array
adding, removing to priorityqueue/heap/bst is lg(n) T(n) = T(n/2) + (n-1) => O(n) T(n) = T(n/2) => O(logn) (binary search) Tags: quicksort partition
- Reorganize String
e
21 Merge Sorted Lists
didn’t assume it was ordered, use recursion. sexy solution.
- Sparse Matrix Multiplication
e
- Binary Tree Zigzag Level Order Traversal
Got bfs real good, DO DFS, it’s pretty cool 4/17: EDIT: Beautiful most recent solution with deq. FINAL ITERATIVE, Next do recursive.
78 Subsets
2 neat ways of solving: Super simple and sleek python contruction second is backtracking, don’t duplicate lists.
- Reverse Words in a String
e
19 Remove Nth Node
Mine is good, look at article it shows using dummy for head which is useful soln to removing head edge case
- Counting Bits
crazy, dp soln w/ pattern detecting (overlap subproblem) and really neat dp with odd/even soln
- Sliding Window Median
e
- Implement Trie (Prefix Tree)
e
- Coin Change
KNOW RUNTIME, bottom up and top down stuff.
- Minimum Remove to Make Valid Parentheses
e
- Convert BST to Greater Tree
There is a way to transfer info back up a tree, much harder tho, try global variable solution first and then discuss that way.
Morris traversal is interesting
- Vertical Order Traversal of a Binary Tree
e
- Copy List with Random Pointer
e
- Add Two Numbers
Get the implementation completely down. added new category :)
344. Reverse String
e
217 Contains Dup
I used sorting solution. I thought would be faster because nlogn + n = nlogn, and worst case for hashtable insert (hashset) is O(n), so I thought that would be O(n^2), but solution says it is only O(1).
- Meeting Rooms
e
- Add Binary
e
- Design Tic-Tac-Toe
e
- Read N Characters Given Read4 II - Call multiple times
- Ez python way, 2. other java/c++ way with array buffer.
- Valid Palindrome II
e
- Longest Substring with At Most K Distinct Characters
DO THE FOLLOWUP IN DISCUSSIONS. UNDERSTAND OPTIMIZED! update: the ordered dictionary is for the follow-up: what if input is as a stream? ans: you need to store the leftmost character’s position… just look at soln article!
- Longest Consecutive Sequence
e
- Implement Rand10() Using Rand7()
e
172 Trailing Zeros
math
- Employee Free Time
Do K-Way Merge Idea when you get to that lesson :)
- Encode and Decode Strings
e
- sqrt()
O(sqrt(x)) solution not wrong, just make sure to check for overflow (i <= x / i) binary search solution practice (many ways to do bisearch)
- Reverse Words in a String III
e
- Valid Number
e
- Course Schedule III
e
- Maximum Frequency Stack
e
- Maximum Length of a Concatenated String with Unique Characters
e
- Unique Paths
memo, weird matrix layout, try to understand and do yourself dp iteration, look at most recent submission
- Binary Search
e
- Analyze User Website Visit Pattern
e
- Populating Next Right Pointers in Each Node II
I used solution article, keep with sachin my boi, other discussion solutions are gay as fuck
- Validate Binary Search Tree
try iteration(stack), and in-order next time too
- Diameter of Binary Tree
e
- Course Schedule
cycle detection method and topological sort ***huge revisit, lot to learn from this one. didn’t really do cycle detection one but seems fun
- Peeking Iterator
e
- Accounts Merge
e
- Letter Combinations of a Phone Number
e
- Number of Distinct Islands
e
- Shuffle an Array
another design similar to right above!! woooooooo!!!!!!! love it !!!! tyes1!!!!!!!! awassome!!!
- Day of the Week
e
- Insert Interval
dont waste time implementing a wrong algo… duh
- Palindromic Substrings
dp and expand solutions
- Minimum Path Sum
MAKE SPACE EFFICIENT sick O(n) space soln
38 Count and say
Integer.toString() takes a long time, changed it just to result.append(times) where “times” is an integer *able to append int to StringBuilder
- Random Pick Index
e
- Search Insert Position
also a handle for dups
- Validate IP Address
e
- Majority Element
quick ans
- Encode and Decode TinyURL
e
66 Plus One
cool
- Count Primes
ancient greek algorithm sieve of arasmuth cool (in hints)
- Single Number
e
- Squares of a Sorted Array
e
- Same Tree
LEARNED: DFS iteratively uses stack. BFS iteratively uses a queue submitted: most recent is BFS using queue solution, next is recursion update: the dfs w/ stack is preorder
- Unique Binary Search Trees
do dp.
- Path Sum III
insane solution, got brute recursion tho, caching solution is muy dificil
- Is Graph Bipartite?
e
- Most Common Word
e
- Number of Islands
e
- Reverse Bits
unsigned left shift doesn’t exist, does the same as <
- Snakes and Ladders
e
- Two Sum
find the edge :/ same num used twice, don’t get too confident bruh one-pass available
- Invert Binary Tree
bfs, dfs, recursive, iterative
- Binary Tree Inorder Traversal
try without altering initial data structure, I forgot to reset the node’s left to null so it infinitely looped
- Merge sorted Array
hit it from the baackkkk most recent submission the soln I like
- Decode String
like flatten nest list, kinda unique stack question, hopefully anotherone like it somewhere
- Permutations II
good, one extra step was to iterate on the counts, not the nums to not look at double.
- Populating Next Right Pointers in Each Node
DO AGAIN
- Valid Palindrome
skip completely alphanumeric, also isLetterOrDigit() try without extra space next time!
- Regular Expression Matching
e
- Exclusive Time of Functions
e
- Top K Frequent Words
e
- Random Pick with Weight
e
- Search a 2D Matrix
cool cool cool cool
- Find Minimum in Rotated Sorted Array
good to learn bisearch inside and out, so many edge cases. l < r if you want to break and return outside of loop use r = mid in order to close in on one specific target from two arrays, otherwise you lose a potential number jesus binary search is hard, keep trying and cross-comparing different q’s
- Remove Invalid Parentheses
e
- Boundary of Binary Tree
e
- Minimum Depth of Binary Tree
iterative BFS (could attach depth to node w/ a tuple. I like generalized global mindepth tho its more like level order), Try all others versions (DFS, recursive).
- LFU Cache
e
- Minimum Number of Arrows to Burst Balloons
not easy in the slightest, greedy
198 House Robber
practice the iterative version as well. Maybe take a crack at the 2 variable one
- Rotting Oranges
e
- Search in Rotated Sorted Array
two ways, 1: look if low and mid are on the same side, then do checks based on that (its either increasing from low to mid, or increasing from mid to high) 2: look at pivot to determine if mid and target are on the same side, then do checks based on that.
- Flatten Binary Tree to Linked List
some crazy ass prev shit LOOK OVER AGAIN FOR SURE
- Find Smallest Letter Greater Than Target
e
- Expression Add Operators
e
122 Buy sell stock
I remembered somehow, understand the peak-valley deal
118 Pascals Triangle
look at fucking return types, had to change whole thing
- Best Time to Buy and Sell Stock with Cooldown
state machine, iterpreting into dp code, optimizing. very good, look at generalization article too
- Remove Duplicates from Sorted Array
Good job altering from original plan to most efficient possible algo! (Beats 100%)
- Word Break II
e
- Word Search II
DO OPTIMIZATION: its in the solution code in a comment.
- Binary Tree Right Side View
DO RECURSION METHOD (reverse pre-order) I got the level order bfs queue version.
- Permutations
list concatenation is O(n). list slicing is O(n). Use hashset to be faster than checking if it exists in a list. Time complexity would be O(n!*n) with list checking. O(n!) w/ set space is O(n!) bc of res.
- Intersection of two Linked Lists
hashset soln if not find other one can have stop condition be while(nodeA != nodeB) bc they will both be null at some point
- Graph Valid Tree
e
- Find Peak Element
there are some sneaky things with bisearch that ppl solns did, mine is easy to understand but has more lines, later attempt to implement those sneaky things if you see them a lot more? also RECURSIVE VERSION
- Average of Levels in Binary Tree
Iterative BFS done. Do recursive/DFS
- Trapping Rain Water
Key Takeaway: even on LC Hard, the fundemental idea you need in order to solve the problem is not too outrageous: min(maxleft, maxright) - curheight basically, don’t think its not possible NEXT: UNDERSTAND STACK SOLUTION!!
- Game of Life
implement it
- Find All Anagrams in a String
Sliding window, plan on memorizing this shit real good
- Insert Delete GetRandom O(1)
get it or u dont, hint: -swap-
15 3Sum
super annoying implementation, needing to protect agianst dups just gross
- Group Anagrams
learned defaultdict, using tuples
- 3Sum Closest
Once find target, return immediately :)
- Peak Index in a Mountain Array
peak finding
268 Missing Number
I thought about doing the sum thing ;0 ;0 ;0 should have thought more ://
- Merge k Sorted Lists
e
191 Nubmer of 1 bits
nice
- Closest Binary Search Tree Value
e
- Reverse Integer
Negative modulus Overflow cycles hella, cant rely on just being less than or greater than previous number. must check if not equal to previous number
- Non-overlapping Intervals
I did sort by first element, best is sort by second
- Remove Linked List Elements
e
- Gas Station
e
- Integer to English Words
e
- Number of Connected Components in an Undirected Graph
e
108 Convert Sorted Array to BST
edge case len = 0
48 Rotate Image
ctci
- Add and Search Word - Data structure design
e
- Lowest Common Ancestor of a Binary Search Tree
try again, iterative too
- Reorder List
neat most recent submission
- Construct Binary Tree from Preorder and Inorder Traversal
bisearch on tree kinda Do java soln to avoid splice time creating new lists from that python guy
- Find All Duplicates in an Array
e
- Rotate List
nice
326 Power of three
smokeout
- Implement Stack using Queues
e
- Search in Rotated Sorted Array II
e
- House Robber III
GENERALLY PASS UP INFORMATION. I tried passing down info, and not good recursive practice. Try to say, given the info of node below, what do I do now? Instead of passing info about current problem down to below problem, actually its just top-down vs bottom-up. ACTUALLY IDK, KEEP A LOOK OUT FOR THIS AND COME BACK. SEE IF OPINION CHANGES
- Restore IP Addresses
e
- Course Schedule II
e
- Recover Binary Search Tree
e
- 4Sum II
pretty simple actually
- Subarray Sum Equals K
looks like sliding window, but actually presum + 2 sum very cool stuff
- LRU Cache
e
- Add Two Numbers II
e
- Max Depth of BST
e
- Prison Cells After N Days
e
234 Palindrome Linked List
really good, optimization and clean code should be attempted next time!! I like my solution the best actually, most recent submission has cleaner for-loops than first 2nd attemp soln
206 Reverse Linked List
try recursive next time,also only need 2 temps to start
- Longest Duplicate Substring
e
387 First unique character in string
I traversed wrong array for second loop…. dumb boy..
- Hamming Distance
many ways to do
- Pacific Atlantic Water Flow
try bfs, direction thing too
- Path Sum II
backtracking aspect. Really good point on BFS vs DFS here in solution article. Take note of this Time complexity
- Odd Even Linked List
got it
- Swap Nodes in Pairs
recursive soln next
- Partition Equal Subset Sum
0/1 knapsack
230 Kth Smallest Element
inorder traverse ez, python global vars n shi try iteration? DO FOLLOW-UP SIMILAR TO LRU CACHE
- Minimum Window Substring
time space linear
- String Compression
e
- Partition Labels
e
- Monotonic Array
e
- Continuous Subarray Sum
e
- Longest Repeating Character Replacement
Can get O(n) by never shrinking the window
53 Maximum Subarray
memorize algo
- All Nodes Distance K in Binary Tree
Build a graph out of the tree, then BFS. Try other solution w/o creating graph
- Implement Str()str()
only traverse haystack.length() - needle.length()+1 use i + j instead of h and use 2nd for loop for ease
- Longest Substring with At Most Two Distinct Characters
NOTE IMPORTANT****: DO OPTIMIZED SOLUTION.
- Design Search Autocomplete System
e
- Find Median from Data Stream
BST solution, list solution, 2 heaps solution
- Word Ladder II
e
202 Happy Number
Gucci (Edit months later: No. u are not gucci u idiot ahaha)
- Shortest Unsorted Continuous Subarray
hard array…
- Longest Increasing Subsequence
dp, also nlogn unnecessary tho
- Serialize and Deserialize N-ary Tree
e
- Top K Frequent Elements
ATTENTION: NOW SWITCHING TO PYTHON LOLOLOLOL bucket sort
- Linked List Cycle II
e
- Backspace String Compare
e
- Search a 2D Matrix II
implement it
- Sort Colors
3 ptr basically or 2 ptr + iteration Tags: quicksort partition
- Middle of the Linked List
e
- Subarray Product Less Than K
e
- Perfect Squares
bfs and dp, implement it
- Meeting Rooms II
e
- Next Permutation
e
- Generate Parentheses
Errors having to do both with understanding stringbuilder class: initialize with string “(“ NOT ‘(‘ Understand why deleteChar(i) after each append :) CONDENSE THAT SHIT (I like my soln, try to condense it continuing using SB, with the given solution’s if statements) most recent submission is hype
- Lowest Common Ancestor of a Binary Tree
Do iterative
- Inorder Successor in BST II
e
- Sum of Two Integers
e
- Minimum Cost to Connect Sticks
e
- Climbing Stairs
dp, fibonnaci nice
- Find All Numbers Disappeared in an Array
negation shit stupid
238 Product of Array Except Self
try in constance time follow up, not very different from linear time
350 Intersections of two arrays II
e
- Increasing Triplet Subsequence
reducing to 3’s, means using that info to reduce time. Like sorting color too.
- Maximum Swap
e
- Add Strings
e
- Missing Element in Sorted Array
e
- Reverse Linked List II
I like my soln the best, most intuitive
- Min Stack
useful prob
- Rotate Array
tried and failed miserably to do in place Reason I failed: checking if the values were equivalent rather than looking at the indexes. Soln: if reach same starting idx, just look at the next idx and go through that loop, THATs the stopping condition, when n swaps! got the extra space soln tho
- Maximum Sum of 3 Non-Overlapping Subarrays
e
- Binary Tree Level Order Traversal II
Do Recursive next
- Roman to Integer
store vals better (hash or array), add all accross and then subtract if necessary, ask if it will always be valid! then, dont need each case
- Evaluate Reverse Polish Notation
e
