Seven Questions Each Day!

Day 2: Breaking Inertia

DONE 7. Validate Binary Search Tree leetcode 98 medium

The approach is recursive. The general idea is that each tree returns its own range to its parent. However, if the tree is not a valid Binary Search Tree (BST), then it will return None, instead.
The base case is a terminal tree (leaf node): This is by definition a valid search tree, and its range is just its own value as minimum and maximum.
The recursive case is an intermediate tree (a non-leaf node): If the tree has a left branch, we get the left branch's range:
- If the returned range is None, then the left tree was invalid: This invalidates also the current tree, so the current tree returns None.
- If instead, the returned range is a valid pair of numbers, then we check the relation between the max of the left tree and the own root's value:
  - If the left.max is equal or worst, greater than the root's value, then the BST got just invalidated and we return None.
  - Otherwise, if left.max is actually strictly less than root.val, then we are good, we just update the minimum on the root's range.
The same idea is applied to the right branch of the root.
Eventually, the root will return its own range (or None). And isValidBST() uses that to determine whether the tree is valid or not.
Finally, the problem says that the tree will always have at least one element. But just for the sake of completeness, if somehow isValidBST() receives a root==None tree, I arbitrarily decided that it will be a valid BST.

 1: # Definition for a binary tree node.
 2: # class TreeNode:
 3: #     def __init__(self, val=0, left=None, right=None):
 4: #         self.val = val
 5: #         self.left = left
 6: #         self.right = right
 7: class Solution:
 8:     class Range:
 9:         def __init__(self, Min, Max):
10:             self.Min = Min
11:             self.Max = Max
12: 
13:     def getTreeRange(self, root: TreeNode) -> Optional[Range]:
14:         myRange = Range(root.val, root.val)
15: 
16:         # If the left tree exists, then we test for correctness and update myRange
17:         # to reflect the minimum of the whole tree.
18:         if root.left != None:
19:             branchRange = self.getTreeRange(root.left)
20:             # if the left tree was incorrect, or the max of the left tree is equal
21:             # or greater than the root's value, then this tree is not a BST
22:             if branchRange == None or branchRange.Max >= myRange.Min:
23:                 return None
24:             myRange.Min = branchRange.Min
25: 
26:         # Same idea with the right tree
27:         if root.right != None:
28:             branchRange = self.getTreeRange(root.right)
29:             if branchRange == None or branchRange.Min <= myRange.Max:
30:                 return None
31:             myRange.Max = branchRange.Max
32: 
33:         return myRange
34: 
35:     def isValidBST(self, root: Optional[TreeNode]) -> bool:
36:         if root == None or self.getTreeRange(root) != None:
37:             return True

Runtime	\(O(n)\)
Memory	\(O(n)\): due to the exec. stack

DONE 6. First Bad Version leetcode 278 easy

Pretty much a binary search. The only difference with the previous problem is that if you get a "hit", that only means that you could have found what you were looking for (the first bad version), or you are testing some far point after the first occurrence. So there is no early return within the loop.
Another thing, after the while loop, we prefer to return early, if this is bad. Otherwise, the only option is late

 1: # The isBadVersion API is already defined for you.
 2: # def isBadVersion(version: int) -> bool:
 3: 
 4: class Solution:
 5:     def firstBadVersion(self, n: int) -> int:
 6:         # cut halves by checking querying the center
 7:         early, late = 1, n
 8:         while early+1 < late:
 9:             mid = early + (late-early)//2
10:             if isBadVersion(mid)
11:                 late = mid
12:             else:
13:                 early = mid
14: 
15:         # check edges
16:         if isBadVersion(early):
17:             return early
18:         else:
19:             return late

Runtime	\(O(\log{n})\)
Memory	\(O(1)\)

DONE 5. Binary Search leetcode 704 easy

The devil is in the details. This one is easy, but attention must be put in some corner cases, like:

