study_code.md

Goal

• Pooja's list
• Arrays: Sorting
• Combination and Permutation (recursion and backtracking)
• Trees
• Graphs
• Heaps
• Union Find (disjoint sets)
• Knapsack problem

week 2 (26 Jul - 1 Aug)

• 3 Sum 2 pointer
• 3 Sum combinatorix
• Heap sort
• 4 sum https://leetcode.com/problems/4sum-ii/discuss/93917/Easy-2-lines-O(N2)-Python
• finish pojas easy list (at least 5 qns a day)
• [ ]

28 jul

• 13. Roman to Integer
• 20. Valid Parentheses
• 21. Merge Two Sorted Lists
• 141. Linked List Cycle
• 155. Min Stack
• 169. Majority Element
• 202. Happy Number
• 204. Count Primes
• 242. Valid Anagram
• 371. Sum of Two Integers

29 Jul

• Product of arrays
• Merge Sorted Array
• Convert Sorted Array to Binary Search Tree
• Rotate Array
• Isomorphic Strings
• Invert Binary Tree
• Find All Numbers Disappeared in an Array
• Subtree of Another Tree
• Reverse Words in a String III
• N-ary Tree Preorder Traversal

31 Jul

• finish all qns from past days
• 605. Can Place Flowers
• 617. Merge Two Binary Trees
• 665. Non-decreasing Array
• 669. Trim a Binary Search Tree
• 674. Longest Continuous Increasing Subsequence
• 703. Kth Largest Element in a Stream
• 705. Design HashSet
• 852. Peak Index in a Mountain Array
• 1160. Find Words That Can Be Formed by Characters

1 Aug

• String to Integer (atoi)
• Roman to Integer
• 3Sum
• Add Binary
• Integer to English Words

2 Aug

• Longest Valid Parentheses
• a way to solve is valid paranthesis inplace no extra space
• Group Anagrams

3 Aug

• finish pass days qns
• Longest Substring Without Repeating Characters
• Next Permutation
• Multiply Strings
• One Edit Distance
• Move Zeroes

4 Aug

• Valid Palindrome
• Valid Palindrome II
• Validate IP Address
• Minimum Window Substring
• Merge Two Sorted Lists
• Add Two Numbers
• Copy List with Random Pointer
• Reorder List

5 Aug

• Validate Binary Search Tree
• Flatten Binary Tree to Linked List
• Binary Tree Maximum Path Sum
• Clone Graph
• Binary Tree Right Side View

6 Aug

• Finish yst qns
• Binary Tree Right Side View
• Subsets
• N-ary Tree Level Order Traversal

7 Aug

• Palindrome Partitioning I|II
• Number of Islands
• Binary Tree Paths
• Alien Dictionary
• Diameter of Binary Tree
• Is Graph Bipartite?
• Convert Binary Search Tree to Sorted Doubly Linked List

8 Aug

• Longest Substring with At Most K Distinct Characters
• LRU Cache
• Binary Tree Vertical Order Traversal
• Read N Characters Given Read4
• Subarray Sum Equals K
• Serialize and Deserialize Binary Tree
• Remove Element

9 Aug

• Second Highest Salary (sql)

11 Aug

• String to Integer (atoi)
• Letter Combinations of a Phone Number
• Permutations
• Permutations II
• Pow(x, n)

12 Aug

• Continuous Subarray Sum
• Subarray Sums Divisible by K

14 Aug

• Squares of a Sorted Array
• Remove Invalid Parentheses
• Strobogrammatic Number II
• Merge Intervals

17 Aug

• Divide Two Integers
• Search in Rotated Sorted Array
• Find First and Last Position of Element in Sorted Array
• First Bad Version
• Shuffle an Array
• Shuffle the Array

18 Aug

• Meeting Rooms
• Meeting Rooms II
• Find the Celebrity
• Best Time to Buy and Sell Stock

19 Aug

• First Missing Positive
• Intersection of Two Arrays
• Intersection of Two Arrays II
• Find Peak Element
• LFU Cache

22 Aug

• Integer to Roman
• Insert Delete GetRandom O(1)
• Verifying an Alien Dictionary
• Maximum Subarray
• Trapping Rain Water
• Text Justification

23 Aug

• Minimum Remove to Make Valid Parentheses
• K Closest Points to Origin
• Median of Two Sorted Arrays

24 Aug

