leetcode_may8_24 Flashcards
2 sum: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
2 sum — want to add 2 number and see if they’re in target. One way to sort it and use 2 pointers but this is 2 sum II is the input is sorted. If its not sorted you basically need to go through each element in the list and see if the element you need to sum it to target is present in the array, search of the array is achieved by pushing every element you visit into a dictionary or set and making checking if the element you need is already there. Push into set only after you visit each element not before. If target is 6 and first element is 3 you don’t want to push 3 into dictionary first and then look in dictionary to find it and say you’ve got a match.
2 sum II: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. Input Array Is Sorted
2 sum II — since input is sorted 2 pointers make the most sense here. Start from the 2 ends of the array and compare the sum with target. If the sum is larger then reduce the high pointer and if the target is larger then increase the left low
pointer.
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers)-1
while l numbers[l]:
l += 1
elif target - numbers[l] < numbers [r]:
r -= 1
3 sum: 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. !!!!Notice that the solution set must not contain duplicate triplets!!!!
3 sum — pretty much an extension to 2 sum. I don’t like neetcode’s solution. What I did instead of iterate through the loop and each time look at the rest of the array as a 2 sum problem with target being negative of the hook element you’re iterating throughh.
But the efficient solution is to sort the array and then iterate through the loop to get a pivot element and then do 2 sum II on the elements in the array after pivot element and figure out which 2 elements add to sum. move pointer based on if sum is greater than or less than target which is negative of pivot element. To get unique elements skip over repeat elements.
Basically breaks the problem into a 2 sum with different target. add to set() to make sure no duplicates.
def threeSum(self, nums: List[int]) -> List[List[int]]:
result = set()
visited = set()
for i in range(len(nums)):
if nums[i] in visited:
continue
visited.add(nums[i])
two_sum = set()
for j in range(i+1, len(nums)):
if -nums[i] - nums[j] in two_sum:
srtd_set = sorted([nums[i],nums[j],-nums[i]-nums[j]])
result.add(tuple(srtd_set))
two_sum.add(nums[j])
return [[i,j,k] for (i,j,k) in result]
Two Pointers
(3 / 5)
Prerequisites
Two Pointers
Advanced Algorithms
Status
Star
Problem
Difficulty
Video Solution
Code
Valid Palindrome
Two Sum II Input Array Is Sorted
3Sum
Container With Most Water
Trapping Rain Water
View on Github
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i, a in enumerate(nums):
# Skip positive integers
if a > 0:
break
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
r -= 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res Select Roadmap
(30 / 150)
Valid anagram: Given two strings s and t, return true if t is an anagram of s, and false otherwise. Can’t use sorting.
Valid anagram - Want to check if 2 strings have all the same alphabets and the same counts basically so you create a dictionary and add elements based on one string and subtract based on another, if not equal then its not an anagram.
Contains Duplicate: 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.
Contains Duplicate - check for duplicate in a list. Another simple Hashmap implementation will do.
Group Anagrams: Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
Example 2:
Group Anagrams - good rule of thumb for any grouping or similarity question is to try and hash it I think. Anyways for this one sorting each string in a new array and then hashing them with the index gives you location of similar string in the original array. After that all you need to do is create the answer. Can hash without sorting to avoid nlogn complexity if needed. See code below:
class Solution:
def hashify(self, string):
hash_list = [0]*26
for char in string:
hash_list[ord(char)-ord(‘a’)] += 1
hash_str = “”
for ele in hash_list:
hash_str+= str(ele) + ‘#’
return hash_str
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result_map = {}
for string in strs:
str_sorted = self.hashify(string)
if str_sorted in result_map:
result_map[str_sorted]+= [string]
else:
result_map[str_sorted] = [string]
return [result_map[key] for key in result_map]
Top K freq elements: Given an integer array nums and an integer k, return the k most frequent elements. Do it in O(n) time.
You gotta do it in O(n). first solution that come to mind is prolly to put elements with count into dictionary and then sort dict.items() according to count and print top k elements. but the sorting is O(nlogn). Instead to do it in O(n) you take the dictionary with count and create a count array of size len(input_array)+1 and then at each index element put a list of numbers that have count as many as index. which means if there are 3 1’s and 3 2’s in your input then at index 3 in count array you’ll have [1,2].
Product of Array Except Self
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]. You must write an algorithm that runs in O(n) time and without using the division operation.
You need to create 2 array by scanning through the input array twice. One is prefix with product of every element before itself at the corresponding index position and another array postfix where you scan through the array in reverse and have the product of every element after the index at corresponding index position. You can make it more efficient by directly creating answer arrat while calculating postfix.
Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Put all elements in a set. iterate through the input array;
Good solution: you check if ele - 1 exists in the set if so you don’t start counting, this means that ele is part of a longer sequence which will get counted later. You start counting only if ele-1 is not in the set.
Not as good solution but still works: you find a possible start for every sequence by checking if the next number exists in the array for every element in the array (or more efficiently checking If num + max_count exists in the array) this tells us whether its worth it to check if all consecutive elements exist in the array. you check for how many consecutive elements exist for such a case and track that count and return max_count.
def longestConsecutive(self, nums: List[int]) -> int:
nums_set = set(nums)
result = 0
for num in nums_set:
seq_len = 1
if num+result in nums_set:
while num+1 in nums_set:
seq_len+=1
num+=1
result = max(result, seq_len)
return result
Valid Palindrome: check if a string is valid palindrome. have to ignore all non-alphanumeric characters while checking. need to be case insensitive. (do you remember functions to convert string to lowercase and to check if string is alphanumeric)?
two pointers from both ends of the string and keep checking for similarity. str.lower() converts str to lowercase and returns it. str.isalnum() return true/false depending on if alphanumeric.
class Solution:
def isPalindrome(self, s: str) -> bool:
start = 0
end = len(s) - 1
while start < end:
while (not s[start].isalnum()) and start
Container With Most Water
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.
you start 2 pointers at 0 and len(heights) - 1 as this is what maximises width in height*width = area, then you want to reduce width only if that can increase height and possibly then increase area. So you find which of l and r pointers in minimum and move it. You keep doing this and then return max_area hence obtained.
start from both ends of the array with pointers and move the pointer with the lesser height while storing volume at each stage along the way as width * min(left_pointer_height, right_pointer_height). You’re moving the limiting factor value pointer
some intuition: You’re always moving the limiting factor, which is why even if there’s a much larger wall ahead of the maximum of the 2 container walls it doesn’t make sense to choose that because all you’ll be doing is reducing width without increasing height. for example if there is [5, 15, 2, 3, 4, 3] when you’re first at 5 and 3 it makes sense to move 3 and look for a higher wall, the fact that you have 15 in front of 5 doesn’t change the volume as it’ll be 3*width anyways even if the other wall is 5 or 15.
#start with two pointers at both ends of the array and move the one which is the limiting factor as there's no
#point in moving the one which isn't even to a possibly higher position.
Best Time to Buy and Sell Stock
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.
you start with creating 2 pointers to note 2 values, one is min value in array and other is curr_price pointer. As you iterate through the loop if your curr_price is less than min_price then you update min_price to be there and keep calculating profit as curr_price - min_price. You return maximum when you’re done iterating through the loop. This makes sense as you basically want to buy lowest and sell highest after lowest. you keep updating lowest as you traverse the array and calculate profit at every price after that and return the maximum hence obtained.
best way to think about this is you want to find the minimum buying point and maximum selling point. If you have 2 pointers l and r, where r is your selling point for every r you want the minimum l before it. so start with l and r at 0 and 1 and then keep pushing r forward with l being the minimum before r which can be set by making l=r when nums[r] < nums[l]. This works as if we find a point less than min as we traverse an array we should have bought then as for a max price after it this makes sense. If the best min and max price were before this new min then that has already been recorded in max_price which we update for every new sliding window
def maxProfit(self, prices: List[int]) -> int:
min_price = 0
max_profit = 0
for i in range(1, len(prices)):
max_profit = max(max_profit, prices[i] - prices[min_price])
if prices[min_price] > prices[i]:
min_price = i
return max_profits
Longest Substring Without Repeating Characters.
Given a string s, find the length of the longest substring without repeating characters.
sliding window with 2 pointers.
you want to start with 2 pointers that start at the beginning of the list and as you increment the right pointer see if the new element is there in your window (use a set for this) and if its there, pop your left pointer value from set and increment you left pointer until you can add right and still have all unique elements. this should give you max_len.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
unique_set = set()
start = 0
end = 0
max_len = 0
while end < len(s):
if s[end] not in unique_set:
unique_set.add(s[end])
end += 1
else:
unique_set.remove(s[start])
start += 1
max_len = max(max_len, len(unique_set))
return max_len
Longest Repeating Character Replacement
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.
Return the length of the longest substring containing the same letter you can get after performing the above operations.
The main challenge here is that you not only need to use a sliding window (as you’re looking to analyse consecutive elements) to keep track of the substring but you also need to make sure that window is valid wrt the condition that if you replace k characters in the window it’ll have only 1 character.
main ideas:
1. keep track of window with dictionary and count variable for number of elements in it.
2. remember that the condition for validity is count - max(dict.values) <= k.
you push the element at hi into the window and check for validity. if valid you update max_window else you reduce window length
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
lo, hi = 0, 0
hmap = {}
# window = 1
max_window = 0
while hi < len(s):
hmap[s[hi]] = hmap.get(s[hi], 0) + 1
if hi-lo+1 - max(hmap.values()) <= k:
max_window = max(max_window, hi-lo+1)
else:
hmap[s[lo]] -= 1
lo += 1
hi += 1
return max_window
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
lo, hi = 0, 0
hmap = {}
max_window = 0
while hi < len(s):
hmap[s[hi]] = hmap.get(s[hi], 0) + 1
while hi-lo+1 - max(hmap.values()) > k:
hmap[s[lo]] -= 1
lo += 1
max_window = max(max_window, hi-lo+1)
hi += 1
return max_window
Minimum Window Substring
Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
Fix code in solution maybe try doing
slide through the string with 2 pointers, keep checking for a valid window by putting elements into a dictionary and checking if the dictionary has required elements. if invalid: increase the right pointer to make the window bigger, if valid: increase the left pointer to decrease the window size as we want smallest array.
main ideas:
1. checking sliding window validity and increasing and decreasing size based on it so as to get smallest match. Here you have to be careful about while condition as you loop to find window. have a look at the solution while and if conditions below.
- neetcode video has a more optimum solution where when you check for validity only care about characters in target string and keep a global match count which you can look at and update to check for match instead of iterating through the keys in the dictionary every time .
class Solution:
def isSubset(self, s_map, t_map):
for key, value in t_map.items():
if key not in s_map or s_map[key] < value:
return False
return True
def minWindow(self, s: str, t: str) -> str:
if len(s) r-l-1:
mws = s[l:r]
s_map[s[l]] -= 1
l+=1
else:
if r == len(s):
break
s_map[s[r]] = s_map.get(s[r], 0) + 1
r += 1
return mws
Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Use a stack. Can use a dictionary to keep track of close to open relations.
push all opening braces into stack and when you get a closing brace the last element in stack should be the corresponding closing which you pop.
Code:
def isValid(self, s: str) -> bool:
stack = []
ele_map = {'{':'}', '[':']', '(':')'}
for ele in s:
if ele in ele_map:
stack.append(ele)
elif len(stack) and ele_map[stack[-1]] == ele : \\ here order of logical boolean evaluation matters!!
stack.pop()
else:
return False
return not len(stack)
Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Fix code in solution maybe implement
if right half is sorted minimum won’t be there except maybe the first element
Simple condition which is to check if mid is less than hi if so right half is the sorted half. so move hi to mid as that could be the minimum. else left half is sorted lo = mid+1 as minimum can’t be the last element of sorted element
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums)-1
while lo nums[lo]
lo = mid + 1
return nums[hi]
Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Finding pivot and then doing binary search is too complex.
Instead the thing to do is find in one loop:
there are 3 possible cases after comparing target with nums[mid]:
Case 1. If nums[mid] = target,
Case 2. If nums[mid] >= nums[left]. It implies that the left subarray nums[left ~ mid] is sorted. We can determine whether to proceed with this subarray by comparing target with the boundary elements:
If nums[left] <= target and target < nums[mid], it suggests that the sorted left half might include target while the other half does not contain target. Consequently, we focus on the left half for further steps.
Otherwise, the left half is guaranteed not to contain target, and we will move on to the right half.
Case 3. If nums[mid] < nums[left], it implies that the left subarray is rotated and the right subarray nums[mid ~ right] is sorted. Therefore, we can determine whether to proceed with the right subarray by comparing the target with its boundary elements:
If nums[mid] < target and target < nums[right], it implies that the sorted right half might contain target. As a result, we will move on with the right half.
Otherwise, the right half is guaranteed not to contain target, and we will move on to the left half.
this makes the solution a lot easier, go through the code
def search(self, nums: List[int], target: int) -> int:
#first find index of sorted portion with target in it
lo, hi = 0, len(nums) - 1
while lo<=hi:
mid = (lo+hi)//2
# print(lo, hi, mid)
if nums[mid] == target:
return mid
elif nums[mid] < nums[hi]:
if target > nums[mid] and target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
else:
if target < nums[mid] and target >= nums[lo]:
hi = mid - 1
else:
lo = mid + 1
return -1
Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list.
take 2 variable and go through with a while loop and swap pointers around.
the recursive way to do it is a lil involved and non intuitive you have to one see that you have to send the end of the list in the return of the recursive call so it needs to travel back and as its being sent back you need to point node.next.next = node to reverse a link and then put node.next = None mostly to put first element in linked list to None when returning. There’s a video in the leetcode solution top comments thats very good. https://youtu.be/S92RuTtt9EE
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if (not head) or (not head.next):
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_temp = curr.next
curr.next = prev
prev = curr
curr = next_temp
return prev
Merge Two Sorted linked Lists
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.
create a tail and dummy, dummy for result and tail to keep track of where you are in the combined list
decide which has the smaller start and calling that the start. then keep adding to it depending on who is smaller through a loop. append whatever is leftover and return.
look at code its non-trivial to code this up
def merge2(self, head1, head2):
tail = ListNode()
dummy = tail
while head1 and head2:
if head1.val
Reorder List
You are given the head of a singly linked list. The list can be represented as follows:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Add code and maybe do
Though not necessary for a valid solution, it introduces the concept of a slow and fast pointer.
Easy: use a list to store elements and then just pointer manipulation. this is O(n) time and O(n) space.
O(1) space solution: this has 3 parts one is finding end and mid of the linkedlist using a fast and slow pointer. Second is reversing the second half of the linked list. Third is merging the 2 halves.
Remove Nth Node From End of List
Given the head of a linked list, remove the nth node from the end of the list and return its head.
use concept of 2 pointers seperated by n nodes.
so you start with a dummy node and a left pointer pointing to it. then you send another right pointer ahead of dummy by n nodes. then you push out both pointers till right pointer reaches end of the linked list. At this point left pointer is pointing at node that needs to be modified to remove nth node from linked list. it’s important to think about dummy node as else you mess up edge cases.
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
l = dummy
r = head
for _ in range(n-1):
r = r.next
while r.next:
r = r.next
l = l.next
l.next = l.next.next
return dummy.next
Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
simple solution is to use set but that’s o(n) space.
better to use floyd’s algorithm ie use fast and slow pointer and know that they will intersect in the loop. floyd’s algo is from the find the looping element question.
For this question all you need to do is start and slow and fast pointer if they meet there’s a loop if fast reaches a None there’s no loop.
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
intuitive solution of going double looping to go through every starting element of each of the lists to pick up the smallest and adding that to solution one by one works.
1. need to keep track of index to remove the right element.
2. need to handle some edge cases of empty lists in input.
But this is O(n*k) time, there’s a better O(nlogk) solution where the main idea is you merge in pairs of 2 cutting down the number of merges to logk time
Look at code its non trivial to code this up
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists: # Check if the list is empty or all elements are None
return None
while len(lists) > 1:
mergedLists = []
for i in range(0, len(lists), 2):
list1 = lists[i]
list2 = lists[i+1] if i+1 < len(lists) else None
mergedLists.append(self.merge2(list1, list2))
lists = mergedLists # Update lists to be the merged lists for the next iteration
return lists[0] # After merging, the final merged list is the first element
def merge2(self, head1, head2):
tail = ListNode()
dummy = tail
while head1 and head2:
if head1.val
Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
simple recursive call will do use the same function as the solution definition. base case is if root is None
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root
iterative solution uses queue:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
Try iterative dfs
Maximum Depth of Binary Tree
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.
—–what is the data structure to do iterative BFS and iterative DFS? how do you do pop and push in each?
simple recursive solution.
base case is if root is None.
add one every recursive step. return max of recursive returns from left and right.
can be done with iterative DFS and iterative BFS using a deque data structure in python.
DFS = stack
BFS = queue
q= collections.deque()
q.append()
q.pop()
q.popleft()
#recursive
if root== None:
return 0
max_d = 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
return max_d
# # BFS:
# if not root: return 0
# q = deque()
# q.append(root)
# depth = 0
# while q:
# for i in range(len(q)):
# ele = q.popleft()
# if ele:
# q.append(ele.left)
# q.append(ele.right)
# depth += 1
# return depth-1
# # DFS
# if not root: return 0
# stack = [[root, 1]]
# maxd = 1
# while len(stack):
# node, depth = stack.pop()
# if node:
# stack.append([node.right, depth+1])
# stack.append([node.left, depth+1])
# maxd = max(maxd, depth)
# # return maxd-1
Same Tree
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.
recursive solution. keep checking if val is the same for both by iterating through the tree the same way
can also use stack here:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
#DFS
p_stack = [p]
q_stack = [q]
while p_stack and q_stack:
p_node = p_stack.pop()
q_node = q_stack.pop()
if p_node== None and q_node == None:
continue
elif p_node == None or q_node == None:
return False
elif p_node.val != q_node.val:
return False
p_stack.append(p_node.left)
p_stack.append(p_node.right)
q_stack.append(q_node.left)
q_stack.append(q_node.right)
return True
Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
iteratively go to every node in the tree and check if the tree with that node as root is the same as the subRoot tree.
checking if 2 trees are the same can also be done recursively.
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def isSame(root1, root2):
if root1 == None and root2 == None:
return True
elif root1 == None or root2 == None:
return False
if root1.val == root2.val:
return isSame(root1.left, root2.left) and isSame(root1.right, root2.right)
else:
return False
return isSame(root, subRoot)\
or (self.isSubtree(root.left, subRoot) if root.left else False) \
or (self.isSubtree(root.right, subRoot) if root.right else False)
Validate Binary Search Tree
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
can be solved recursively by checking if tree from a given node is valid.
But main idea here is that we don’t check from bottom to top we check from top to bottom by passing the min and max restrictions of that node which it inherits from its parents.
Right node will inherit parents max restriction and will have a min restriction parents value. Similarly left child will inherit the parents min restriction and will have a max restriction of parents value.
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def isValid(root, pmin, pmax):
if root == None:
return True
return root.val>pmin and root.val
Diameter of Binary Tree
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
main idea is you gotta work from the bottom to the top of the tree. You return up both the max child height and diameter from every node.
the max child height is max of left and right child height plus 1 and diameter is max of right, left diameter and the right height plus left height.
Balanced Binary Tree
Given a binary tree, determine if it is
height-balanced
.
write a recursive function to which returns both the height from a node and whether the tree from that node is balanced.
the base case is height is 0 and true for balance validity.
the update rule is height is 1+ max of left and right height, its valid if both right and left are valid and height condition is met (difference is less than or equal to 1)
Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
tree = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
—- what data structure do you use and how?
you have to use a queue but since you want all elements in one level to be put in a list separately you have to use a for loop to pop all the elements in the queue at one time and then append all their children together for the next iteration and you wrap this for loop in a while loop which continues till queue is empty.
class Solution:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
q = collections.deque()
if root:
q.append(root)
while q:
val = []
for i in range(len(q)):
node = q.popleft()
val.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
res.append(val)
return res
LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
obj = LRUCache(capacity)
There is simpler code but using double linked list is best. Create a ListNode and in LRUCache class you need init, get, put, add add and remove
class ListNode:
def \_\_init\_\_(self, key= -10, val = -10, next1 = None, prev = None):
self.val = val
self.key = key
self.next = next1
self.prev = prev
class LRUCache:
def \_\_init\_\_(self, capacity: int):
self.capacity = capacity
self.knmap = {}
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.knmap:
self.remove(key)
self.add(key)
return self.knmap[key].val
else:
return -1
def put(self, key: int, value: int) -> None:
if key not in self.knmap.keys():
self.knmap[key] = ListNode(key, value)
else:
self.remove(key)
node = self.knmap[key]
node.val = value
self.add(key)
while len(self.knmap) > self.capacity:
del_key = self.tail.prev.key
self.remove(del_key)
del self.knmap[del_key]
def add(self, key):
node = self.knmap[key]
node.next = self.head.next
node.prev = self.head
node.next.prev = node
self.head.next = node
def remove(self, key):
node = self.knmap[key]
node.prev.next = node.next
node.next.prev = node.prev
Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Your LRUCache object will be instantiated and called as such:
~~~
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
~~~
if you use a queue to keep track of gets and a dictionary to count the occurrence of key in queue and a dictionary to hold key value pairs then this is a lot simpler to implement than with doubly linked lists
class LRUCache:
def __init__(self, capacity: int):
self.cacheq = deque()
self.count_hash = {}
self.kv = {}
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.kv:
return -1
else:
self.put(key, self.kv[key])
return self.kv[key]
def put(self, key: int, value: int) -> None:
self.kv[key] = value
self.count_hash[key] = self.count_hash.get(key, 0) + 1
self.cacheq.appendleft(key)
while len(self.kv) > self.capacity:
key = self.cacheq.pop()
self.count_hash[key] -= 1
if self.count_hash[key] == 0:
del self.kv[key]
Binary Tree Right Side View
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
—– make sure you have code in mind
This is basically making a list of the rightmost element at every level and returning it.
main challenge is how to do level order traversal or BFS. this is done using a queue and a for loop inside a while loop.
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
#do level order traversal and only append the last element
if not root:
return []
q = deque()
q.append(root)
sol = []
while q:
level = []
for i in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
level.append(node.val)
sol.append(level[-1])
return sol
Count Good Nodes in Binary Tree
Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.
Return the number of good nodes in the binary tree.
Need to do recursive calls and pass down the condition which is the max node seen up to this point on the way down the recursion. A lot like checking whether a BST is valid.
Add code!!
Lowest Common Ancestor of a Binary search tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
class TreeNode:
bst is ordered which means everything on left of a node is always smaller and everything on right of a node is larger so you can leverage this to get an easy solution like below:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while root:
if (p.val < root.val) and (q.val < root.val):
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
