Leetcode

A collection of leetcode problems I did in college. Most these were completed in 2021 and 2022.

I honestly never got much out of doing leetcode, most of it was a memorization game for me and I lost a lot of value doing that.

1. Two Sum

Problem Link
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Hashmap Solution (1)

1. Create dictionary
2. Iterate through the numbers
3. See if the number you are looking for (target = 3 + ?)
   1. If it is, return the list
   2. Else, add that number to the dictionary

def twoSum(self, nums: List[int], target: int) -> List[int]:
    d = {} # 1
    for i in range(len(nums)): # 2
        look = target - nums[i] # 3
        if look in d: # 3.1
            return [i, d[look]]
        d[nums[i]] = i # 3.2
    return

2. Add Two Numbers

Problem Link
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Carry Solution (2)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = cur = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry%10)
            cur = cur.next
            carry = carry // 10
        return dummy.next

Anki (2)

https://leetcode.com/problems/add-two-numbers/

1. Create two nodes and a carry to start the output
2. Start a while loop with the termination condition of l1 or l2 or carry
   1. Check if l1 is valid, if so sum carry with the value and iterate it to the next node
   2. Check if l2 is valid, if so sum carry with the value and iterate it to the next node
   3. Set cur.next equal to the LSB of carry
   4. say cur = cur.next
   5. delete LSB of carry
3. return the node storing the head’s .next variable

3. Longest Substring Without Repeating Characters

Problem Link
Given a string s, find the length of the longest substring without repeating characters.

Sliding Window Solution (3)

1. Create a set charset, left pointer l and result res
2. Iterate through the string s
3. Use a while loop to incrementally delete the left pointer to reach the right pointer
4. Add the element at the right pointer s[r] to the charset
5. Check if the current or previous subset is the largest
6. Return result res

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charset = set() # 1
        l = 0 # 1
        res = 0 # 1

        for r in range(len(s)): # 2
            while s[r] in charset: # 3
                charset.remove(s[l])
                l += 1
            charset.add(s[r]) # 4
            res = max(res, r - l + 1) # 5
        return res

Anki (3)

https://leetcode.com/problems/longest-substring-without-repeating-characters/ #flashcard

1. Create a set charset, left pointer l and result res
2. Iterate through the string s
3. Use a while loop to incrementally delete the left pointer to reach the right pointer
4. Add the element at the right pointer s[r] to the charset
5. Check if the current or previous subset is the largest
6. Return

Intuitive Solution (3)

Sliding window for real

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        res = 0
        charset = set()
        l = 0
        r = 1
        charset.add(s[l])
        while r < len(s):
            while s[r] in charset:
                charset.remove(s[l])
                l += 1
            res = max(res, r - l + 1)
            charset.add(s[r])
            r += 1
        res = max(res, r - l)
        return res

7. Reverse Integer

Problem Link
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Reverse String Solution (7)

class Solution:
    def reverse(self, x: int) -> int:
        negative = False
        if x < 0:
            negative = True
            x = -x

        x = str(x)[::-1]
        x = int(x)
        if negative:
            x = -x

        if x > 2**31 - 1 or x < -2**31:
            return 0
        return x

Anki (7)

https://leetcode.com/problems/reverse-integer/ #flashcard
String solution or floor and mod solution

9. Palindrome Number

Problem Link
Given an integer x, return true if x is palindrome integer. An integer is a palindrome when it reads the same backward as forward

Cast to String Solution (9)

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0:
            return False
        elif str(x) == str(x)[::-1]:
            return True

Floor and Mod Solution (9)

1. Check if int x is less than 0 as negative number cannot be palindromes
2. Create a loop while x > 0
   1. Multiply the return value by 10 and add mod 10 of the number to be flipped
   2. Then x = x // 10 to decrement the input
3. Compare the original to the flipped version, if they are equivalent return True, original == flipped

class Solution:
    def isPalindrome(self, x: int) -> bool:        
        if x < 0:
            return False

        original = x
        new = 0
        while x > 0:
            new = new * 10 + x % 10
            x = x // 10
        return new == original

Anki (9)

https://leetcode.com/problems/palindrome-number/ #flashcard

1. Check if int x is less than 0 as negative number cannot be palindromes
2. Create a loop while x > 0
   1. Multiply the return value by 10 and add mod 10 of the number to be flipped
   2. Then x = x // 10 to decrement the input
3. Compare the original to the flipped version, if they are equivalent return True, original == flipped

11. Container With Most Water

Problem Link
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Two Pointer Solution (11)

1. Initialize out, left pointer at 0, and right pointer at the end of input array
2. Iterate through list while l < r
   1. calculate the area of the current contained area
   2. save the maximum area
   3. move the pointer based on which pointer is shorter
3. Return

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height)-1
        out = 0
        while l < r:
            area = min(height[l], height[r])* (r - l)
            out = max(out, area)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return out

Anki (11)

https://leetcode.com/problems/container-with-most-water/ #flashcard

1. Initialize out, left pointer at 0, and right pointer at the end of input array
2. Iterate through list while l < r
   1. calculate the area of the current contained area
   2. save the maximum area
   3. move the pointer based on which pointer is shorter
3. Return

14. Longest Common Prefix