What if the list is empty (the statement actually guarantees that it will not, though).
What if the value is in some edge (index 0 or index len(nums)-1).
Can the code generate indices out of bounds?
In python this is not a problem, but in other language (cough cough C) you could incur in an an integer overflow while computing mid. If the array is very very large, then computing (l+r) // 2, in particular l+r, may overflow the size of the integer type, getting esoteric results or lovely Segmentation Fault messages.

Here, l and r are setup in such a way that they always have at least one other element in between, and, if they indeed enter the while loop, they never go out of boundaries.

The consequence of the above is that l, m, and r, are always in total order (l < mid < r). That is why the final check after the while loop makes sense.

 1: class Solution:
 2:     def search(self, nums: List[int], target: int) -> int:
 3:         if nums == None or len(nums) == 0:
 4:             return -1
 5: 
 6:         # check internals by partitioning
 7:         l, r = 0, len(nums) - 1
 8:         while l + 1 < r:
 9:             mid = l + (r-l)//2
10:             if target == nums[mid]:
11:                 return mid
12:             elif target < nums[mid]:
13:                 r = mid
14:             else: # target > nums[mid]:
15:                 l = mid
16: 
17:         # check edges
18:         if target == nums[l]:
19:             return l
20:         if target == nums[r]:
21:             return r
22:         return -1

Runtime	\(O(\log{n})\)
Memory	\(O(1)\)

DONE 4. Binary Tree Level Order Traversal leetcode 102 medium

This problem is very similar to the previous one, but it has two twists:

We descend by levels instead of depth-first
We return a "list of lists": one list per level of the tree.

Let's agree in some names:

uncles: the nodes in a given level.
children: the descendants of a particular uncle.
nephews: all the nodes in the next level.

To solve the first issue, we will use a queue instead of a stack. This changes the traversing direction because each uncle puts their own children behind whatever there is in the queue already. So no nephew is read from the queue until all uncles are read first.

To solve the "one list per level" thing, we will, instead of using just one queue, we will use two: uncles and nephews.

Read nodes from uncles.
Append the uncle's value in a list level_vals.
Enqueue this uncle's children to nephews.
Repeat from 1.

Once uncles becomes empty, that means that level_vals has the values of this level. So:

Append level_vals to the answer list.
Assign a new empty list to the name "level_vals".
Swap the lists' names uncles and nephews, as the first one is empty, and the second one has a full generation of kids on it!
Now start again from 1.

We finish when, after swapping the names, uncles is empty.

 1: # Definition for a binary tree node.
 2: # class TreeNode:
 3: #     def __init__(self, val=0, left=None, right=None):
 4: #         self.val = val
 5: #         self.left = left
 6: #         self.right = right
 7: class Solution:
 8:     def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
 9:         if root == None:
10:             return []
11:         uncles = [root]
12:         answer = []
13:         while len(uncles) > 0:
14:             nephews = []
15:             level_vals = []
16: 
17:             # passing through one generation.
18:             while len(uncles) > 0:
19:                 dady = uncles.pop(0)
20:                 level_vals.append(dady.val)
21:                 if dady.left != None:
22:                     nephews.append(dady.left)
23:                 if dady.right != None:
24:                     nephews.append(dady.right)
25:             answer.append(level_vals)
26:             uncles, nephews = nephews, uncles
27: 
28:         return answer

Runtime	\(O(n)\)
Memory	\(O(n)\)

DONE 3. N-ary Tree Pre-order Traversal leetcode 589 easy

Recursive Solution

The recursive approach is not difficult to obtain, however, there are some little interesting aspects.
I could have just used preorder() as a recursive function, but I defined a new one called preorder_rec(), this is because of the return value: If I used the original function, then each level will have to collect the work of their children and extend their own result with the bits obtained from the children.
That is unnecessary. Instead, a unique list preorder_list can be created as a Solution's class member, so each level can directly access it.
Additionally, we could start with a list of at least 1000 elements, so the array doesn't have to be updated every time a new element is inserted. The upside of this is gaining some speed, the downside is that even if the tree has 1 node, the code will reserve a list for 1000 values, which may be a waste. Choose your flavor…

 1: """
 2: # Definition for a Node.
 3: class Node:
 4:     def __init__(self, val=None, children=None):
 5:         self.val = val
 6:         self.children = children
 7: """
 8: class Solution:
 9:     # Recursive Solution
