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

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