Data Structures and Algorithms

There's an increasing concern about me being too weak with DSA problems. I'm trying to overcome that by trying out some DSA.

Arrays and Hashing

Problem	Approach	Remarks
Valid Anagram	Obvious approach is to use HashMap to count the occurrences of characters. Another simpler but expensive operation is to sort the strings and check if they are equal
Group Anagrams	I tried by Sorting the strings and using them as a key to the HashMap, and then combining all the values together. A better approach is to use a HashTable, and the occurrences marked on the array joined into a string is used as the HashMap key. So a key for string abbc would be 1,2,1,0,0,0....
Top K Frequent Element	I was on the right track by first counting the numbers, then making a table with the indices being the count and the value being the List of numbers matching the count. Then just reading the table in reverse till K is reached.	I really struggled with Arrays and Lists in C#
Rotate Array K times	Solution was not obvious to me at all. First reverse the whole array. Then reverse from 0 - (k - 1) Then reverse from k - (n - 1)	Doing it in place is the hardest! Other solutions are easy
Move Zeroes	Two pointers: l will iterate over elements one by one, r will find the next non-zero number. if a[l] = 0 and a[r] != 0, and r > l, swap. else move the r once. All elements between l and r will be zeroes. Iterate till one pointer reaches the end.
Police and Thieves	Keep a pointer for police, keep a pointer for thieves. Find the closest police index. Find the closest thief index. Check if the difference in absolute <= k -> caught, move both pointers. If not and police is less -> find next police else find next theif	I did it by copying it to two arrays and then comparing.
Find the Union	Two pointers on both arrays and move. The trick is that aside from comparing a[i] == b[i] we should also compare the last element in the union array with a[i] and b[i]. Also, copy the remaining items in the array.
Single Element	XOR the whole array
Longest Subarray with Sum K	The prefix sum is calculated and stored in hashmap, with value as the index. If k == prefixSum -> maxLength = max(maxLength, i + 1) otherwise, check if (prefixSum - k) exists in hashmap -> if yes, then hashMap[prefixSum - k] is k. maxLength = max(maxLength, hashMap[prefixSum - k]) if (hashMap[prefixSum] does not exist) -> add it to hashmap (why check? because we need the longest subarray, and overwriting it would give us a shorter one) -> happens with zeroes and negatives.	https://www.youtube.com/watch?v=frf7qxiN2qU Can understand only by dry run
Dutch Flag/Sort Colors	2 approaches: Count the number of occurrences of each color, overwrite the array -> Called bucket sort. Approach 2: Keep two pointers left and right. Start another pointer i from left till i > right. When nums[i] = 0, swap with left. Increment both iand left. When nums[i] = 2, swap with right, but only decrement right. don't change i because we could've swapped with i with 0, and there is a 1 on the left of i. In next iteration, 0 will get swapped to left.	First approach is easy to come up with and I figured it out. Second was a bit more harder
Majority Element	Approach 1: Use a hashmap to count, when count = n/2 Approach 2: Moore's Voting Algorithm > Single Pass Moore's Algorithm
Majority Element 2	Moore's Voting Algorithm with verification. Keep two counts and two majority elements. At most, only two elements will be in result. Then use the voting algorithm. If num is in majorityCandidates, increment counters. If not decrement counters. If one counter is 0, replace it with a new candidate.
Maximum Subarray	Kadane's Algorithm
Stock Buy and Sell	Go from 0 to N, find the lowest price on the way, and find the price[i] - currentLowest. If it is higher than maxProfit, update
Rearrange the array in alternating positive and negative items	Set p = 0, n = 1 Go from 0 - N, if num[i] is positive, place it in res[p], increment p += 2; Else place it in res[n] and move n += 2.	I thought of the other way around. I placed the p and n on the actual input array, and tried to find the next positive and negative on each iteration.
Generate all permutations	1. Keep an array of bools. Recursively add each element at each place, and then remove it back. 2. Recursively swap each element with another element	https://youtu.be/YK78FU5Ffjw?si=xYREhnkHuvGhzRV https://youtu.be/f2ic2Rsc9pU?si=SThfc2gGbxqXo1Rn
Next Permutation	1. Start from last, go backwards till there is a dip (nums[i] < nums[i+1]). Store i in pivot 2. If pivot > -1, find the smallest element that is > nums[pivot] at the farthest position (meaning, nums[pivot] < nums[j] && nums[j] <= nums[currentMinimumIndex]). Swap the pivot with the index of the minimum element. 3. Reverse the right portion of the array	I would never come up with this solution on my own... https://youtu.be/JDOXKqF60RQ?si=HsOnMMnOuR3wXGa\_
Longest Consecutive Sequence	Need to imagine it on a number line. Convert nums to a hashSet. For each num in hashSet, check if num - 1 exists. If it does, try to check how many consecutive numbers exist by adding 1, and update the counter.	There is some other version with a HashMap, that stores the number of left and right of a number that seems much better.
Set Matrix Zeroes	Use the first row and first column and an additional variable to denote what rows to set zero to. Then, set the first row and first column to zero if any of the other elements in their row or column is zero. Iterate over the elements except first row and first column and set them to zero. Separately iterate over the first row and first column and set them to zero	https://www.geeksforgeeks.org/dsa/set-matrix-rows-and-columns-to-zeroes/
Rotate Image	The trick is to know that 90 degree rotation is done by Transpose and then Reverse. The second trick is to know how to transpose.	To transpose, only swap the elements to the right of diagonal once. i = 0 to N j=i+1 to N
Spiral Matrix	Keep a dx and dy to indicate direction of movement. Ending condition is i >= m*n. Replace the visited element with some garbage.	https://youtu.be/pLjhGbKMxL4?si=uCEUBkU9Wkx5Y-Jl
Subarrays equals K	Prefix sum + Counting method. Bit complicated. Go through summing the array. At each point, check what prefix can be removed to get k. Check if that k has occurred in prefixSums, and the count of occurrence. res += count.	https://youtu.be/fFVZt-6sgyo?si=9hmDzEURjuh4TKHz
Pascal Triangle	The most optimized solution is an $n^2$ solution. Initialize the first row in list. From second row: The first element would always be $1$. The next element would be last row's i-1 value + last row's i value. Last value will also be $1$.