• Find Median from Data Stream
• Kth Largest Element in an Array
• Time Based Key-Value Store
• Spiral Matrix
• Design In-Memory File System
• Employee Free Time

25 Aug

• Buildings With an Ocean View
• Permutation in String
• Spiral Matrix II
• Longest Palindromic Substring
• Longest Valid Parentheses

26 Aug

• Decode Ways
• Strobogrammatic Number
• Strobogrammatic Number II
• Smallest Subtree with all the Deepest Nodes
• lowest-common-ancestor-of-deepest-leaves
• Maximum Size Subarray Sum Equals k
• Find All Anagrams in a String
• Partition Equal Subset Sum

29 Aug

• Add Strings
• Remove All Adjacent Duplicates In String
• Range Sum Query 2D - Immutable
• Word Break
• Interval List Intersections

30 Aug

• Remove Nth Node From End of List
• Edit distance
• Minimum Add to Make Parentheses Valid

31 Aug

• Kth Largest Element in an Array
• Find N Unique Integers Sum up to Zero

1 Sep

• Subsets
• Subsets II
• Permutations
• Permutations II
• Combinations
• Combination Sum II
• Combination Sum III
• Palindrome Partition
• Shuffle String
• Minimum Time Visiting All Points

week 3 (26 Jul - 1 Aug)

• trees
  • traversal
  • leetcode tree easy
  • iterative inorder traversal https://www.youtube.com/watch?v=nzmtCFNae9k
• Pojas medium list

First Bad Version

1. binary search
2. find [F,T]. if [F,F] search right. else if [T,T] search left
3. note base case, clamp at 1 and n

model soln: 2 pointers, L and R, to do binary search. process mid. if T, search left. F, search right. this narrows in on meeting point [F,T], which is the base case.

class Solution:
    def firstBadVersion(self, n):
        l = 1
        r = n
        while l < r:
            mid = (r-l) // 2 + l
            if isBadVersion(mid):
                r = mid
            else:
                l = mid + 1
        return r

Intersection of Two Arrays

1. sets or
2. sort nums 1 and nums2 asc. nums1 and nums2 as stacks, top ele same, add to ans (a set). else, pop the larger element.

Intersection of Two Arrays II
my soln: same as Intersection of Two Arrays sort approach, but use ans =[]
other soln, no sort: see hash map soln, key:num, val: count, similar to detect anagrams https://leetcode.com/problems/intersection-of-two-arrays-ii/solution/

Find Peak Element
binary search. search in direction of increasing element. https://leetcode.com/submissions/detail/541033977/
TODO: read https://leetcode.com/problems/find-peak-element/solution/

LFU Cache

1. dict for key2usecount
2. dict<usecount, OrderDict()> for usecount2orderedkv. Ordered dict stores k,v of input. ordered dict is hashmap + doubly linked list withDLL node's address hashed so can give LRU with .popitem(last=False)
3. self.min_used to keep track of min use count for eviction. Note: the update for min use should be

# a new key
            if prev_count == 0:
                self.min_used = 1
            else:
                if self.min_used == prev_count and len(self.usecount2orderedkv[prev_count]) == 0:
                        self.min_used += 1

4. corner case: capacity = 0

todo: try out cleaner code: https://leetcode.com/problems/lfu-cache/discuss/166683/Python-only-use-OrderedDict-get-O(1)-put-O(1)-Simple-and-Brief-Explained!!!!!!

^ takes care of min_used and corner cases

Find First and Last Position of Element in Sorted Array
2 pointer iterative bin search
https://leetcode.com/submissions/detail/541921922/?from=explore&item_id=3030
time complexity: o(n) cause of search_common

model ans: binsearch for left and right index. o(logn) time. similar template to First Bad Version

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find_left_index(nums):
            left = 0
            right = len(nums) - 1
            while left < right:
                mid = (right - left) // 2 + left # floor, left pointer has to move
                val = nums[mid]
                if val >= target:
                    # search left
                    right = mid
                else:
                    # search right
                    left = mid + 1
            return right
        
        def find_right_index(nums):  
            left = 0
            right = len(nums) - 1
            while left < right:
                mid = ceil((right - left) / 2) + left # ceil, right pointer has to move
                val = nums[mid]
                if val > target:
                    # search left
                    right = mid - 1
                else:
                    left = mid
            return left
        
        if len(nums) == 0:
            return [-1,-1]
        left = find_left_index(nums)
        right = find_right_index(nums)
        if nums[left] != target:
            return [-1, -1]
        else:
            return [left, right]