10:     def __init__(self):
11:         self.preorder_list = []*1000
12: 
13:     def preorder_rec(self, root: 'Node') -> None:
14:         self.preorder_list.append(root.val)
15:         for c in root.children:
16:             self.preorder_rec(c)
17:         return
18: 
19:     def preorder(self, root: 'Node') -> List[int]:
20:         if root != None:
21:             self.preorder_rec(root)
22:         return self.preorder_list

Runtime	\(O(n)\)
Memory	\(O(n)\)

Iterative Solution

A stack is created to store nodes. The first to put is the root.
This is the algorithm:
1. Pop a node from the stack (into curr_node).
2. Save its value on the list to be returned.
3. Take its children and push them to the queue in reversed order.
4. Repeat from step 1.
By doing this, we always "go down" following the child of the child of the child…. of the first node. This is effectively a depth-first search.

 1: """
 2: # Definition for a Node.
 3: class Node:
 4:     def __init__(self, val=None, children=None):
 5:         self.val = val
 6:         self.children = children
 7: """
 8: 
 9: class Solution:
10:     # Iterative Solution
11:     def preorder(self, root: 'Node') -> List[int]:
12:         if root == None:
13:             return []
14:         expansion_stack = [root]
15:         preorder_list = []
16:         while len(expansion_stack) > 0:
17:             curr_node = expansion_stack.pop()
18:             preorder_list.append(curr_node.val)
19:             expansion_stack.extend(reversed(curr_node.children))
20: 
21:         return preorder_list

Runtime	\(O(n)\)
Memory	\(O(n)\)

DONE 2. Longest Palindrome leetcode 409 easy

Just count the pairs found (I use a set for that).
If the character has not been seen before, add it. If it is in the set, (it has been seen before), then increment the pairs_found counter, and remove the character from the set.
At the end, you have pairs_found pairs of characters to make your biggest palindrome, BUT remember that palindromes can also have a unique character in the very center. So check if there is any element in the set, If so, one can use any of them to put in the center. If the set is empty, then there is no character left to put in the center.
Finally, return 2 * pairs_found + center_char, where center_char is 1 or 0.

 1: class Solution:
 2:     def longestPalindrome(self, s: str) -> int:
 3:         char_pairs = set()
 4:         pairs_found = 0
 5:         for c in s:
 6:             if c in char_pairs:
 7:                 pairs_found += 1
 8:                 char_pairs.remove(c)
 9:             else:
10:                 char_pairs.add(c)
11:         center_char = 1 if len(char_pairs) > 0 else 0
12: 
13:         return 2 * pairs_found + center_char

Runtime	\(O(n)\)
Memory	\(O(n)\)

DONE 1. Best Time to Buy and Sell Stock leetcode 121 easy

This is greedy: the idea is to traverse the array and keep track of the smallest price so far, and to check what would the profit be if I sell the stock today.
More precisely, we initialize the variables best_buy and best_profit with their worst possible values.
Then we just run through the list reading one element day_price at the time:
1. If day_price is smaller than the minimum seen so far, then update the minimum registered.
2. If, instead, day_price is NOT smaller, then we don't attempt to update best_buy, instead, there is profit if we sell today. So we check whether selling today would yield a better profit than what we have seen so far. If so, then update your best_profit, otherwise, keep the current.
3. After doing this test, and perhaps update, just get the next element and repeat from (1.).

 1: class Solution:
 2:     def maxProfit(self, prices: List[int]) -> int:
 3:         best_buy = float('inf')
 4:         best_profit = 0
 5: 
 6:         for day_price in prices:
 7:             if day_price < best_buy:
 8:                 best_buy = day_price
 9:             elif (day_price - best_buy) > best_profit:
