must-know Flashcards
Two Sum
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
Three Sum
class Solution:
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
Longest Consecutive Sequence
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
Contains Duplicate
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
return len(set(nums)) < len(nums)
Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
newStr = ‘’
for c in s:
if c.isalnum():
newStr += c.lower()
return newStr == newStr[::-1]
/**
* @param {string} s
* @return {boolean}
*/
var isPalindrome = function(s) {
const cleanStr = s.toLowerCase().replace(/[^a-z0-9]/g, ‘’);
const reversedStr = cleanStr.split(‘’).reverse().join(‘’);
return cleanStr === reversedStr;
};
// Test cases
function testIsPalindrome() {
console.log(“Test 1 Passed:”, isPalindrome(“A man, a plan, a canal: Panama”) === true);
console.log(“Test 2 Passed:”, isPalindrome(“race a car”) === false);
console.log(“Test 3 Passed:”, isPalindrome(“ “) === true); // considering empty string or spaces as palindromes
console.log(“Test 4 Passed:”, isPalindrome(“12321”) === true);
console.log(“Test 5 Passed:”, isPalindrome(“123456”) === false);
}
testIsPalindrome();
Valid Anagram
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
Group Anagrams
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
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
Product of Array Except Itself
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
total_product = 1
zero_count = 0
n = len(nums)
for num in nums:
if num != 0:
total_product *= num
else:
zero_count += 1
if zero_count > 1:
return [0] * n
elif zero_count == 1:
result = []
for num in nums:
if num == 0:
result.append(total_product)
else:
result.append(0)
return result
else:
result = [total_product // num for num in nums]
return result
class Solution:
def productExceptSelf(self, nums):
res, p = [1] * len(nums), 1
for i in range(len(nums)): res[i], p = p, p * nums[i]
p = 1
for i in range(len(nums) - 1, -1, -1): res[i], p = res[i] * p, p * nums[i]
return res
Valid Parenthesis
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)
Best Time to Buy and Sell Stock
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 Repeated Characters
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
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
left = 0
seen = {}
output = 0
for right, curr in enumerate(s):
if curr in seen:
left = max(left, seen[curr] + 1)
output = max(output, right - left + 1)
seen[curr] = right
return output
Longest Repeating Character Replacement
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
Permutation in String
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s1) > len(s2):
return False
s1count = [0] * 26
s2count = [0] * 26
for i in range(len(s1)): #init freq counts for s1 and 1st window in s2
s1count[ord(s1[i]) - ord('a')] += 1
s2count[ord(s2[i]) - ord('a')] += 1
for i in range(len(s2) - len(s1)): #slide window over s2
if s1count == s2count:
return True
s2count[ord(s2[i]) - ord('a')] -= 1
s2count[ord(s2[i + len(s1)]) - ord('a')] += 1
return s1count == s2count #check last window
Minimum Window Substring
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(s) < len(t):
return “”
char_count = defaultdict(int) #store A-Z and put val 1 if in substr, or -1 if not
for ch in t:
char_count[ch] += 1
target_chars_remaining = len(t) #go thru s, see at each index if it equals t, subtract this
min_window = (0, float("inf")) #0 to infinity just to init
start_index = 0
for end_index, ch in enumerate(s):
if char_count[ch] > 0: #if value of s is present in dict, AKA if its 1
target_chars_remaining -= 1 #one less char we need to find from substr
char_count[ch] -= 1
if target_chars_remaining == 0:
while True:
char_at_start = s[start_index]
if char_count[char_at_start] == 0:
break
char_count[char_at_start] += 1
start_index += 1
if end_index - start_index < min_window[1] - min_window[0]:
min_window = (start_index, end_index)
char_count[s[start_index]] += 1
target_chars_remaining += 1
start_index += 1
return "" if min_window[1] > len(s) else s[min_window[0]:min_window[1]+1]
Merge K Sorted Lists
Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
nodes = []
for node in lists:
while node:
nodes.append(node)
node = node.next
nodes.sort(key = lambda x: x.val)
dummy = ListNode()
i = dummy
for node in nodes:
i.next = node
i = i.next
i.next = None
return dummy.next
Container With the Most Water
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
Merge Intervals
class Solution:
#input arrays within the big intervals list might not be sorted
#interval must be from 0…infinity
#go thru the start indices, i.e. list[0][0], list[1][0], …, list[4][0], …
#while at the same time oppositely comparing with end indices, i.e. list[-1][1]
#O(n log n)
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key = lambda i : i[0]) #sorting by all start interval values
output = [intervals[0]] #avoid edge case
for start, end in intervals[1:]: #skip first
lastEnd = output[-1][1] #end value of most recent interval
if start <= lastEnd: #overlapping
output[-1][1] = max(lastEnd, end)
#e.g. in [1,5] , [2,4]
#we want to keep the 5 from the first when merging
else:
output.append([start,end])
#e.g. [1,5] , [7,8] = [1,5] , [7,8] -> equals itself, already sorted
return output
Largest Number
class Solution:
def largestNumber(self, nums: List[int]) -> str:
return ‘‘.join(sorted(map(str, nums), key=lambda s: s * 10, reverse=True)) if any(nums) else “0”
Binary Search
class Solution:
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Search a 2D Matrix
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
row, col = mid // cols, mid % cols
guess = matrix[row][col]
if guess == target:
return True
if guess < target:
left = mid + 1
else:
right = mid - 1
return False
Find Minimum in Rotated Sorted Array
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] <= nums[right]:
right = mid
else:
left = mid + 1
return nums[left]
Reverse Linked List
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 Lists
Definition for singly-linked list.
# 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