Search in Rotated Sorted Array
standard to pointer binary search, while left <= right, target case, leave out mid when resizing window

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = (right - left) // 2 + left
            val = nums[mid]
            if val == target:
                return mid
            if val < nums[right]: # right is sorted
                if nums[mid] < target and target <= nums[right]: # target is in right 
                    left = mid + 1
                else: # target is in left
                    right = mid - 1
            else: # left is sorted
                if nums[left] <= target and target < nums[mid]: # target is in left
                    right = mid - 1
                else:
                    # target is in right
                    left = mid + 1
        return -1

Maximum Subarray
my soln: sum array then find greatest max after min difference pair. similar to Best Time to Buy and Sell Stock, time = 2n = O(n)
https://leetcode.com/submissions/detail/542273944/

Kadane's Algorithm soln o(n): reset to 0 whenever cursum is neg

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxsum = -inf
        cursum = 0
        for v in nums:
            cursum += v
            maxsum = max(cursum, maxsum)
            if cursum < 0:
                cursum = 0
        return maxsum

todo: Divide and Conquer O(logn)

Integer to Roman
hardcoded mappings for 1,4,5,9 for ones (10**0), tens(10**2), hundreds (10**3), thousands (10**4): https://leetcode.com/submissions/detail/542298177/

todo: greedy soln

Insert Delete GetRandom O(1)

1. delete an element at a certain index from arr in o(1) time: swap with last ele and pop().
2. insert ele into arr in o(1): arr.append(ele)
3. use arr to get ele at random index and dict for keeping track of val to arr index (aka order)
   note: update before deletion to avoid index out of bounds error

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.val2order = {}
        self.arr = []

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        """
        if val in self.val2order:
            return False
        self.arr.append(val)
        self.val2order[val] = len(self.arr) - 1
        return True
        
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        """
        if val not in self.val2order:
            return False
        index = self.val2order[val]
        # swap with last ele
        self.arr[index], self.arr[-1] = self.arr[-1], self.arr[index]
        # update dict
        self.val2order[self.arr[index]] = index
        # remove val
        del self.val2order[val]
        self.arr.pop()
        return True
        

    def getRandom(self) -> int:
        """
        Get a random element from the set.
        """
        return self.arr[random.randint(0, len(self.arr)-1)]

Trapping Rain Water

1. scan left to right
2. scan right to left
3. get min of left to right and right to left arr return sum

class Solution:
    def trap(self, height: List[int]) -> int:
        height = [0] + height + [0]
        waterL2R = [0] * len(height)
        for i in range(1, len(height) - 2):
            water = height[i-1] - height[i] + waterL2R[i-1] 
            waterL2R[i] = max(0, water)
       
        waterR2L = [0] * (len(height))
        for i in range(len(height)-2, 0, -1):
            water = height[i+1] - height[i] + waterR2L[i+1]
            waterR2L[i] = max(0, water)
        
        # reuse waterL2R to save space
        for i in range(len(waterL2R)):
            waterL2R[i] = min(waterL2R[i], waterR2L[i])
        return sum(waterL2R)

Verifying an Alien Dictionary

class Solution:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        char2order = {}
        for i,c in enumerate(order):
            char2order[c] = i
        
        if len(words) < 2:
            return True
        for i in range(0, len(words)-1):
            cur = words[i]
            _next = words[i+1]
            for c in range(len(cur)):
                if c < len(_next):
                    if cur[c] == _next[c]:
                        continue
                    else:
                        if char2order[cur[c]] > char2order[_next[c]]:
                            return False
                        else:
                            break # stop after first different element are lexicographically in order
                else:
                    return False # eg ["apple", "app"]
        return True

Minimum Remove to Make Valid Parentheses
my soln: https://leetcode.com/submissions/detail/542868434/