10:                 best_profit = day_price - best_buy
11:         return best_profit

Runtime	\(O(n)\)
Memory	\(O(1)\)

Day 1: Let's go!

DONE 7. Linked List Cycle II leetcode 142 medium

This Problem uses Floyd's "Tortise and Hare" Cycle finding algorithm.
Basically, we put two pointers "slow" and "fast" at the same location: head.
Slow advances one node at the time, and Fast advances two. (Be careful with de-referencing None pointers).
If there is no loop, then the fast pointer will find that its own next node is None. Fast pointer will see this before the slow pointer.
But, as the algorithm states, if for a second time (the first was in head) slow and fast are in the same spot, then there must be a cycle. It is quite intuitive.
The second part of the algorithm is more interesting, it states that: if you put a pointer p1 at the meeting point between fast and slow, and another p2 at head, and make both of them advance one node at the time, they will meet at the entrance of the loop. Always!

 1: # Definition for singly-linked list.
 2: # class ListNode:
 3: #     def __init__(self, x):
 4: #         self.val = x
 5: #         self.next = None
 6: 
 7: class Solution:
 8:     def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
 9:         slow_ptr = fast_ptr = head
10: 
11:         # If a pointer reaches None, then the list has an exit, so no loops.
12:         while fast_ptr != None \
13:               and fast_ptr.next != None:
14:             slow_ptr = slow_ptr.next
15:             fast_ptr = fast_ptr.next.next
16: 
17:             # If fast_ptr catches slow_ptr from behind, then there must be a loop.
18:             if slow_ptr == fast_ptr:
19:                 break
20: 
21:         # if while loop ended because of end-of-list, then there is no loop.
22:         if fast_ptr == None or fast_ptr.next == None:
23:             return None
24: 
25:         # Otherwise, there is a loop!! Now find the entrance to it.
26:         # There is no need to check for None because we already know that
27:         # there is no end in this list.
28:         # This will not be an infinite loop because of math! the pointers
29:         # are guaranteed to meet at the entrance.
30:         slow_ptr2 = head
31:         while slow_ptr != slow_ptr2:
32:             slow_ptr = slow_ptr.next
33:             slow_ptr2 = slow_ptr2.next
34: 
35:         return slow_ptr

Runtime	\(O(n)\)
Memory	\(O(1)\)

DONE 6. Middle of the Linked List leetcode 876 easy

In a while loop, I make two pointers run through the list.
fast_ptr moves to the next in every loop, and slow_ptr does it only in odd loops (first loop is odd).
It is important to move slow_ptr in odd rather than even loops, because if the list has an even number of elements, moving slow_ptr only in even loops, would give us the first of the two middle nodes.

 1: # Definition for singly-linked list.
 2: # class ListNode:
 3: #     def __init__(self, val=0, next=None):
 4: #         self.val = val
 5: #         self.next = next
 6: class Solution:
 7:     def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
 8:         if head == None:
 9:             return None
10:         slow_ptr = fast_ptr = head
11:         odd_loop = True
12:         while fast_ptr.next != None:
13:             fast_ptr = fast_ptr.next
14:             # move slow_ptr only in odd loops
15:             if odd_loop:
16:                 slow_ptr = slow_ptr.next
17:             odd_loop = not odd_loop
18:         return slow_ptr

Runtime	\(O(n)\)
Memory	\(O(1)\)

DONE 5. Reverse Linked List leetcode 206 easy

Let's think about the original list as something like this: a--> b--> ... m--> n--> ... --> None.
This list will be divided in two partitions: The Original list (orig_head), and the New list (new_list). The Original will shrink removing one element at the time from its beginning. The New will grow adding one element at the time to its beginning.
At some point the lists will look like this: New: None <--a <--b <--c ... <--m. Original: n--> o--> p--> ... --> None.
Note that the assignment before looping new_head.next = None is to signal the end of the new list.
In the loop, if orig_head is None, this means that we reached the end of the original list, therefore, the reversing is done, and already attached to new_head=.
But if orig_head actually is a node, then we take that node and put it at the beginning of the new list.

 1: # Definition for singly-linked list.
 2: # class ListNode:
 3: #     def __init__(self, val=0, next=None):
 4: #         self.val = val
 5: #         self.next = next
 6: class Solution:
 7:     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
 8:         if head == None:
 9:             return None
