75 Flashcards
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.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
numSet = set()
for n in nums:
if n in numSet:
return True
numSet.add(n)
return False
#O(n)
#O(n)Valid Anagram: Given two strings s and t, return true if t is an anagram of s, and false otherwise.
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
sCount = {}
tCount = {}
for i in range(len(s)):
sCount[s[i]] = sCount.get(s[i], 0) + 1
tCount[t[i]] = tCount.get(t[i], 0) + 1
return tCount == sCount
#O(n)
#O(1) -> 26 characters in alphabet
Two Sum: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {}
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
#O(n)
#O(n)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.
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
#hashmap maps anagrams to strs
anaMap = {}
for s in strs:
curCounts = [0] * 26
for c in s:
curCounts[ord(c) - ord('a')] += 1
curTup = tuple(curCounts)
if curTup not in anaMap:
anaMap[curTup] = [s]
else:
anaMap[curTup].append(s)
return anaMap.values()
#O(N) #all the characters in strs
#O(N) #the mapping needs all the characters in strs and the anagrams.
#In other words, we can also say O(nm), where n is number of strs and m is the avg length of each ana.
Top K Frequent Elements: Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freqs = [[] for i in range(len(nums) + 1)]
#default to list comprehension for empty [] inits, or all.
counts = {}
for n in nums:
counts[n] = counts.get(n, 0) + 1
for n, c in counts.items():
freqs[c].append(n)
res = []
for i in range(len(freqs) - 1, -1, -1):
for n in freqs[i]:
res.append(n)
if len(res) == k:
return res
#O(n) for iterating, hashing, etc
#O(n) for the hashing, and the counts array for the bucket sort.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.
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
prefix = 1
for i in range(len(nums)):
res[i] = prefix
prefix *= nums[i]
suffix = 1
for j in range(len(nums) - 1, -1, -1):
res[j] *= suffix
suffix *= nums[j]
return res
#O(n) number of elts and traverse
#O(n) keep res variable, tho O(1) if you don't count res as extra space I guess...?Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
class Solution:
def isValid(self, s: str) -> bool:
closedToOpen = {")": "(", "}": "{", "]":"[" } #map closed to open parentheses
stack = []
for c in s:
if c in closedToOpen:
if not stack or stack[-1] != closedToOpen[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
#O(n)
#O(n)Given the head of a singly linked list, reverse the list, and return the reversed list.
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
cur = head
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
return prev
#O(n)
#O(1)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.
# 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]:
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
if list2:
tail.next = list2
return dummy.next
#O(l1 + l2)
#O(1)
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.
# Definition for singly-linked list.
# class ListNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow, fast = head, head #fine to just set these to the same initially.
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
#O(n)
#O(1)
Given the root of a binary tree, invert the tree, and return its root.
# 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:
return None
invertedLeft = self.invertTree(root.left)
invertedRight = self.invertTree(root.right)
root.left = invertedRight
root.right = invertedLeft
return root
#O(n)
#O(h) #recursion stack, expected O(log n)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.
# 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))
#O(n)
#O(h)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.
# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
#O(|p| + |q|)
#O(min(height of p, height of q trees))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.
# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
if not subRoot:
return True
if not root:
return False
if self.sameTree(root, subRoot):
return True
return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)
def sameTree(self, t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2 or t1.val != t2.val:
return False
return self.sameTree(t1.left, t2.left) and self.sameTree(t1.right, t2.right)
#O(|t1| * |t2|) #check each root for subroot match
#O(height of t1 + height of t2) #We can potentially be at the bottom of the first tree, and we need to compare against all nodes in t2
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).”
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
elif p.val > root.val and q.val > root.val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
#O(h) -> we only go level by level, not need to visit all nodes
#O(h) -> same for recursion stackGiven the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).
# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
q = deque([root])
res = []
while q:
curLevel = []
for _ in range(len(q)):
cur = q.popleft()
curLevel.append(cur.val)
if cur.left:
q.append(cur.left)
if cur.right:
q.append(cur.right)
res.append(curLevel)
return res
#O(n) #traverse every node
#O(n) # queue sizeGiven 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.
# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node, left, right):
if not node: #empty BST is a valid BST
return True
#It's not binary search. It's the expected left and right values!
if not (node.val > left and node.val < right):
return False
return dfs(node.left, left, node.val) and dfs(node.right, node.val, right)
return dfs(root, -float('inf'), float('inf'))
#O(n)
#O(h)Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
# 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 kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
cur = root
count = 0
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
count += 1
if count == k:
return cur.val
cur = cur.right
#O(n) #potentially all nodes
#O(h) #stack at most height size
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
res = [root.val] #initially, this root can be negative, so don't init to 0
def dfs(root): #returns max WITHOUT splitting
if not root:
return 0
leftMax = max(dfs(root.left), 0)
rightMax = max(dfs(root.right), 0)
res[0] = max(res[0], root.val + leftMax + rightMax)
return root.val + max(leftMax, rightMax)
dfs(root)
return res[0]
#Runtime: O(n)
#Space: O(h)
A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
class TrieNode:
def \_\_init\_\_(self):
self.children = {}
self.isWord = False
class Trie:
def \_\_init\_\_(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isWord = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
if c not in cur.children:
return False
cur = cur.children[c]
return cur.isWord
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
if c not in cur.children:
return False
cur = cur.children[c]
return True
#O(m) for all operations
#O(m) insert, O(1) otherwise.
Design a data structure that supports adding new words and finding if a string matches any previously added string.
Implement the WordDictionary class:
WordDictionary() Initializes the object.
void addWord(word) Adds word to the data structure, it can be matched later.
bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots ‘.’ where dots can be matched with any letter.
class TrieNode:
def \_\_init\_\_(self):
self.children = {}
self.isWord = False
class WordDictionary:
def \_\_init\_\_(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isWord = True
def search(self, word: str) -> bool:
def dfs(j, root):
cur = root
#have a loop that loops through everything from i to length of word, even though it's a dfs
for i in range(j, len(word)):
c = word[i]
if c == ".":
for child in cur.children.values():
#if any child node are matched, we return True
if dfs(i + 1, child): #skip current char
return True
#if can't matched any, return False
return False
else:
if c not in cur.children: #have this be a return!
return False #this is a return that will potentially end the recursion
cur = cur.children[c]
return cur.isWord #return True if reached end of the input string, and is word
return dfs(0, self.root)
#Runtime: O(M) per add and init opeartion
#Search: O(M) if no dots else O(26^M)
#Space: O(26^ word length) -> O(1) for storage.
#For Search: O(1) if no dots, else O(M) if recursion needed Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
res = [intervals[0]]
for start, end in intervals[1:]:
prevEnd = res[-1][1]
if start > prevEnd:
res.append([start, end])
else:
res[-1][1] = max(prevEnd, end)
return res
#O(n log n) due to sorting.
#O(n)You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
Return intervals after the insertion.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
#already told us it's sorted, but would sort here
res = []
#This one, you need to check one by one. Can't just arbitarily set res to res[intervals[]]
for i in range(len(intervals)):
#if newInterval precedes current interval, just add
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
#NOT i + 1. If newInterval precedes, then add newInterval in, then i onwards
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
#can't append newInterval yet - might overlap with something later
else:
#if truly overlapping, then we modify our newInterval
newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
#If we're at this point, we haven't returned yet, so we still have an interval.
res.append(newInterval)
return res
#O(n)
#O(n)Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort() #sort by the start time to start out
prevEnd = intervals[0][1]
res = 0
for start, end in intervals[1:]:
if start >= prevEnd: #they don't overlap
prevEnd = end
else:
#if they do overlap, we want to MINIMIZE chance of collision
#So, we should only keep the interval with earlier end time
res += 1
prevEnd = min(end, prevEnd)
return res
#O(n log n) #for sorting
#O(1)
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort()
for i in range(len(intervals) - 1):
if intervals[i + 1][0] < intervals[i][1]:
return False
return True
#O(n log n)
#O(1)Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
starts = []
ends = []
for start, end in intervals:
starts.append(start)
ends.append(end)
starts.sort()
ends.sort()
#[0, 5, 15]
#[30, 10, 20] -> [10, 20, 30]
#We sort both so we know when we can close a conference room
i, j = 0, 0
#For counts, we know j won't increment our count, so iteration is just
#until i < len(starts)
maxCount = 0
curCount = 0
while i < len(starts):
if starts[i] < ends[j]: #if nothing has ended yet
curCount += 1
maxCount = max(maxCount, curCount)
i += 1
else: #something has ended
curCount -= 1
j += 1
return maxCount
#O(nlogn) for sorting
#O(n) for starts and ends.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?
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 3:
return n
n1 = 2
n2 = 3
for i in range(4, n + 1):
tmp = n1 + n2
n1 = n2
n2 = tmp
return n2
#O(n)
#O(1)
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.
class Solution:
def rob(self, nums: List[int]) -> int:
n1, n2 = 0, 0
for n in nums:
tmp = max(n2, n1 + n)
n1 = n2
n2 = tmp
return n2
#O(n)
#O(1)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.
class Solution:
def rob(self, nums: List[int]) -> int:
#nums[0] because in single element case, you need to rob something
return max(nums[0], self.hr1(nums[:-1]), self.hr1(nums[1:]))
def hr1(self, nums):
n1, n2 = 0, 0
for n in nums:
tmp = max(n2, n1 + n)
n1 = n2
n2 = tmp
return n2
#Runtime: O(n)
#Space: O(1)
Given a string s, return the longest
palindromic
substring
in s.
class Solution:
def longestPalindrome(self, s: str) -> str:
maxLength = 0
maxL, maxR = 0, 0
for i in range(len(s)):
#centers are at elts
l, r = i, i #do this so you can have centers at in
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > maxLength:
maxLength = r - l + 1
maxL, maxR = l, r
l -= 1
r += 1
#centers are in between elts
l, r = i, i + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > maxLength:
maxLength = r - l + 1
maxL, maxR = l, r
l -= 1
r += 1
return s[maxL: maxR + 1]
#O(n^2): O(2*n) centers, O(n) to go through each.
#O(1)