1. find min number of ( and ) to remove
2. remove ) from left to right and ( from right to left greedily

K Closest Points to Origin
model soln: https://leetcode.com/problems/k-closest-points-to-origin/discuss/217969/JavaPython-3-61-liner-using-PriorityQueueheapq
use heap. O(nlogk) instead of O(nlogn)

Text Justification
my soln: https://leetcode.com/submissions/detail/542963282/
todo: understand a more concise soln

Spiral Matrix
my soln: bfs and mark visited. use ['left', 'down', 'right', 'up'] % 4 to keep track of cur step https://leetcode.com/problems/spiral-matrix/solution/

Buildings With an Ocean View
go from right to left, compare if heights[i] > max height

Permutation in String

1. [0]*26 array to keep tack of char freqs
2. sliding window of len(s1) over s2. if char count of s2 in window matches char count of s1, return True
3. To maintain window size, trim left end of window

https://leetcode.com/submissions/detail/543959401/

Spiral Matrix II

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        # create empty matrix
        ans = [[0] * n for _ in range(n)]
        limit = n*n
        
        # walk the spiral, fill in the matrix
        r,c,dr,dc = 0,0,0,1
        for num in range(limit):
            ans[r][c] = num + 1
            # if hit boundary or already written
            if ans[(r+dr)%n][(c+dc)%n] != 0:
                # change direction
                dr, dc = dc, -dr 
            r += dr
            c += dc
        return ans

cool way to change direction

dr, dc = dc, -dr 

Decode Ways
similar to 1&2 steps staircase problem

1. number of ways to partition = number of previous ways to partition + number of previous previous ways to partition
2. due to invalid codes like 34, 0 , 06, need to check if next partition's code is valid. Valid code has to be 1 to 26.
3. the next code adding onto previous partition is one digit i, and code adding onto previous previous partition is 2 digit [i-1::i+1]
   eg. 1234, i = 3 (pointing to 4), prev partition: 123|4 , prev prev partition: 12|34
   my soln: https://leetcode.com/submissions/detail/544477531/

Strobogrammatic Number
1.

strobopair = {
            '0':'0',
            '1':'1',
            '8':'8',
            '6':'9',
            '9':'6'
        }

2. find mid point (different case for odd and even)
3. expend outwards from midpoint checking if left and right pointers pair up according to strobopair
   my soln: https://leetcode.com/submissions/detail/544487333/

Smallest Subtree with all the Deepest Nodes, same as lowest-common-ancestor-of-deepest-leaves

1. post order dfs
2. base case node == None, return height = 0, subroot = None
3. return max(left subtree height, right subtree) height + 1 and subroot of taller subtree
4. if height of left subtree == height of right subtree, subroot becomes current node
   my soln: https://leetcode.com/submissions/detail/544498909/

Maximum Size Subarray Sum Equals k
similar to Permutation in String, with addition of recording start index of matching anagram window.
my soln: https://leetcode.com/submissions/detail/544518170/

Maximum Size Subarray Sum Equals k

1. sum arr of nums
2. 2 sum over sum array, target = nums[i] - k
3. match if target in seen dict. record length.
4. update seen dict with nums[i] : i. keep min i (L->R) so only update if nums[i] not in seen dict
   my soln: https://leetcode.com/submissions/detail/544512913/

Add Strings
my soln: use ord(digit) - ord('0') to convert. https://leetcode.com/submissions/detail/546041432/

2 pointer, slow and fast, where slow (one node before node to remove) is n nodes behind fast

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(0, head)
        slow, fast = dummy_head, dummy_head
        i = 0
        while fast:
            i += 1
            fast = fast.next
            if i >= n+2:
                slow = slow.next
        # remove
        slow.next = slow.next.next
        return dummy_head.next

Similar String Groups
my soln: have an arr of sets. iterate and compare each word against all other words. Group similar words in the same set. finally go through the arr of sets to count number of intersections. an intersection means the sets should be combined to one set. return number of disjoint sets, len(groups) - intersections, which should not be less then 1. https://leetcode.com/problems/similar-string-groups/submissions/

todo: understand disjoint and graph soln

Minimum Add to Make Parentheses Valid
Go from left to right, have a count = 0, if see ( add 1, else -1 from count. each time count == -1 means invalid ')'. reset count after. remaining count means num of invalid '('. https://leetcode.com/submissions/detail/546783701/

Kth Largest Element in an Array
heapq.nlargest elements. return heapq.nlargest(k, nums)[-1]
todo: understand soln: https://leetcode.com/problems/kth-largest-element-in-an-array/solution/

Find N Unique Integers Sum up to Zero

1. rule: if odd, append 0 to ans. get 1 to n//2 inclusive positive and neg range.
   cool soln: https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/discuss/464344/Trivial-PythonRubyJavaC%2B%2B