Two Pointers

Problem	Approach	Remarks
Three Sum	Sort the array. Fix one element, then the problem becomes a two sum. So, foreach element, find the two sum so that sum = 0.	No need to iterate through the whole list. Iterate till the sortedNums[i] < 0.
Four Sum	Sort the array. Fix two elements, Search for Two Sum. Best complexity is $n^3$
Valid Sudoku	Easy solution: For each row and column and square, init a set and check if the element exists in set or not. Hard solution: Use a single int for each row, col and square. Use the bits to indicate if a element is seen or not.
Container with most water	Two pointers. Find area, Whichever height is smaller, move the pointer.
Trapping Rain Water	Method 1: Go from left to right, find the maxLefts. Start from right to left, find the maxRights, and calculate the amount of water at each position. Method 2: Two pointers: Left and Right. Till both meet, check if left is small or right is small. Whichever is small, calculate the water there (because the minimum height is the bottleneck), and move the pointer.

Stack

Problem	Approach	Remarks
Generate Parantheses	Backtracking: Start string with ( If open < n, then append a ( and recurse. Backtrack. If open > closed, then append a ) and recurse. Backtrack. Base case Check if open = closed = n -> append string to result.
Daily Temperatures	Push each temperature to stack with index. If a new temperature that is higher than the temperature on the top of the stack is found, then pop while a lower temperature is found and calculate the day difference with current temperature. Add this to the list
Car Fleet	Sort the values by position descendng. Calculate the eta they arrive at. If stack is empty or top of stack has a value less than eta, push to stack. return count of stack. Better way: Sort, while iterating, check if prevETA is bigger than current, then set fleet++. Return fleet.
Largest Histogram	Iterate through each element. The top of the stack should be lesser than the current element -> Push current element with startIndex = i. Else, while top of stack is greater, pop the stack and calculate the maxArea. Push the current element at the end with startIndex = index of last popped element. Calculate area for rest of the elements	https://youtu.be/zx5Sw9130L0

Binary Search

Problem	Approach	Remarks
Searching in sorted 2D Array	Binary search -> Think of the array as a 1D array.
left = 0, right = length -1. Calculate mid. The element will be at [mid/rowLength][mid % rowLength]
Koko Eating Bananas	Binary Search on timeTaken. Set l = 1, r = max(piles) Binary search: Find mid (speed). Foreach pile in piles, t = pile/speed.
time = sum(t). if time < h, we are going in the correct direction, no point in searching to right -> r = speed - 1. else, l = speed + 1. T = n log (maxPile)	This is a bit confusing, because we are not doing mid > something and mid < something. Instead, the time taken, which is calculated using mid is compared to change the search domain
Search in a Rotated Array	The idea is to figure out which part is the sorted part and whether the target is in sorted or unsorted part. At each mid, check if left part is sorted or right part is sorted. Then in the sorted part, check if the target is between mid and the sorted part's pointer (l or r). Then decide where to move it.	This problem had me screwed over comparison + equals.
Find Minimum of Rotated Array	Get mid, check which part is sorted. Check whether l has lower value or r has lower value, and move it towards there.
Time-based Key Value Store	Make a dictionary<string, List<(int, string)> Set is straight forward. Just set the (timestamp, value) pair to the dictionary. For Get, start at 0 and length of list of values of the key. Then do a binary search on indexes. If something with less or equal timestamp is found, set it to result and move the left pointer. Else, move the right pointer.	Array is always sorted because timestamp is increasing
Median of Two Sorted Array	Idea is to do binary search on the smaller array, so that we find the left half and right half. Do it till the partition is found, NOT l<=r. Also, mid is calculated by Math.Floor, not integer division.
half = len(a) + len(b). Then find how many elements of b will be part of the left half by binary search.
m -> pointer to b
j = half - m - 2 (the -2 is for index adjustment). j will be pointer to a. Partition is found when:
a[j] < b[m + 1] and b[m] < a[j+1]. If first condition is wrong, set l = m + 1. if second condition is wrong, r = m - 1. Median is min(aRight, bRight) if odd and max(aLeft, bLeft) + min(aRight, bRight) is even. Lots of gotchas: Better to think of right of both arrays as +inf, and left of both arrays as -inf.	Wont understand s- without the video: https://www.youtube.com/watch?v=q6IEA26hvXc

Sliding Window

Problem	Approach	Remarks
Longest Substring Without Repeating Characters	Keep a HashSet of char arrays. Keep l and r. Check if s[r] exists in the HashSet. While it exists, move the l pointer to right, and remove the s[l] from the HashSet. Once the loop exits (an element with same value as s[r] is removed), put back s[r]. Calculate maxLen = Max(maxLen, r - l + 1).
Longest Repeating Character Replacement	Two methods: One has $O(26n)$ time complexity. Other has $O(n)$. First one, keep two pointers. Keep the counts of the characters inside the window as we move the right pointer. charactersToReplace = windowSize - counts.Values.Max(). If this is bigger than k, move left pointer and decrease count of the character till the charactersToReplace is <=k. Second one, same as above, but instead of doing counts.Values.Max(), we keep a maxF that we will update only if some value for some character is higher than any frequency we've seen. Rest of the algorithm is the exact same. This works because we have to maximize the value of both maxF and windowSize to get the longest string.	I have no idea how the second approach works. I'm just parroting. Neetcode says the second approach is not expected in interviews. https://youtu.be/gqXU1UyA8pk?si=7WLZ6LB_xa5qAOkB
Permutation in String	Two solutions: $O(26n)$: Keep two 26-element lists. Count first strings count. Start window at (0,0). Add count of s2[r] in it's count. If r-l+1 > s1.Length, move l++. When r-l+1 == s1.Length, compare both arrays and return true if it matches. $O(n)$: Keep a matches variable. For the length of s1, count the characters of both s1 and s2 in one-go. For 26 elements, set matches += 1 if countS1[i] == countS2[i]. Then, start r at s1.Length. Check if matches == 26, then return true. Otherwise, increase or decrease (countS1[character] == countS2[character] - 1, we overshoot by one) the matches variable. Move the l variable too, and increase or decrease (countS1[character] == countS2[character] + 1, we undershot the character) the matches variable. Then even after exiting loop, return whether matches == 26.	I came up with the first solution. The whole trick of the second solution is to know how to increment or decrement the count.
Minimum Window Substring	If t is empty or bigger than s, return empty string. Count the characters in t. Then start counting characters in s. If the character is in t, then check if their counts match. If it matches -> match++ While match == countT.Keys, check if that is the smallest matching string we've seen and update. Move l++. Then remove the count of s[l] from counts. Also check if the match count has changed by checking countS[s[l - 1]] < countT[s[l - 1]] and subtract matches.	Trick is to know when to start shrinking the left -> when we have a matching string.
Sliding Window Maximum	Trick is to use a deque (LinkedList in C#). The left most element in deque will tell the largest element in the window. The second trick is to store only the indexes in the deque and not the element. Iterate through each of the element. When windowSize > k, check if the first index in deque is same as l. If yes, remove it, if not, keep it. Move l. Pop all the elements less than nums[r] in the deque, and add r to the deque. When windowSize == k, add the first element of deque to the result.

Linked Lists

Problem	Approach	Remarks
Reverse a Linked List	Like swapping, but keeping track of the previous element	I need to be careful of what I assign and what I return
Merge two sorted linked lists	Merge two while checking for lesser one. Use a dummy head at start. Once the first while loop exits, assign whichever list is not null to the tail.
Check for Cycles	Floyd's Rabbit and Turtle Algorithm
Reorder Linked List	1. Find Middle using Floyd's Rabbit and Turtle Algorithm 2. Split the list at right midpoint) start $r$ and $t$ at head) 3. Reverse right half 4. Carefully join back	I made a lot of fumbles while joining back
Remove Nth Node	Two pass - Calculate count, go $count - n$ and delete. One pass - 1. Move $n$ steps. 2. Make a dummy that points to head. Start another point from dummy, creating a window of size $n + 1$. 3. Move both pointers one by one. 4. When right pointer reaches null, the left pointer is just behind the node to remove. 5. r.next = r.next.next
Copy Linked List with Random Pointer	1. Make dictionary, create copy of nodes one by one, without any links. Dictionary key is old node and gives back new node. 2. Make the links by referring to the old list and the dictionary. Handle nulls	There is one test case which just sends in a null list.
Add two numbers	Can do the whole addition in one while loop. If l1 or l2 is not null or carry > 0, do a sum and keep on adding. Make sure to do null checks anytime l1 or l2 is accessed.
Find Duplicate	Treat the array like a linked list. Each value at each position is like a pointer to the next node. This will create a chain if there are duplicates. Use Floyd's Rabbit and Turtle Algorithm to find the start of the cycle.
LRU Cache	Dictionary<int, LinkedList> + Doubly Linked List. Recently used nodes at the end. Rarely used at head. - Keep dummy head and tails. - Use Dictionary to lookup nodes in linked list. - Remove from Dictionary when node is removed. - Store key in Node. - Make method to Insert at Tail and Remove from Head - The single node case is tricky, don't call the method blindly.	- After doing operations on links, do a runthrough to check if they actually work