10: 
11:         new_head = head
12:         orig_head = head.next # maybe None
13:         new_head.next = None # the ending of the new list
14:         # None <--nh    h--> ...--> None
15:         while orig_head != None:
16:             temp_head = orig_head
17:             orig_head = orig_head.next # maybe None
18:             # None <--nh   th--> h--> ...--> None
19: 
20:             temp_head.next = new_head
21:             # None <--nh <--th    h--> ...--> None
22: 
23:             new_head = temp_head
24:             # None <--?? <--nh    h--> ...--> None
25: 
26:         return new_head

Runtime	\(O(n)\)
Memory	\(O(1)\)

DONE 4. Merge Two Sorted Lists leetcode 21 easy

Out of the two lists list1 and list2, we put the one that starts smallest in list_runner, and the other in list_insert.
We walk through list_runner and stop when the pointer is on the last element smaller or equal than the one on list_insert.
We create an after_cut pointer to the next one in list_runner, and insert the whole list_insert at list_runner.next.
Now we use list_insert as the new list_runner, and after_cut as the new list_insert.
We repeat the steps from 2.
Considerations and corner-cases:
1. If one of the lists is empty, then the work is trivial: the other list is the solution.
2. If we walk to the very end of list_runner (as in step 2.), whatever is reminder from list_insert, is appended at the end of list_runner

 1: # Definition for singly-linked list.
 2: # class ListNode:
 3: #     def __init__(self, val=0, next=None):
 4: #         self.val = val
 5: #         self.next = next
 6: class Solution:
 7:     def mergeTwoLists(self,
 8:                       list1: Optional[ListNode], \
 9:                       list2: Optional[ListNode]) \
10:                       -> Optional[ListNode]:
11:         if list1 == None:
12:             return list2
13:         if list2 == None:
14:             return list1
15: 
16:         # let list1 be the one with the smallest (or equal) starting
17:         # value out of the two lists.
18:         list_runner,list_insert = (list1,list2) \
19:             if list1.val < list2.val \
20:                else (list2,list1)
21:         ans = list_runner
22: 
23:         # breaks when there is nothing else to insert in list_runner.
24:         while list_insert != None:
25:             # list_runner points to its furthest element smaller or equal
26:             # than value at list_insert. After this while loop, list_runner
27:             # is at the end of its contiguous segment. Between
28:             # list_runner and list_runner.next, a portion of list_insert
29:             # will be inserted.
30:             while list_runner.next != None and \
31:                   list_runner.next.val <= list_insert.val:
32:                 list_runner = list_runner.next
33: 
34:             # means that we reached the end of list_runner and still the
35:             # last element was smaller or equal than the current in
36:             # list_insert. Therefore, we just append the whole list_insert
37:             # at the end of list_runner.
38:             if list_runner.next == None:
39:                 list_runner.next = list_insert
40:                 break
41: 
42:             # ――――――――lr――lrac―――――
43:             # li―――――――
44:             list_runner_after_cut = list_runner.next
45: 
46:             # ――――――――lr┐ lrac―――――
47:             #           └―li―――――――
48:             list_runner.next = list_insert
49: 
50:             # ――――――――――┐ li―――――――
51:             #           └―lr―――――――
52:             list_runner,list_insert = list_insert,list_runner_after_cut
53: 
54:         return ans

Runtime	\(O(n)\)
Memory	\(O(1)\)

DONE 3. Is Sub-sequence leetcode 392 easy

