neetcode Flashcards
Contains Duplicate:
Given an integer array nums, return true if any value appears more than once in the array, otherwise return false.
Example 1:
Input: nums = [1, 2, 3, 3]
Output: true
Example 2:
Input: nums = [1, 2, 3, 4]
Output: false
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)
- Valid Anagram:
Given two strings s and t, return true if t is an
anagram
of s, and false otherwise.
Example 1:
Input: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
Constraints:
1 <= s.length, t.length <= 5 * 104
s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
for val in count:
if val != 0:
return False
return True
Two Sum:
Given an array of integers nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
Return the answer with the smaller index first.
Example 1:
Input:
nums = [3,4,5,6], target = 7
Output: [0,1]
Explanation: nums[0] + nums[1] == 7, so we return [0, 1].
Example 2:
Input: nums = [4,5,6], target = 10
Output: [0,2]
Example 3:
Input: nums = [5,5], target = 10
Output: [0,1]
Constraints:
2 <= nums.length <= 1000
-10,000,000 <= nums[i] <= 10,000,000
-10,000,000 <= target <= 10,000,000
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {} #val->index
for i, n in enumerate(nums):
difference = target - n
if difference in prevMap:
return [prevMap[difference], i]
prevMap[n] = i
Group Anagrams
Given an array of strings strs, group all anagrams together into sublists. You may return the output in any order.
An anagram is a string that contains the exact same characters as another string, but the order of the characters can be different.
Example 1:
Input: strs = [“act”,”pots”,”tops”,”cat”,”stop”,”hat”]
Output: [[“hat”],[“act”, “cat”],[“stop”, “pots”, “tops”]]
Example 2:
Input: strs = [“x”]
Output: [[“x”]]
Example 3:
Input: strs = [””]
Output: [[””]]
Constraints:
1 <= strs.length <= 1000.
0 <= strs[i].length <= 100
strs[i] is made up of lowercase English letters.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list) #map char count to list of anagrams
for s in strs:
count = [0] * 26 # a...z
for c in s:
count[ord(c) - ord("a")] += 1 #ascii values
res[tuple(count)].append(s)
return list(res.values())
Top K Frequent Elements:
Given an integer array nums and an integer k, return the k most frequent elements within the array.
The test cases are generated such that the answer is always unique.
You may return the output in any order.
Example 1:
Input: nums = [1,2,2,3,3,3], k = 2
Output: [2,3]
Example 2:
Input: nums = [7,7], k = 1
Output: [7]
Constraints:
1 <= nums.length <= 10^4.
-1000 <= nums[i] <= 1000
1 <= k <= number of distinct elements in nums.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
#O(n) -> modified bucket sort, table example:
#i (count) : 0 1 2 …
#values : [10] [2] [4,2] …
#this is better because the i(count) row is always size of array, always
#bounded, never wasting time/space
count = {} #hashmap
frequencies = [[] for i in range(len(nums) + 1)] #size of input + 1
for n in nums:
count[n] = 1 + count.get(n,0)
for n, c in count.items(): #for every number and count
frequencies[c].append(n)
result = []
for i in range(len(frequencies) - 1, 0, -1): #descending order to find top k
for n in frequencies[i]:
result.append(n) #append most freq
if len(result) == k:
return result
Encode and Decode Strings:
Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.
Please implement encode and decode
Example 1:
Input: [“neet”,”code”,”love”,”you”]
Output:[“neet”,”code”,”love”,”you”]
Example 2:
Input: [“we”,”say”,”:”,”yes”]
Output: [“we”,”say”,”:”,”yes”]
Constraints:
0 <= strs.length < 100
0 <= strs[i].length < 200
strs[i] contains only UTF-8 characters.
class Solution:
def encode(self, strs: List[str]) -> str: def decode(self, s: str) -> List[str]:
class Solution:
#make a list in the string itself INSTEAD OF SEPARATE DATA STRUCUTURE to store
#lengths of each element
#make a code w number length, then delimeter, then word, for all words
#e.g. "4#neet", "5#co#de", these all work and won't get confused
def encode(self, strs: List[str]) -> str:
result = ""
for s in strs:
result += str(len(s)) + "#" + s #"4#neet"
return result
def decode(self, s: str) -> List[str]:
result = []
i = 0 #ptr
while i < len(s):
j = i #find end of integer
while s[j] != "#": #we're still at integer character
j += 1 #increment until you reach pound delimeter
length = int(s[i:j]) #from i to j, this is the string integer (convert)
result.append(s[j + 1 : j + 1 + length])
i = j + 1 + length #beginning of next string OR end of current string
return result
Products of Array Except Self:
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].
Each product is guaranteed to fit in a 32-bit integer.
Follow-up: Could you solve it in
O
(
n
)
O(n) time without using the division operation?
Example 1:
Input: nums = [1,2,4,6]
Output: [48,24,12,8]
Example 2:
Input: nums = [-1,0,1,2,3]
Output: [0,-6,0,0,0]
Constraints:
2 <= nums.length <= 1000
-20 <= nums[i] <= 20
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
class Solution:
#get the product of every value of left of value, then every value on right
#then multiply altogether
#compute all prefixes and postfixes (assume "1" if on very left/right)
#then, for each index, multiply prefix on left and postfix on right of element
def productExceptSelf(self, nums: List[int]) -> List[int]:
result = [1] * len(nums)
prefix = 1
for i in range(len(nums)):
result[i] = prefix
prefix *= nums[i]
postfix = 1
for i in range(len(nums) - 1, -1, -1):
result[i] *= postfix
postfix *= nums[i]
return result
Longest Consecutive Sequence:
Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.
A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [2,20,4,10,3,4,5]
Output: 4
Explanation: The longest consecutive sequence is [2, 3, 4, 5].
Example 2:
Input: nums = [0,3,2,5,4,6,1,1]
Output: 7
Constraints:
0 <= nums.length <= 1000
-10^9 <= nums[i] <= 10^9
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
class Solution:
#group items by sequences, figure it out if there’s left neighbor
#e.g. in [100,4,200,1,3,2], sequences -> [1,2,3,4] , [100] , [200]
#notice how there’s no 0, 99, or 199 AKA one less than seq. AKA no left
#meaning that sequence ONLY STARTS if there’s no left value, so like at 4
#it isn’t start of sequence because there’s a 3 on the left
#O(n) time
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest_sequence = 0
for n in nums:
if (n -1) not in numSet: #check if start of sequence
length = 0
while (n + length) in numSet:
length += 1
longest_sequence = max(length, longest_sequence)
return longest_sequence
Valid Palindrome:
Given a string s, return true if it is a palindrome, otherwise return false.
A palindrome is a string that reads the same forward and backward. It is also case-insensitive and ignores all non-alphanumeric characters.
Example 1:
Input: s = “Was it a car or a cat I saw?”
Output: true
Explanation: After considering only alphanumerical characters we have “wasitacaroracatisaw”, which is a palindrome.
Example 2:
Input: s = “tab a cat”
Output: false
Explanation: “tabacat” is not a palindrome.
Constraints:
1 <= s.length <= 1000
s is made up of only printable ASCII characters.
class Solution:
def isPalindrome(self, s: str) -> bool:
class Solution:
def isPalindrome(self, s: str) -> bool:
newStr = ‘’
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]
3Sum:
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
Constraints:
3 <= nums.length <= 1000
-10^5 <= nums[i] <= 10^5
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
class Solution: #O(n^2)
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1
r-= 1
return res
Container With Most Water:
You are given an integer array heights where heights[i] represents the height of the i-th bar.
You may choose any two bars to form a container. Return the maximum amount of water a container can store.
Example 1:
Input: height = [1,7,2,5,4,7,3,6]
Output: 36
Example 2:
Input: height = [2,2,2]
Output: 4
Constraints:
2 <= height.length <= 1000
0 <= height[i] <= 1000
class Solution:
def maxArea(self, heights: List[int]) -> int:
class Solution:
def maxArea(self, heights: List[int]) -> int:
left, right = 0, len(heights)-1
res = 0
while left < right:
area = min(heights[left], heights[right]) * (right-left)
res = max(res,area)
if heights[left] <= heights[right]:
left += 1
else:
right -= 1
return res
Best Time to Buy and Sell Stock:
You are given an integer array prices where prices[i] is the price of NeetCoin on the ith day.
You may choose a single day to buy one NeetCoin and choose a different day in the future to sell it.
Return the maximum profit you can achieve. You may choose to not make any transactions, in which case the profit would be 0.
Example 1:
Input: prices = [10,1,5,6,7,1]
Output: 6
Explanation: Buy prices[1] and sell prices[4], profit = 7 - 1 = 6.
Example 2:
Input: prices = [10,8,7,5,2]
Output: 0
Explanation: No profitable transactions can be made, thus the max profit is 0.
Constraints:
1 <= prices.length <= 100
0 <= prices[i] <= 100
class Solution:
def maxProfit(self, prices: List[int]) -> int:
class Solution:
#init left ptr on day one, right ptr on day two
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1 #left is buying, right is selling
max_profit = 0
while r < len(prices):
if prices[l] < prices[r]: #check if profitable
profit = prices[r] - prices[l]
max_profit = max(profit, max_profit)
else:
l = r #shift all the way to the right; we found the lowest price
r += 1
return max_profit
Longest Substring Without Repeating Characters:
Given a string s, find the length of the longest substring without duplicate characters.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: s = “zxyzxyz”
Output: 3
Explanation: The string “xyz” is the longest without duplicate characters.
Example 2:
Input: s = “xxxx”
Output: 1
Constraints:
0 <= s.length <= 1000
s may consist of printable ASCII characters.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
char_set = set()
l = 0
result = 0
for r in range(len(s)):
while s[r] in char_set: #duplicate
char_set.remove(s[l])
l += 1
char_set.add(s[r])
result = max(result, r-l + 1)
return result
Longest Repeating Character Replacement:
You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.
After performing at most k replacements, return the length of the longest substring which contains only one distinct character.
Example 1:
Input: s = “XYYX”, k = 2
Output: 4
Explanation: Either replace the ‘X’s with ‘Y’s, or replace the ‘Y’s with ‘X’s.
Example 2:
Input: s = “AAABABB”, k = 1
Output: 5
Constraints:
1 <= s.length <= 1000
0 <= k <= s.length
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
class Solution:
#hashmap/array to count occurences of char
#do window length - count[each index] to figure out with window/substring, which
#needs to be replaced
def characterReplacement(self, s: str, k: int) -> int:
count = {}
res = 0
l = 0
maxf = 0
for r in range(len(s)):
count[s[r]] = 1 + count.get(s[r], 0)
maxf = max(maxf, count[s[r]])
while (r - l + 1) - maxf > k:
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return res
Valid Parentheses:
You are given a string s consisting of the following characters: ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’.
The input string s is valid if and only if:
Every open bracket is closed by the same type of close bracket.
Open brackets are closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
Return true if s is a valid string, and false otherwise.
Example 1:
Input: s = “[]”
Output: true
Example 2:
Input: s = “([{}])”
Output: true
Example 3:
Input: s = “[(])”
Output: false
Explanation: The brackets are not closed in the correct order.
Constraints:
1 <= s.length <= 1000
class Solution:
def isValid(self, s: str) -> bool:
O(n^2)
class Solution:
def isValid(self, s: str) -> bool:
while ‘()’ in s or ‘{}’ in s or ‘[]’ in s:
s = s.replace(‘()’, ‘’)
s = s.replace(‘{}’, ‘’)
s = s.replace(‘[]’, ‘’)
return s == ‘’
class Solution:
def isValid(self, s: str) -> bool:
stack = []
# Create a mapping of closing parentheses to opening parentheses
mapping = {‘)’: ‘(‘, ‘}’: ‘{‘, ‘]’: ‘[’}
for char in s:
if char in mapping:
# If the stack is empty or the top of the stack doesn't match the corresponding opening parenthesis
top_element = stack.pop() if stack else '#'
if top_element != mapping[char]:
return False
else:
# Push the opening parenthesis onto the stack
stack.append(char)
# If the stack is empty, all parentheses are valid
return not stack #O(n)
Find Minimum in Rotated Sorted Array:
You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2] if it was rotated 4 times.
[1,2,3,4,5,6] if it was rotated 6 times.
Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.
Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.
A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?
Example 1:
Input: nums = [3,4,5,6,1,2]
Output: 1
Example 2:
Input: nums = [4,5,0,1,2,3]
Output: 0
Example 3:
Input: nums = [4,5,6,7]
Output: 4
Constraints:
1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
class Solution:
def findMin(self, nums: List[int]) -> int:
class Solution:
#binary search -> O(log n)
#nums[m] >= nums[l]: search right
#else: search left
def findMin(self, nums: List[int]) -> int:
l,r = 0, len(nums)-1
while l < r:
m = l + (r-l) // 2
if nums[m] < nums[r]:
r = m
else:
l = m +1
return nums[l]
Search in Rotated Sorted Array:
You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:
[3,4,5,6,1,2] if it was rotated 4 times.
[1,2,3,4,5,6] if it was rotated 6 times.
Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.
You may assume all elements in the sorted rotated array nums are unique,
A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?
Example 1:
Input: nums = [3,4,5,6,1,2], target = 1
Output: 4
Example 2:
Input: nums = [3,5,6,0,1,2], target = 4
Output: -1
Constraints:
1 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-1000 <= target <= 1000
class Solution:
def search(self, nums: List[int], target: int) -> int:
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r: #we do <= if array size is just one
mid = (l + r) // 2
if target == nums[mid]:
return mid
#check if we're in left portion
if nums[l] <= nums[mid]:
if target > nums[mid] or target < nums[l]:
l = mid + 1
else: #less than m but > l
r = mid - 1
#check if we're in right portion
else:
if target < nums[mid] or target > nums[r]:
r = mid - 1
else:
l = mid + 1
return -1
class ListNode:
Reverse Linked List:
Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list.
Example 1:
Input: head = [0,1,2,3]
Output: [3,2,1,0]
Example 2:
Input: head = []
Output: []
Constraints:
0 <= The length of the list <= 1000.
-1000 <= Node.val <= 1000
Definition for singly-linked list.
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
class ListNode:
Definition for singly-linked list.
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
previous = None
current = head
while current:
next_node = current.next
current.next = previous
previous = current
current = next_node
return previous
Merge Two Sorted Linked Lists:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted linked list and return the head of the new sorted linked list.
The new list should be made up of nodes from list1 and list2.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,5]
Output: [1,1,2,3,4,5]
Example 2:
Input: list1 = [], list2 = [1,2]
Output: [1,2]
Example 3:
Input: list1 = [], list2 = []
Output: []
Constraints:
0 <= The length of the each list <= 100.
-100 <= Node.val <= 100
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
temp = ListNode()
node = ListNode()
temp = node
while list1 and list2:
if list1.val < list2.val:
node.next = list1
list1 = list1.next
else:
node.next = list2
list2 = list2.next
node = node.next
node.next = list1 or list2
return temp.next
Linked List Cycle Detection:
Given the beginning of a linked list head, return true if there is a cycle in the linked list. Otherwise, return false.
There is a cycle in a linked list if at least one node in the list that can be visited again by following the next pointer.
Internally, index determines the index of the beginning of the cycle, if it exists. The tail node of the list will set it’s next pointer to the index-th node. If index = -1, then the tail node points to null and no cycle exists.
Note: index is not given to you as a parameter.
Example 1:
Input: head = [1,2,3,4], index = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], index = -1
Output: false
Constraints:
1 <= Length of the list <= 1000.
-1000 <= Node.val <= 1000
index is -1 or a valid index in the linked list.
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
current = head
visited = []
while current:
if current.next in visited:
return True
else:
visited.append(current)
current = current.next
return False
Reorder Linked List:
You are given the head of a singly linked-list.
The positions of a linked list of length = 7 for example, can intially be represented as:
[0, 1, 2, 3, 4, 5, 6]
Reorder the nodes of the linked list to be in the following order:
[0, 6, 1, 5, 2, 4, 3]
Notice that in the general case for a list of length = n the nodes are reordered to be in the following order:
[0, n-1, 1, n-2, 2, n-3, …]
You may not modify the values in the list’s nodes, but instead you must reorder the nodes themselves.
Example 1:
Input: head = [2,4,6,8]
Output: [2,8,4,6]
Example 2:
Input: head = [2,4,6,8,10]
Output: [2,10,4,8,6]
Constraints:
1 <= Length of the list <= 1000.
1 <= Node.val <= 1000
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
if not head:
return
nodes = []
cur = head
while cur:
nodes.append(cur)
cur = cur.next
i, j = 0, len(nodes) - 1
while i < j:
nodes[i].next = nodes[j]
i += 1
if i >= j:
break
nodes[j].next = nodes[i]
j -= 1
nodes[i].next = None
Remove Node From End of Linked List:
You are given the beginning of a linked list head, and an integer n.
Remove the nth node from the end of the list and return the beginning of the list.
Example 1:
Input: head = [1,2,3,4], n = 2
Output: [1,2,4]
Example 2:
Input: head = [5], n = 1
Output: []
Example 3:
Input: head = [1,2], n = 2
Output: [2]
Constraints:
The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy_node = ListNode(0, head) # insert dummy at beginning pointing to head
left = dummy_node
right = head
#right = head + n
while n > 0 and right:
right = right.next
n -= 1 #keep shifting right
while right: #end
left = left.next
right = right. next
#delete
left.next = left.next.next
return dummy_node.next #dont include the dummy node but do next (back to OG head)
Invert Binary Tree:
You are given the root of a binary tree root. Invert the binary tree and return its root.
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,3,2,7,6,5,4]
Example 2:
Input: root = [3,2,1]
Output: [3,1,2]
Example 3:
Input: root = []
Output: []
Constraints:
0 <= The number of nodes in the tree <= 100.
-100 <= Node.val <= 100
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
dfs, use recursion
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root: #if root null
return None
#swap children otherwise
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.left)
self.invertTree(root.right)
return root
Maximum Depth of Binary Tree:
Given the root of a binary tree, return its depth.
The depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.
Example 1:
Input: root = [1,2,3,null,null,4]
Output: 3
Example 2:
Input: root = []
Output: 0
Constraints:
0 <= The number of nodes in the tree <= 100.
-100 <= Node.val <= 100
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