Problem Link
Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        out = []
        # find the shortest string to prevent exceeding index
        use = 0
        for i in range(len(strs)):
            if len(strs[i]) < len(strs[use]):
                use = i
        # comparing each character 
        for i in range(len(strs[use])):
            compare = strs[0][i]
            for word in strs:
                if compare != word[i]:
                    return ''.join(out)
            out.append(compare)
        return ''.join(out)

Anki (14)

15. Three Sum

Problem Link
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Python Solution

Two Pointer Solution (15)

1. Create a list
2. Sort list nums
3. Iterate through list nums
   1. Create left and right pointers
   2. While l < r, increment l and decrement r until you find a proper answer
      1. If match found, increment l to avoid duplicate lists in returnlist
4. Return

def threeSum(self, nums: List[int]) -> List[List[int]]:
    returnlist = [] # 1
    nums.sort() # 2
    for i in range(len(nums)): # 3
        if i > 0 and nums[i] == nums[i-1]:
            continue
        l = i + 1 # 4
        r = len(nums)-1 # 4
        while l < r: # 5
            ans = nums[i] + nums[l] + nums[r]
            if ans > 0:
                r -= 1
            elif ans < 0:
                l += 1
            else:
                returnlist.append([nums[i], nums[l], nums[r]])
                l += 1
                while nums[l] == nums[l - 1] and l < r: # 6
                    l += 1
    return returnlist

Anki (15)

https://leetcode.com/problems/3sum/ #flashcard

1. Create a list
2. Sort list nums
3. Iterate through list nums
   1. Create left and right pointers
   2. While l < r, increment l and decrement r until you find a proper answer
      1. If match found, increment l to avoid duplicate lists in returnlist
4. Return

16. Three Sum Closest

Problem Link
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers. You may assume that each input would have exactly one solution.

Two Pointer Solution (16)