Here I am thinking that if many sub-sequences s are going to be searched in the same t then it may be a good idea to make a dictionary with "the first occurrence of each character of t", then, each subsequent search would be just checking that the indices obtained from the dictionary go in ascending order… hold on… This does not handle repetitions. Scratch that.
I will grab the first char of the sub-sequence candidate s, and start traversing t. If I find my character, then I grab the next one in s, and keep searching starting from the very next one in t.
There are some special cases:
- If s is empty, then it is always a sub-sequence.
- If t is empty, then only s="" is sub-sequence.
- If len(s)>len(t), then s cannot be sub-sequence of t.

 1: class Solution:
 2:     def isSubsequence(self, s: str, t: str) -> bool:
 3:         # corner cases
 4:         if len(s) == 0:
 5:             return True
 6:         if len(t) < len(s):
 7:             return False
 8: 
 9:         # to indices traverse s and t
10:         i, j = 0, 0
11:         while (i < len(s) and j < len(t)):
12:             if (s[i] == t[j]):
13:                 i += 1
14:             j += 1
15: 
16:         # check if the s was totally covered
17:         if (i == len(s)):
18:             return True
19:         else:
20:             return False

Runtime	\(O(n)\)
Memory	\(O(1)\)

DONE 2. Isomorphic Strings leetcode 205 easy

Here I am using a "bilingual" dictionary (forward_dict for \(s \rightarrow t\), and backward_dict for \(t \rightarrow s\).
The idea is that if a character si maps to ti in forward_dict, then backward_dict must have a mapping from ti to si, and vice versa.
If a mapping is not found, and because it is factual that si \(\leftrightarrow\) ti, then each mapping is added to its corresponding dictionary.

 1: class Solution:
 2:     def isIsomorphic(self, s: str, t: str) -> bool:
 3:         forward_dict = {}
 4:         backward_dict = {}
 5: 
 6:         # diff lenghth breaks isomorphism.
 7:         if len(s) != len(t):
 8:             return False
 9: 
10:         # It must be that: si -> ti and ti -> si
11:         for si,ti in zip(s,t):
12:             if si in forward_dict:
13:                 # if si->tj, then si->ti and si->tj; not isomorphic
14:                 if forward_dict[si] != ti:
15:                     return False
16:             else:
17:                 forward_dict[si] = ti
18: 
19:             if ti in backward_dict:
20:                 if backward_dict[ti] != si:
21:                     return False  
22:             else:
23:                 backward_dict[ti] = si
24:         return True

Runtime	\(O(n)\)
Memory	\(O(n)\)

DONE 1. Find Pivot Index leetcode 724 easy

An idea that leads to \(O(n)\) exec. time is to add-up everything in a variable total, so we know what is the total sum of the whole array nums.
Then, go back to the beginning and traverse one by one and carrying a left_sum initialized in 0 .
In each iteration, I compute right_sum = total - left_sum - nums[i] and check if left_sum is equal to right_sum.
If they are equal, I return the index. If not, the pivot candidate arr[i] is added to left_sum.
The numbers can be negative, so even if left_sum becomes bigger than right_sum, there is still a chance of going back to a balanced state.

 1: class Solution:
 2:     def pivotIndex(self, nums: List[int]) -> int:
 3:         total = sum(nums)
 4:         left_sum = 0
 5:         for i,piv in enumerate(nums):
 6:             right_sum = total - left_sum - piv
 7:             if left_sum == right_sum:
 8:                 return i
 9:             left_sum += piv
10:         return -1

Runtime	\(O(n)\)
Memory	\(O(1)\)

Day 0: Get your lazy ass started!

DONE 1. Running Sum of 1d Array leetcode 1480 easy

Easy warm-up, carry the sum in a variable last_sum, and in every iteration, put its current value in the array to return.

1: class Solution:
2:     def runningSum(self, nums: List[int]) -> List[int]:
3:         rsum = []
4:         last_sum = 0
5:         for x in nums:
6:             last_sum += x
7:             rsum.append(last_sum)
8:         return rsum

Runtime	\(O(n)\)
Memory	\(O(n)\)