Note: Same as [[000 leetcode collection#15 Three Sum|Three Sum]] but stores the closest answer

1. Set the closest as the sum of the first the numbers in the array instead of setting it to infinity.
2. Sort array nums
3. Iterate through array nums
   1. Skip the number i if it is equivalent to the previous number i
   2. Use two pointers within the iteration
   3. If the sum of nums[i] + nums[l] + nums[r] is closer than closest, assign closest equal to nums[i] + nums[l] + nums[r]
4. Return

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        closest = sum(nums[:3]) # 1
        nums.sort() # 2
        for i in range(len(nums)): # 3
            if i > 0 and nums[i] == nums[i-1]: # 3.1
                continue
            l = i + 1 # 4
            r = len(nums)-1 # 4 
            while l < r: # 4
                s = nums[i] + nums[l] + nums[r] # 5
                if abs(s - target) < abs(closest - target):
                    closest = s

                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
                else:
                    return s
        return closest

Anki (16)

https://leetcode.com/problems/3sum-closest/ #flashcard

1. Set the closest as the sum of the first the numbers in the array instead of setting it to infinity.
2. Sort array nums
3. Iterate through array nums
   1. Skip the number i if it is equivalent to the previous number i
   2. Use two pointers within the iteration
   3. If the sum of nums[i] + nums[l] + nums[r] is closer than closest, assign closest equal to nums[i] + nums[l] + nums[r]
4. Return

19. Remove Nth Node From End of List

Problem Link
Given the head of a linked list, remove the nth node from the end of the list and return its head.

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        arr = []
        cur = head
        while cur:
            arr.append(cur)
            cur = cur.next

        i = len(arr) - n
        prev = arr[i - 1]
        if i <= 0:
            return head.next
        else:
            if prev.next:
                prev.next = prev.next.next
            else:
                prev.next = None
        return head

Anki (19)

20. Valid Parentheses

Problem Link
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Stack Solution (20)

1. See if the string is length of an odd number, making it impossible to make every bracket valid
2. Initialize stack
3. Initialize dictionary with proper mapping of opposite
4. Iterate through string and see if it is an opening or closing bracket
   1. If it closing, check if it matches the last item on the stack
   2. If it is opening, add it to the stack
5. If the stack has remaining elements after reaching the end of the string s, return False
6. If it has passed all test cases, return True

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False

        stack = []
        d = {'[':']', '(':')', '{':'}'}
        for c in s:
            if c not in d.keys():
                if stack:
                    test = d[stack.pop()]
                    if test != c:
                        return False
                else:
                    return False
            else:
                stack.append(c)
        if stack:
            return False
        return True

Anki (20)

https://leetcode.com/problems/valid-parentheses/ #flashcard

1. See if the string is length of an odd number, making it impossible to make every bracket valid
2. Initialize stack
3. Initialize dictionary with proper mapping of opposite
4. Iterate through string and see if it is an opening or closing bracket
   1. If it closing, check if it matches the last item on the stack
   2. If it is opening, add it to the stack
5. If the stack has remaining elements after reaching the end of the string s, return False
6. If it has passed all test cases, return True

21. Merge Two Sorted Lists

Problem Link
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Merging Solution (21)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        cur = dummy = ListNode()
        while list1 and list2:               
            if list1.val < list2.val:
                cur.next = list1
                tmp = list1
                list1 = list1.next
                cur = tmp
            else:
                cur.next = list2
                tmp = list2
                list2 = list2.next
                cur = tmp

        if list1 or list2:
            if list1:
                cur.next = list1
            else:
                cur.next = list2

        return dummy.next

Anki (21)

https://leetcode.com/problems/merge-two-sorted-lists/ #flashcard
This one easy easy

Naive Solution (21)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return 
        elif not list2:
            cur = ListNode(list1.val)
            list1 = list1.next
        elif not list1:
            cur = ListNode(list2.val)
            list2 = list2.next
        elif list1.val < list2.val:
            cur = ListNode(list1.val)
            list1 = list1.next
        else:
            cur = ListNode(list2.val)
            list2 = list2.next
        head = cur
        while list1 or list2:
            if not list2:
                cur.next = ListNode(list1.val)
                list1 = list1.next
            elif not list1:
                cur.next = ListNode(list2.val)
                list2 = list2.next
            else:
                if list1.val < list2.val:
                    cur.next = ListNode(list1.val)
                    list1 = list1.next
                else:
                    cur.next = ListNode(list2.val)
                    list2 = list2.next
            cur = cur.next
        return head

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

DFS Solution (22)

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if not n:
            return []
        left = right = n
        out = []
        self.dfs(left,right, out, "")
        return out

    def dfs(self, left, right, out, string):
        if right < left:
            return
        if not left and not right:
            out.append(string)
            return
        if left:
            self.dfs(left-1, right, out, string + "(")
        if right:
            self.dfs(left, right-1, out, string + ")")

Anki (22)

https://leetcode.com/problems/generate-parentheses/ #flashcard
DFS:

1. If right < left: return
2. if not left and not right: append(str)
3. if left: self.dfs(left-1, right, out, str + ‘(‘)
4. if right: self.dfs(left, right-1, out, str + ‘)’)

35. Search Insert Position

Problem Link
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Binary Search Solution

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums)-1
        would = 0
        print(l) 
        print(r)
        while l <= r:
            mid = (r + l) // 2
            print(mid)
            would = mid
            if nums[mid] < target:
                l = mid + 1
            elif nums[mid] > target:
                r = mid-1
            else:
                return mid
        if nums[would] < target:
            return would + 1
        return would 

49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Hashmap / Ascii Solution (49)

1. Create dictionary
2. Create alphabet list
3. Add characters to alphabet list
4. Add word to dictionary using key “alphabet list”
5. Return

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        res = {} # 1

        for s in strs: # 2
            count = [0] * 26 # 26 because only lowercase letters used

            for c in s: # 3
                count[ord(c) - ord('a')] += 1

            if tuple(count) not in res: # 4
                res[tuple(count)] = []
            res[tuple(count)].append(s) 

        return res.values() # 5

Sort String Solution (49)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = {}
        for s in strs:
            key = list(s)
            key.sort()
            # print(key)
            if tuple(key) not in d:
                d[tuple(key)] = []
            d[tuple(key)].append(s)
        return d.values()

Anki (49)

https://leetcode.com/problems/group-anagrams/ #flashcard

1. Create dictionary
2. Create alphabet list
3. Add characters to alphabet list
4. Add word to dictionary using key “alphabet list”
5. Return

70. Climbing Stairs

Problem Link
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Python Solution
C++ Solution

Dynamic Programming Solution (70)

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2: # base case eliminator
            return n
        else:
            a = 1
            b = 2
            while n > 2:
                tmp = a + b
                a = b
                b = tmp
                n -= 1
            return b

Anki (70)

https://leetcode.com/problems/climbing-stairs/ #flashcard
DP

74. Search a 2D Matrix

Problem Link
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Binary Search Solution (74)

1. Create left (0) and right matrix pointers (len(matrix)-1)
2. Use binary search to locate the array which would contain the desired element
3. Use binary search on this array to check if the target element is present
4. Return true/false based on if target element is found

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l = 0
        r = len(matrix)-1
        while l <= r:
            mmid = (l + r) // 2
            row = matrix[mmid]
            if row[0] > target:
                r = mmid - 1
            elif row[-1] < target:
                l = mmid + 1
            else:
                l2 = 0
                r2 = len(row)-1
                while l2 <= r2:
                    mid2 = (l2 + r2) // 2
                    if row[mid2] < target:
                        l2 = mid2 + 1
                    elif row[mid2] > target:
                        r2 = mid2 - 1
                    else:
                        return True
                return False
        return False

Merge Matrix Into List (74)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        out = []
        for row in matrix:
            out += row

        # binary search
        l = 0
        r = len(out)-1
        while l <= r:
            m = (l + r) // 2
            if out[m] < target:
                l = m + 1
            elif out[m] > target:
                r = m - 1
            else:
                return True
        return False

Anki (74)

https://leetcode.com/problems/search-a-2d-matrix/ #flashcard

1. Create left (0) and right matrix pointers (len(matrix)-1)
2. Use binary search to locate the array which would contain the desired element
3. Use binary search on this array to check if the target element is present
4. Return true/false based on if target element is found

94. Binary Tree Inorder Traversal

Problem Link
Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Depth-First Search Solution (94)

1. Check if there is a root
2. Check if the root has children, if it doesn’t return root.val
3. Else, return recursive items in this order
   1. Traverse(root.left)
   2. root.val
   3. Traverse(root.right)

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        if not root.right and not root.left:
            return [root.val]
        else:
            return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

Anki (94)

https://leetcode.com/problems/binary-tree-inorder-traversal/ #flashcard

1. Check if there is a root
2. Check if the root has children, if it doesn’t return root.val
3. Else, return recursive items in this order
   1. Traverse(root.left)
   2. root.val
   3. Traverse(root.right)

100. Same Tree

Problem Link
Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Depth-First Search Solution (100)

1. See if the nodes are present
2. See if the nodes values are not equal to disqualify
3. Else, return a recursive function down the tree
   1. SameTree(p.left, q.left) and SameTree(p.right, q.right)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p or not q:
            return p == q
        elif p.val != q.val:
            return False
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Anki (100)

https://leetcode.com/problems/same-tree/ #flashcard

1. See if the nodes are present
2. See if the nodes values are not equal to disqualify
3. Else, return a recursive function down the tree
   1. SameTree(p.left, q.left) and SameTree(p.right, q.right)

101. Symmetric Tree

Problem Link
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Depth-First Search Solution (101)

1. Create a new function to accept left and right branches of a root
   1. Check if both branches are present, otherwise return false
   2. Otherwise check if the two branches are the same and return the recursive versions of the proper branches

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.f(root.left, root.right)

    def f(self, l, r):
        if not l or not r:
            return l == r
        else:
            return l.val == r.val and self.f(l.right, r.left) and self.f(l.left, r.right)

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return f(root->right, root->left);
    }

    bool f(TreeNode* r, TreeNode* l) {
        if (!r || !l) return r == l;
        else {
            return r->val == l->val && f(r->right, l->left) && f(r->left, l->right);
        }
    }
};

Anki (101)

https://leetcode.com/problems/symmetric-tree/ #flashcard

1. Create a new function to accept left and right branches of a root
   1. Check if both branches are present, otherwise return false
   2. Otherwise check if the two branches are the same and return the recursive versions of the proper branches

104. Maximum Depth of Binary Tree

Problem Link
Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Python solution
C++ Solution

Recursive Solution (104)

1. If not root, depth of zero
2. If root with no children, depth of 1
3. Else, return 1 + the longest subtree found through recursion

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        elif not root.right and not root.left:
            return 1
        else:
            l = self.maxDepth(root.left)
            r = self.maxDepth(root.right)
            if r > l:
                return 1 + r
            else:
                return 1 + l

Anki (104)

https://leetcode.com/problems/maximum-depth-of-binary-tree/ #flashcard

1. If not root, depth of zero
2. If root with no children, depth of 1
3. Else, return 1 + the longest subtree fonud through recursion

110. Balanced Binary Tree

Problem Link
Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as “a binary tree in which the left and right subtrees of every node differ in height by no more than 1.”
Tree, Depth-First Search, Binary Tree

Depth-First Search Solution (110)

1. Create a function to set equal to -1 to return a bool value
   1. If there is no root, return 0
   2. Create recursive left and right subtrees
   3. Check if either tree is equal to -1 (indicating there is imbalance)
   4. If not, return 1 + the max of left and right subtrees

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        return self.f(root) != -1

    def f(self, root):
        if not root:
            return 0

        l = self.f(root.left)
        r = self.f(root.right)

        if l == -1 or r == -1:
            return -1
        if abs(l - r) > 1:
            return -1
        return 1 + max(l, r)

Anki (110)

https://leetcode.com/problems/balanced-binary-tree/ #flashcard

1. Create a function to set equal to -1 to return a bool value
   1. If there is no root, return 0
   2. Create recursive left and right subtrees
   3. Check if either tree is equal to -1 (indicating there is imbalance)
   4. If not, return 1 + the max of left and right subtrees

111. Minimum Depth of Binary Tree

Problem Link
Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Depth First Search (111)

1. If root is not present, return 0
2. Create variables to store both recursive right and left subtrees
3. If the tree is missing one branch, use the longest branch to find the minimum depth still
4. Else, return 1 + minimum of right and left subtrees

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        r = self.minDepth(root.right)
        l = self.minDepth(root.left)

        if not root.right or not root.left:
            return 1 + max(r, l)

        return 1 + min(r, l)

Anki (111)

https://leetcode.com/problems/minimum-depth-of-binary-tree/ #flashcard

1. If root is not present, return 0
2. Create variables to store both recursive right and left subtrees
3. If the tree is missing one branch, use the longest branch to find the minimum depth still
4. Else, return 1 + minimum of right and left subtrees

112. Path Sum

Problem Link
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

DFS Solution (112)

    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        if not root.left and not root.right and root.val == targetSum:
            return True

        targetSum -= root.val

        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

Anki (112)

https://leetcode.com/problems/path-sum/ #flashcard
DFS

117. Populating Next Right Pointers in Each Node 2

Problem Link
Given a binary tree, populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL.

Breadth-First Search Solution (117)

This solution implements the [[404 Data Structures#Breadth-First Search Binary Search Tree|breadth-first search]] algorithm with the slight modification of the prev attribute. When you traverse the level, you assign prev to the previous node traversed on that level.

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root == None: 
            return root
        q = []
        q.append(root)
        while q:
            prev = None
            for _ in range(len(q)):
                cur = q.pop(0)
                if prev != None:
                    prev.next = cur
                prev = cur
                if cur.left != None:
                    q.append(cur.left)
                if cur.right != None:
                    q.append(cur.right)
        return root

Anki (117)

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/ #flashcard
BFS Solution

121. Best Time to Buy and Sell Stock

Problem Link
You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Kadane’s Algorithm Solution (121)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Kadane's Algorithm
        # Same problem as Max Subarray
        maxPrice = 0
        minPrice = prices[0]
        for i in prices:
            if i < minPrice:
                minPrice = i
            elif i - minPrice > maxPrice:
                maxPrice = i - minPrice
        return maxPrice

Sliding Window Solution (121)

1. Initialize max m, left and right pointers l and r
2. Iterate through prices while r hasn’t reached the end
3. If prices[l] < prices[r] then see if it is the new largest profit
4. If prices[l] > prices[r] then l = r since you have checked every index between the two already
5. Increment r

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = 0 # 1
        r = 1 # 1
        m = 0 # 1
        while r < len(prices): # 2
            if prices[l] < prices[r]: # 3
                profit = prices[r] - prices[l]
                m = max(profit, m)
            else: # 4
                l = r
            r += 1 # 5
        return m

Anki (121)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ #flashcard

1. Initialize max m, left and right pointers l and r
2. Iterate through prices while r hasn’t reached the end
3. If prices[l] < prices[r] then see if it is the new largest profit
4. If prices[l] > prices[r] then l = r since you have checked every index between the two already
5. Increment r

125. Valid Palindrome

Problem Link
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Two Pointer / Regex (125)

1. Remove all characters that aren’t letters or numbers
2. Create two pointers
3. Iterate through the new string until the two pointers meet
   1. Set the character at the pointers locations to lowercase and compare to possibly return False
4. Increment pointers
5. If it completes, return True

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = re.sub('[^A-Za-z0-9]+', '', s)
        l = 0
        r = len(s)-1
        while l < r:
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True

Anki (125)

https://leetcode.com/problems/valid-palindrome/ #flashcard

1. Remove all characters that aren’t letters or numbers
2. Create two pointers
3. Iterate through the new string until the two pointers meet
   1. Set the character at the pointers locations to lowercase and compare to possibly return False
4. Increment pointers
5. If it completes, return True

129. Sum Root to Leaf Numbers

Problem Link
You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Recursive Solution (129)

# Recursive
def sumNumbers(self, root) -> int:
    if not root:
        return 0
    elif not root.right and not root.left:
        return root.val
    if root.left: 
        root.left.val = 10 * root.val + root.left.val
    if root.right:
        root.right.val = 10 * root.val + root.right.val

    return self.sumNumbers(root.left) + self.sumNumbers(root.right)

Anki (129)

https://leetcode.com/problems/sum-root-to-leaf-numbers/ #flashcard
DFS

Single Number (136)

Problem Link
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant extra space.

XOR Solution (136)

1. Create value to store result
2. Iterate through num in nums
   1. XOR result with num
3. Return

def singleNumber(self, nums: List[int]) -> int:
    solution = 0
    for num in nums:
        # operation for XOR in python
        solution ^= num
    return solution

Single Number II (137)

Problem Link
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.

Hashmap Solution (137)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        d = {}
        for n in nums:
            if n in d:
                d[n] += 1
            else:
                d[n] = 1

        for key, val in d.items():
            if val == 1:
                return key
        return

Anki (137)

https://leetcode.com/problems/single-number/ #flashcard

1. Create value to store result
2. Iterate through num in nums
   1. XOR result with num
3. Return

141. Linked List Cycle

Problem Link
Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Tortoise and the Hare Solution (141)

Here we use the [[contest algorithms#Tortoise and the Hare Floyd’s Algorithm|tortoise and the hare algorithm]] to find the cycle in the linked list. This algorithm was specifically developed for this purpose.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # a try statement incase head.next does not exist
        try:
            slow = head
            fast = head.next
            while slow != fast:
                # if either pointer has reached the end of the linked list
                if slow == None or fast == None:
                    return False
                slow = slow.next
                fast = fast.next.next
            return True
        except:
            return False

Anki (141)

https://leetcode.com/problems/linked-list-cycle/ #flashcard
Tortoise and the hare solution

148. Sort List

Problem Link
Given the head of a linked list, return the list after sorting it in ascending order

Intuitive Sort List (148)

The intuitive sort list explicitly codes out merge sort and sorts the linked list

“` python
class Solution:
def sortList(self, head):
if not head or not head.next: return head
mid = self.getMid(head)
left = self.sortList(head)
right = self.sortList(mid)
return self.merge(left, right)

# Merge sort (as specified in problem)
def getMid(self, head):
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    return mid

def merge(self, head1, head2):
    dummy = tail = ListNode(None)
    while head1 and head2:
        if head1.val < head2.val:
            tail.next, tail, head1 = head1, head1, head1.next
        else:
            tail.next, tail, head2 = head2, head2, head2.next

    tail.next = head1 or head2
    return dummy.next

Optimal Sort List (148)

This solution uses python’s default sort algorithm, tim sort. The array is transformed from linked list into an array $O(n)$, sorted $O(n log n)$ and then transformed back into a linked list $O(n)$

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        temp = head
            while temp:
            vals.append(temp.val)
            temp = temp.next

        vals.sort()
        temp = head

        for val in vals:
            temp.val = val
            temp = temp.next
  
        return head

155. Min Stack

Problem Link
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.

Two Stack Solution (155)

1. Create self.stack and self.minStack in __init__
2. PUSH: Append val to normal stack, compare top of minStack to new value val
3. POP: Pop from both stacks
4. TOP: return top of self.stack
5. GETMIN: return top of self.minStack

class MinStack:
    def __init__(self):
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        if not self.minStack or val < self.minStack[-1]:
            self.minStack.append(val)
        else:
            self.minStack.append(self.minStack[-1])

    def pop(self) -> None:
        self.minStack.pop()
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1]

Anki (155)

https://leetcode.com/problems/min-stack/ #flashcard

1. Create self.stack and self.minStack in __init__
2. PUSH: Append val to normal stack, compare top of minStack to new value val
3. POP: Pop from both stacks
4. TOP: return top of self.stack
5. GETMIN: return top of self.minStack

167. Two Sum 2

Problem Link
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2_, added by one as an integer array_ [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Two Pointer Solution (167)

1. Create left and right pointers
2. Iterate through list using the two pointers (since list is sorted)
3. If the numbers equal the target, return the pointer locations

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l = 0 # 1
        r = len(numbers)-1 # 1
        while l < r: # 2
            s = numbers[l] + numbers[r]
            if s < target:
                l += 1
            elif s > target:
                r -= 1
            else: # 3
                return [l + 1, r + 1]

Anki (167)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ #flashcard

1. Create left and right pointers
2. Iterate through list using the two pointers (since list is sorted)
3. If the numbers equal the target, return the pointer locations

169. Majority Element

Problem Link
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Hashmap Solution

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        d = {}
        m = 0
        if len(nums) == 1:
            return nums[0]
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
                if d[i] > len(nums)/2:
                    return i

191. Number of 1 Bits

Problem Link

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Binary Solution (191)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')

Anki (191)

https://leetcode.com/problems/number-of-1-bits/ #flashcard
count binary

198. House Robber

Problem Link

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Dynamic Programming (198)

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1 = 0
        rob2 = 0
        for house in nums:
            tmp = max(house + rob1, rob2)
            rob1 = rob2
            rob2 = tmp
        return rob2

Anki (198)

https://leetcode.com/problems/house-robber/ #flashcard
House Robber Solution, i’m too lazy to write the steps

206. Reverse Linked List

Problem Link
Given the head of a singly linked list, reverse the list, and return the reversed list.

Iterative Solution (206)

1. Create pointer prev
2. While loop until head no longer exists
   1. Store the next head
   2. Set the next head to pointer prev
   3. increment prev=head and head=head.next (tmp)
3. Return pointer prev

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            tmp = head.next
            head.next = prev
            prev = head
            head = tmp
        return prev

Anki (206)

https://leetcode.com/problems/reverse-linked-list/ #flashcard

1. Create pointer prev
2. While loop until head no longer exists
   1. Store the next head
   2. Set the next head to pointer prev
   3. increment prev=head and head=head.next (tmp)
3. Return pointer prev

213. House Robber 2

TIME: 0:58

Problem Link
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Dynamic Programming Solution (213)

class Solution:
    def rob(self, nums: List[int]) -> int:    
        return max(nums[0] + self.robbing(nums[2:-1]), \
                   self.robbing(nums[1:]))

    def robbing(self, nums):
        rob1 = 0
        rob2 = 0
        for house in nums:
            tmp = max(house + rob1, rob2)
            rob1 = rob2
            rob2 = tmp
        return rob2

Anki (213)

https://leetcode.com/problems/house-robber-ii/ #flashcard

1. Return the output of two subproblems
   1. The mandatory first step: nums[0] + … + nums[2:-1]
   2. The second step: nums[1:]
2. Create another function to use dynamic programming to solve the two sub problems
   1. Create two variables to store values (a, b: equivalents)
   2. Iterate through each num in the house to sum together
3. Return b (or rob2)

217. Contains Duplicate

Problem Link
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Hashmap Solution (217)

1. Create dictionary
2. Iterate through list nums and add to dictionary
   1. If item already in dictionary, return True
   2. Else, return False

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        d = {}
        for i in nums:
            if i in d:
                return True
            d[i] = 0
        return False

Anki (217)

https://leetcode.com/problems/contains-duplicate/ #flashcard

1. Create dictionary
2. Iterate through list nums and add to dictionary
   1. If item already in dictionary, return True
   2. Else, return False

219. Contains Duplicate 2

Problem Link
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Note: Basically means the number between two duplicate numbers cannot be greater than k

Hashmap Solution (219)

1. Create dictionary
2. Iterate through list nums
3. If num i is a duplicate and closer than k, return True
4. Add num to dictionary
5. If you never find a proper case, return False

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = {}
        for i in range(len(nums)):
            if nums[i] in d:
                if abs(d[nums[i]] - i) <= k:
                    return True
            d[nums[i]] = i
        return False

Anki (219)

https://leetcode.com/problems/contains-duplicate-ii/ #flashcard

1. Create dictionary
2. Iterate through list nums
3. If num i is a duplicate and closer than k, return True
4. Add num to dictionary
5. If you never find a proper case, return False

226. Invert Binary Tree

Problem Link
Given the root of a binary tree, invert the tree, and return its root.

Python Solution
C++ Solution

Depth-First Search Solution (226)

1. If there is a root, then you are able to invert it
2. Recursively find right subtree and left subtree
3. Swap right and left subtrees
4. Return modified root

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root: # 1
        r = self.invertTree(root.right) # 2
        l = self.invertTree(root.left) # 2
        root.left = r # 3
        root.right = l # 3
        return root # 4

Anki (226)

https://leetcode.com/problems/invert-binary-tree/ #flashcard

1. If there is a root, then you are able to invert it
2. Recursively find right subtree and left subtree
3. Swap right and left subtrees
4. Return modified root

237. Delete Node in a Linked List

Time: 0:12
Problem Link
Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Simple Solution (237)

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

Anki (237)

https://leetcode.com/problems/delete-node-in-a-linked-list/ #flashcard
Simple solution man, cmon its so easy

238. Product of Array Except Self

Problem Link
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Prefix and Postfix Solution (238)

1. Initialize a list full of 1’s to store prefix values, then final answer
2. PREFIX: Iterate through nums, increment prefix by the current nums[i] and store it in the return list out
3. POSTFIX: Iterate through nums, increment postfix and multiply each item in the prefix array by the upcoming index in the newly generated postfix numbers
4. Return answer list

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = [1] * len(nums) # 1
        prefix = 1
        for i in range(len(nums)): # 2
            out[i] = prefix
            prefix *= nums[i]

        postfix = 1
        for i in reversed(range(len(nums))): # 3
            out[i] *= postfix
            postfix *= nums[i]

        return out

Anki (238)

https://leetcode.com/problems/product-of-array-except-self/ #flashcard

1. Initialize a list full of 1’s to store prefix values, then final answer
2. PREFIX: Iterate through nums, increment prefix by the current nums[i] and store it in the return list out
3. POSTFIX: Iterate through nums, increment postfix and multiply each item in the prefix array by the upcoming index in the newly generated postfix numbers
4. Return answer list

242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s_, and_ false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Hashmap Comparison Solution (242)

1. If the length of the two words are not the same, they cannot be anagrams
2. Create dictionaries to map the characters in s and t
3. Iterate through s and t, then map the characters to the dictionary
4. Set the dictionaries equal to each other and return the answer

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t): # 1
            return False
        d1 = {} # 2
        d2 = {} # 2
        for i in range(len(s)): # 3
            if s[i] not in d1:
                d1[s[i]] = 1
            else:
                d1[s[i]] += 1
            if t[i] not in d2:
                d2[t[i]] = 1
            else:
                d2[t[i]] += 1
        return d1 == d2 # 4

Anki (242)

https://leetcode.com/problems/valid-anagram/ #flashcard

1. If the length of the two words are not the same, they cannot be anagrams
2. Create dictionaries to map the characters in s and t
3. Iterate through s and t, then map the characters to the dictionary
4. Set the dictionaries equal to each other and return the answer

268. Missing Number

Problem Link
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Bit Manipulation Solution (268)

Using XOR we can find the missing bit

1. Set a variable to store solution
2. iterate through array nums
   1. solution = XOR of solution and index + 1
   2. solution = XOR of solution and nums[i]
3. Return

def missingNumber(self, nums: List[int]) -> int:
    solution = 0
    for i in range(len(nums)):
        solution ^= i+1
        solution ^= nums[i]
    return solution

Anki (268)

https://leetcode.com/problems/missing-number/ #flashcard
Using XOR we can find the missing bit

1. Set a variable to store solution
2. iterate through array nums
   1. solution = XOR of solution and index + 1
   2. solution = XOR of solution and nums[i]
3. Return

Reverse Vowels of a String

Problem Link
Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = 'aeiouAEIOU'
        s = list(s)
        stack = []
        for n in s:
            if n in vowels:
                stack.append(n)
        for n in reversed(range(len(s))):
            if s[n] in vowels:
                s[n] = stack.pop(0)
        return ''.join(s)

347. Top K Frequent Elements

Problem Link
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Naive Hashmap Solution (347)

1. Populate a dictionary with the frequency of all items in list nums
2. Create a list ordering items by frequency in which they appear
3. Reverse the ordered list and iterate through each sub-list to append until you reach the desired k amount tracked with kcount

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = {} # 1
        for i in nums:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1

        key_list = [[] for j in range(len(nums)+1)] # 2
        for key, value in d.items():
            key_list[value].append(key)

        returnlist = []
        kcount = 0
        for i in reversed(range(len(key_list))): # 3
            for j in key_list[i]:
                if kcount < k:
                    returnlist.append(j)
                    kcount += 1
        return returnlist

Anki (347)

https://leetcode.com/problems/top-k-frequent-elements/ #flashcard

1. Populate a dictionary with the frequency of all items in list nums
2. Create a list ordering items by frequency in which they appear
3. Reverse the ordered list and iterate through each sub-list to append until you reach the desired k amount tracked with kcount

376. Wiggle Subsequence

Problem Link
A wiggle sequence is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.

• For example, [1, 7, 4, 9, 2, 5] is a wiggle sequence because the differences (6, -3, 5, -7, 3) alternate between positive and negative.
• In contrast, [1, 4, 7, 2, 5] and [1, 7, 4, 5, 5] are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.

A subsequence is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

Given an integer array nums, return the length of the longest wiggle subsequence of nums.

Dynamic Programming Solution (376)

1. If non items in the list, there is no wiggle subsequence
2. Initialize up to keep track of wiggle and longest to keep track of the subsequence
3. Iterate through the list nums starting from the first index (to check the previous index without errors)
4. Compare the current number to the previous to check for “wiggle” using wiggle
5. Return longest

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if not nums: # 1
            return 0

        wiggle = None # 2
        longest = 1 # 2
        for i in range(1, len(nums)): # 3 
            if nums[i] > nums[i-1] and wiggle != True: # 4
                longest += 1
                up = True
            elif nums[i] < nums[i-1] and wiggle != False: # 4
                longest += 1
                up = False

        return longest

Anki (376)

https://leetcode.com/problems/wiggle-subsequence/ #flashcard

1. If non items in the list, there is no wiggle subsequence
2. Initialize up to keep track of wiggle and longest to keep track of the subsequence
3. Iterate through the list nums starting from the first index (to check the previous index without errors)
4. Compare the current number to the previous to check for “wiggle” using wiggle
5. Return longest

389. Find the Difference

Problem Link
You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

XOR Solution

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        out = 0
        for c in s:
            out ^= ord(c)
        for c in t:
            out ^= ord(c)
        return chr(out)

Anki (389)

https://leetcode.com/problems/find-the-difference/ #flashcard
XOR Solution

404. Sum of Left Leaves

Problem Link
Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Depth-First Search Solution (404)

def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
    return self.dfs(root, False)

def dfs(self, node, left_side):
    if not node:
        return 0
    elif not node.left and not node.right:
        if left_side:
            return node.val
        else:
            return 0
    else:
        return self.dfs(node.left, True) + self.dfs(node.right, False)

Anki (404)

https://leetcode.com/problems/sum-of-left-leaves/ #flashcard
Add solution here later I’m lazy

421. Maximum XOR of Two Numbers in an Array

Problem Link

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Mask / Set Solution (421)

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        mask = 0
        for i in reversed(range(31)):
            mask |= 1<

def fib(self, n: int) -> int:
    if n <= 1: # base case
        return n
    a = 0
    b = 1
    while n > 2: # don't visit fib1 and fib2
        tmp = a + b
        a = b
        b = tmp
        n -= 1
    return b

def fib(self, n: int) -> int:
    if n <= 1:
        return n
    else:
        return self.fib(n-1) + self.fib(n-2)

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        count = {}
        max_count = 0
        for word in words:
            if word not in count:
                count[word] = 1
            else:
                count[word] += 1
            if count[word] > max_count:
                max_count = count[word]

        out = []
        l = [[] for i in range(max_count + 1)]
        for word, num in count.items():
            l[num].append(word)
        print(l)

        for s in reversed(l):
            while s:
                s.sort()
                out.append(s.pop(0))
                k -= 1
                if k == 0:
                    return out
        return out

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        elif root.val == val:
            return root
        else:
            return self.searchBST(root.right, val) or self.searchBST(root.left, val)

def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
    if not root:
        return TreeNode(val)
    if root.val < val:
        root.right = self.insertIntoBST(root.right, val)
    else: # root.val > val
        root.left = self.insertIntoBST(root.left, val)
    return root

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0 # 1
        r = len(nums)-1

        while l <= r: # 2
            m = (r + l) // 2 # 3
            if nums[m] < target: # 4
                l = m + 1
            elif nums[m] > target: # 4
                r = m - 1
            else: # 5
                return m
        return -1 # 6

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        c1 = cost[0]
        c2 = cost[1]
        for i in range(2, len(cost)):
            tmp = cost[i] + min(c1, c2)
            c1 = c2
            c2 = tmp
        return min(c1, c2)

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        a = 0
        b = 0
        for i in reversed(range(len(cost))):
            tmp = cost[i] + min(b, a)
            a = b
            b = tmp
        return min(b, a)

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for row in range(len(image)):
            for col in range(len(image[row])):
                if image[row][col] == 1:
                    image[row][col] = 0
                else:
                    image[row][col] = 1
            image[row] = image[row][::-1]
        return image

class Solution:
    def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
        m = len(matrix)
        n = len(matrix[0])
        out = [[None] * m for i in range(n)]
        for row in range(m):
            for col in range(n):
                out[col][row] = matrix[row][col]
        return out

class Solution:
    def buddyStrings(self, s: str, goal: str) -> bool:
        # 2 diff swap: swapped == goal 
        # > 2 diff == false
        if len(s) != len(goal): return False
        if s == goal: 
            if len(s) - len(set(goal)) >= 1:
                return True
            else: 
                return False

        diff = []
        for i in range(len(s)):
            if s[i] != goal[i]:
                diff.append(i)
                if len(diff) > 2:
                    return False

        if len(diff) != 2:
            return False

        if s[diff[0]] == goal[diff[1]] and s[diff[1]] == goal[diff[0]]:
            return True

        return False

def bstToGst(self, root: TreeNode) -> TreeNode:
    # record an ongoing sum to update values accordingly
    self.sum = 0
    self.toGst(root)
    return root

def toGst(self, root):
    # null values requested
    if not root:
        return None
    # right, root, left
    self.toGst(root.right)
    self.sum += root.val
    root.val = self.sum
    self.toGst(root.left)
    # no need to return since we are modifying the tree

    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:        

        horizontalCuts.append(0) # 1
        horizontalCuts.append(h) # 1
        verticalCuts.append(0) # 1
        verticalCuts.append(w) # 1

        horizontalCuts.sort() # 2
        verticalCuts.sort() # 2

        h = 0 # 3
        v = 0 # 3

        for i in range(1, len(horizontalCuts)): # 5
            h = max(h, horizontalCuts[i] - horizontalCuts[i-1])

        for j in range(1, len(verticalCuts)): # 5
            v = max(v, verticalCuts[j] - verticalCuts[j-1])

        return v * h % (10**9 + 7)