Meta Flashcards
Description
Notes
- Add Two Numbers
Medium
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
- carry or l1 or l2
- carry,value = divmod(carry, 10)
T: O(n)
S: O(1)
- Longest Substring Without Repeating Characters
Medium
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
- Sliding window
- while counter[swe]>1:
counter[s[ws]]-=1
ws+=1
maxi=max(maxi, we-ws+1))def lengthOfLongestSubstring(self, s: str) -> int:
ws=0
counter=defaultdict(int)maxi=0 for we, swe in enumerate(s): counter[swe]+=1 while counter[swe]>1: counter[s[ws]]-=1 #if counter[s[ws]]==0: # del counter[s[ws]] ws+=1 maxi=max(maxi, we-ws+1) return maxi
T: O(n)
S: O(n)
- Median of Two Sorted Arrays
Hard
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
- Right array must be longer (take left and right of N1). Half is (N1+N2+1)//2
- Binary search (while left<=right)
- i=(left+right)//2, j=half -i
- aleft=A[i-1] if A[i-1]>0 else float(‘-inf’), bleft=B[j-1]….
- aright = A[i] if ibright: right=i-1. Else left=i+1
Super weird. Need to figure out how to explain this logic.
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A = nums1
B = nums2
if len(A) > len(B):
A, B = B, A
N1 = len(A)
N2 = len(B)
left = 0
half = (N1 + N2 + 1) // 2
right = N1
while left <= right:
i = (left + right) // 2
j = half - i
aleft = A[i - 1] if i - 1 >= 0 else float('-inf')
bleft = B[j - 1] if j - 1 >= 0 else float('-inf')
aright = A[i] if i < N1 else float('inf')
bright = B[j] if j < N2 else float('inf')
if aleft <= bright and bleft <= aright:
if (N1 + N2) % 2 != 0:
return max(aleft, bleft)
else:
return (max(aleft, bleft) + min(aright, bright)) / 2.0
elif aleft > bright:
right = i - 1
else:
left = i + 1
return -1
T: O(log(min(m,n))
S: O(1)
- Longest Palindromic Substring
Medium
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output: “bb”
- Expand from middle
- is_odd=is_palin(s, i, i)
- is_even=is_palin(s, i, i+1)
- longest = max(longest, odd, even, key=len)
- within is_palin,
while low>=0 and high str:
longest=””
for i in range(len(s)):
odd=self.is_palin(s, i, i)
even=self.is_palin(s, i, i+1)
longest=max(longest, odd, even, key=len)
return longestdef is_palin(self, s, low, high):
while low>=0 and high
- Zigzag Conversion
Medium
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:
string convert(string s, int numRows);
Example 1:
Input: s = “PAYPALISHIRING”, numRows = 3
Output: “PAHNAPLSIIGYIR”
Example 2:
Input: s = “PAYPALISHIRING”, numRows = 4
Output: “PINALSIGYAHRPI”
Explanation:
P I N
A L S I G
Y A H R
P I
- Tricky. Maintain a defaultdict(list)
- index=1, up=False
- Iterate through s and append to result[index]
- if up, index-=1, else index+=1
- if index==numRows or index==1: up = not updef convert(self, s: str, numRows: int) -> str:
if numRows==1:
return sresult=defaultdict(list) index=1 up=False for c in s: result[index].append(c) if up: index-=1 else: index+=1 if index==numRows or index==1: up=not up ret_result="" for i in range(1, numRows+1): ret_result+=''.join(result[i]) return ret_result
T: O(n)
S: O(1)
- Reverse Integer
Medium
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
- divmoddef reverse(self, x: int) -> int:
sign=1if x<0: sign=-1 x*=-1 cx=0 while x: x,value = divmod(x, 10) cx=cx*10+value cx=sign*cx return cx if -2**31 <=cx <=2**31-1 else 0
T: O(log(x)), logx is the number of digits in x (log10)
S: O(1)
- String to Integer (atoi)
Medium
Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.
The algorithm for myAtoi(string s) is as follows:
Whitespace: Ignore any leading whitespace (“ “).
Signedness: Determine the sign by checking if the next character is ‘-‘ or ‘+’, assuming positivity is neither present.
Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0.
Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1.
Return the integer as the final result.
Example 1:
Input: s = “42”
Output: 42
Explanation:
The underlined characters are what is read in and the caret is the current reader position.
Step 1: “42” (no characters read because there is no leading whitespace)
^
Step 2: “42” (no characters read because there is neither a ‘-‘ nor ‘+’)
^
Step 3: “42” (“42” is read in)
^
- Strip and see if there’s no string. Else, return
- Convert it to a list.
- Check sign and set sign variable to be 1 or -1. Delete the first item after sign is gotten (if +/-).
- While i int:
if not s.strip():
return 0slist=list(s.strip()) sign=1 if slist[0]=='-': sign=-1 if slist[0] in '+-': del slist[0] num=0 i=0 while i
- Regular Expression Matching
Hard
Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:
’.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Example 1:
Input: s = “aa”, p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:
Input: s = “aa”, p = “a”
Output: true
Explanation: ‘’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:
Input: s = “ab”, p = “.”
Output: true
Explanation: “.” means “zero or more (*) of any character (.)”.
- Backtracking, helper with s, p, i and j
- if j==len(p) return i==len(s)
- first condition is to check the non character match. Then character match
- if j+1 bool:
return self.is_match(s, p, 0,0)@lru_cache
def is_match(self, s, p, i, j):
if j==len(p):
return i==len(s)if j+1
- Container With Most Water
Medium
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.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
- left, right=N-1
- basic two pointerdef maxArea(self, heights: List[int]) -> int:
left=0
right=len(heights)-1max_area=0 while left
- 3Sum
Medium
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.
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].
Notice that the order of the output and the order of the triplets does not matter.
- sort the nums
- for each num, take the current num and convert into -target. Call two_sum
- In order to avoid duplicates (if i>0 and nums[i]==nums[i-1] continue)
- Within two_sum, if result is found, add (-target, nums[i], nums[j].
- Also for next num, increment i+1 and j+1 and then do a while loop to compare:
while i List[List[int]]:
nums.sort()
result=[]
for i, num in enumerate(nums):
if i>0 and nums[i]==nums[i-1]:
continue
self.two_sum(-num, nums, i, result)
return resultdef two_sum(self, target, nums, ti, result):
i=ti+1
j=len(nums)-1while itarget: j-=1 else: result.append([-target, nums[i], nums[j]]) i+=1 j-=1 while i
- 3Sum Closest
Medium
Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
- Sort the nums
- initialize closest to sum(nums[:3])
- for loop through 0 to N-2 and then while loop (ii=i+1, j=N-1)
- csum = i+ii+jj
- if csum==target, return
- if csum-target int:
if len(nums)<=3:
return sum(nums)nums.sort() N=len(nums) closest=sum(nums[:3]) for i in range(N-2): ii=i+1 jj=N-1 while ii
- Letter Combinations of a Phone Number
Medium
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
- Backtracking. Contruct a map of integer to keys- {2:”abc”….}
- helper with index, curr, result and map
- if len(curr)==len(digits), result.append(curr) and return
- if index>len(digits), return
- for c in mapp[digits[index]]:
bt(curr+c, digits, index+1, mapp)def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return None
result=[]
mapp = {“2”: “abc”, “3”: “def”, “4”: “ghi”, “5”: “jkl”, “6”: “mno”, “7”: “pqrs”, “8”: “tuv”, “9”: “wxyz”}
self.bt(digits, 0, result, ‘’, mapp)
return resultdef bt(self, digits, i, result, curr, mapp):
if len(curr)==len(digits):
result.append(curr)
returnif i>=len(digits): return for c in mapp[digits[i]]: self.bt(digits, i+1, result, curr+c, mapp)
T: O(4^n)
S: O(n) - not counting the result space, stack space is N. Goes to the depth of the number of digits, since when we reach the number of digits, we return.
- 4Sum
Medium
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
- N^3 solution
- for i in range(N), j in range(i+1, N), ii=j+1, jj=N-1
- Do a two_sum for ii and jjdef fourSum(self, nums: List[int], target: int) -> List[List[int]]:
N = len(nums)
nums.sort()
result = set()
for i in range(N):
for j in range(i + 1, N):
itarget = target - (nums[i] + nums[j])
ii = j + 1
jj = N - 1
while ii < jj:
csum = nums[ii] + nums[jj]
if csum < itarget:
ii += 1
elif csum > itarget:
jj -= 1
else:
result.add((nums[i], nums[j], nums[ii], nums[jj]))
ii += 1
jj -= 1
return result
T: O(n^3)
S: O(n) - for sorting
- Remove Nth Node From End of List
Medium
Given the head of a linked list, remove the nth node from the end of the list and return its head.
Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
- Two pointer. Move fast to n
- Move slow and fast together
- if not fast, return head.nextdef removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
fast=headfor i in range(n): fast=fast.next if not fast: return head.next slow=head while fast.next: fast=fast.next slow=slow.next slow.next=slow.next.next return head
T: O(n)
S: O(1)
- Generate Parentheses
Medium
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
- Use helper - n, curr, result, open, close
- if open List[str]:
result = []
self.generate_parenthesis(n, “”, result, 0, 0)
return resultdef generate_parenthesis(self, n, curr, result, open, close):
if len(curr) == n * 2:
result.append(curr)
return
if open < n:
self.generate_parenthesis(n, curr + ‘(‘, result, open + 1, close)if close < open: self.generate_parenthesis(n, curr + ')', result, open, close + 1)
T: O(2^2n) - O(4^n) - The tree can potentially have 2^{2n} nodes because at each step (with up to 2n steps), it can choose to add an opening or closing parenthesis. nth catalan number is 4^n….
S: O(n) - stack until twice the depth of n
- Merge k Sorted Lists
Hard
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.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
- Use heap. Iterate through each list and append first item of the list and list (if list exists)
- construct a new LinkedList
- Pop from heap, create new node with value and append to the list
- If popped list.next, then add to heapdef mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
pq=[]for i, each in enumerate(lists): if each: heapq.heappush(pq, (each.val, i, each)) head=sent=ListNode(0) while pq: val, idx, lst = heapq.heappop(pq) head.next=ListNode(val) head=head.next if lst.next: heapq.heappush(pq, (lst.next.val, idx, lst.next)) return sent.next
T: O(nlogm) - m size of the LL and n is the total size of all LL together
S: O(m) - maximum of 3 nodes is kept in the heap (result is not counted)
- Swap Nodes in Pairs
Medium
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
- Hard, honestly. Recursive is easier.def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return headsecond = head.next prev = ListNode(0) while head and head.next: nxt = head.next head.next = nxt.next nxt.next = head prev.next = nxt head = head.next prev = nxt.next return second # if head and head.next: # temp=head.next # head.next=self.swapPairs(temp.next) # temp.next=head # return temp # return head
T: O(n)
S: O(n) - stack used for recursion
- Next Permutation
Medium
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
[12431]->[13124]
1. From the last identify the first drop from an increase (target=N-1, while i>0 and nums[target-1]>nums[target], target-=1
2. if target==0, then reverse and return (since the sub permutation is already done)
3. target-=1 (to be swapped, since we are breaking when target-1 None:
target=len(nums)-1
while target>0 and nums[target-1]>=nums[target]:
target-=1
if target==0:
nums.reverse()
return
target-=1
source=len(nums)-1
while nums[source]<=nums[target]:
source-=1
nums[source], nums[target]=nums[target], nums[source]
left=target+1
right=len(nums)-1
while left
- Search in Rotated Sorted Array
Medium
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.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
- Binary search with a twist.
- if nums[mid]==target: return mid
- if nums[low]<=nums[mid]:
if nums[low]<=target int:
low=0
high=len(nums)-1while low<=high: mid=(low+high)//2 if nums[mid]==target: return mid elif nums[low]<=nums[mid]: if nums[low]<=target
- Find First and Last Position of Element in Sorted Array
Medium
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Example 3:
Input: nums = [], target = 0
Output: [-1,-1]
- Binary search - bisect_left and bisect_right
- bisect_left: if arr[mid] List[int]:
left=self.bisect_left(nums, target)dd
right=self.bisect_right(nums, target)if left==right: return [-1,-1] else: return [left, right-1]def bisect_left(self, nums, target):
left=0
right=len(nums)-1while left<=right: mid=(left+right)//2 if nums[mid]
- Valid Sudoku
Medium
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[[“5”,”3”,”.”,”.”,”7”,”.”,”.”,”.”,”.”]
,[“6”,”.”,”.”,”1”,”9”,”5”,”.”,”.”,”.”]
,[”.”,”9”,”8”,”.”,”.”,”.”,”.”,”6”,”.”]
,[“8”,”.”,”.”,”.”,”6”,”.”,”.”,”.”,”3”]
,[“4”,”.”,”.”,”8”,”.”,”3”,”.”,”.”,”1”]
,[“7”,”.”,”.”,”.”,”2”,”.”,”.”,”.”,”6”]
,[”.”,”6”,”.”,”.”,”.”,”.”,”2”,”8”,”.”]
,[”.”,”.”,”.”,”4”,”1”,”9”,”.”,”.”,”5”]
,[”.”,”.”,”.”,”.”,”8”,”.”,”.”,”7”,”9”]]
Output: true
- defaultdict(set) for rows, cols and boxes
- box formula is (r//3)*3+(c//3)def isValidSudoku(self, board: List[List[str]]) -> bool:
rows = defaultdict(set)
cols = defaultdict(set)
boxes = defaultdict(set)R = len(board) C = len(board[0]) for r in range(R): for c in range(C): if board[r][c] == '.': continue if board[r][c] in rows[r]: return False rows[r].add(board[r][c]) if board[r][c] in cols[c]: return False cols[c].add(board[r][c]) box = (r // 3) * 3 + (c // 3) if board[r][c] in boxes[box]: return False boxes[box].add(board[r][c]) return True
T: O(MN) - 99 - O(81) - O(1)
S: O(9+9+9) - O(27) - O(1) - 9 rows, 9 cols and 9 boxes
- Count and Say
Medium
The count-and-say sequence is a sequence of digit strings defined by the recursive formula:
countAndSay(1) = “1”
countAndSay(n) is the run-length encoding of countAndSay(n - 1).
Run-length encoding (RLE) is a string compression method that works by replacing consecutive identical characters (repeated 2 or more times) with the concatenation of the character and the number marking the count of the characters (length of the run). For example, to compress the string “3322251” we replace “33” with “23”, replace “222” with “32”, replace “5” with “15” and replace “1” with “11”. Thus the compressed string becomes “23321511”.
Given a positive integer n, return the nth element of the count-and-say sequence.
Example 1:
Input: n = 4
Output: “1211”
Explanation:
countAndSay(1) = “1”
countAndSay(2) = RLE of “1” = “11”
countAndSay(3) = RLE of “11” = “21”
countAndSay(4) = RLE of “21” = “1211”
- Tricky. Initialize s=”1”
- Iterate until n-1 (since 1 is already the first iteration)
- count=0, start=s[0], temp=’’
- for l in s:
if start==l:
increment count
else:
append str(count) + start to temp
reset count=1 and start=l - As a cleanup, append to temp the last iteration
- s=tempdef countAndSay(self, n: int) -> str:
s=”1”for _ in range(n-1): count=0 temp='' start=s[0] for l in s: if start==l: count+=1 else: temp+=str(count)+start start=l count=1 temp+=str(count)+start s=temp return s
T: O(2^n) - For every iteration, the s approximately doubles
S: O(2^n)
- Combination Sum II
Medium
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
- Call helper with result, curr, target
- Skipping duplicates : if i!=index and candidates[i]==candidates[i-1]: continuedef combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
result = []
candidates.sort()
self.combination_sum(candidates, target, 0, [], result)
return resultdef combination_sum(self, candidates, target, index, curr, result):
if target == 0:
result.append(curr.copy())
return
if target < 0:
returnfor i in range(index, len(candidates)): if i != index and i > 0 and candidates[i] == candidates[i - 1]: continue self.combination_sum(candidates, target - candidates[i], i + 1, curr + [candidates[i]], result)
T: O(2^n)
S: O(n)
- Trapping Rain Water
Hard
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
- Two pointers
- Fast forward left and right until they are 0
- If left>right: return 0
- lmax=heights[0], rmax=heights[-1]
- while left<=right,
if current left is greater than right, then
1. set lmax
2. trapped+= lmax-hleft
3. left+=1 - Do reverse for rightdef trap(self, heights: List[int]) -> int:
if len(heights)==1:
return 0left = 0 while heights[left] == 0: left += 1 right = len(heights) - 1 while heights[right] == 0: right -= 1 if left > right: return 0 lmax = heights[0] rmax = heights[-1] trapped = 0 while left <= right: hleft = heights[left] hright = heights[right] if hleft < hright: lmax = max(hleft, lmax) trapped += lmax - hleft left += 1 else: rmax = max(rmax, hright) trapped += rmax - hright right -= 1 return trapped
T: O(n)
S: O(1)
- Multiply Strings
Medium
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.
Example 1:
Input: num1 = “2”, num2 = “3”
Output: “6”
Example 2:
Input: num1 = “123”, num2 = “456”
Output: “56088”
- Regular multiplication. Initialize result to [0]* (N1+N2)
- Outer loop is reversed(num1) and inner loop is reversed(num2)
- Initialize temp=pos (which was originally len(result)-1
- During each iteration,
result[temp]+= n1*n2
result[temp-1]+= result[temp]//10
result[temp]%=10
temp-=1 (for inner loop) - pos-=1 for outer loop
- Finally, we need to skip off all the leading zeroes and return the string
class Solution:
def multiply(self, num1: str, num2: str) -> str:
N1=len(num1)
N2=len(num2)
result=[0]*(N1+N2)
pos=len(result)-1
for n1 in reversed(num1):
temp=pos
for n2 in reversed(num2):
result[temp]+=int(n1)*int(n2)
result[temp-1]+=result[temp]//10
result[temp]%=10
temp-=1
pos-=1
pt=0
while pt
- Next Permutation
Medium
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]
- Use a maskdef permuteUnique(self, nums: List[int]) -> List[List[int]]:
nums.sort()
mask=0
result=[]
self.helper(nums, [], result, mask)
return resultdef helper(self, nums, curr, result, mask):
if mask ==(1<0 and nums[i]==nums[i-1] and not mask&(1«(i-1)):
continue
self.helper(nums, curr+[nums[i]], result, (mask | (1«i></i>
- Permutations II
Medium
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
- Call helper with curr, and result
- Iterate through i, len(nums) and invoke helper.
- Add nums[i] to curr but pass nums[:i]+nums[i+1:] to helper
self.helper(nums[:i]+nums[i+1:], curr=[nums[i]], result)
T: N! (n steps for each permutation)
S: O(N) not counting the result
- Rotate Image
Medium
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
- Flip and reverse
- While flipping range(R) but C=range(r)def rotate(self, matrix: List[List[int]]) -> None:
R=len(matrix)
C=len(matrix[0])for r in range(R): for c in range(r): matrix[r][c], matrix[c][r]=matrix[c][r], matrix[r][c] for r in range(R): matrix[r].reverse()
T: O(n*m)
S: O(1)
- Group Anagrams
Medium
Share
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.
Example 1:
Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mapp = defaultdict(list)
for st in strs:
mapp[tuple(sorted(st))].append(st)
return [v for k,v in mapp.items()]
T: O(N*KlogK)
S: O(NK)
K = maximum length of the string in strs
- Pow(x, n)
Medium
Implement pow(x, n), which calculates x raised to the power n (i.e., xn).
Example 1:
Input: x = 2.00000, n = 10
Output: 1024.00000
Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100
- If negative, make it positive and x=1/x
- Loop until x and divide n//2 and xx. But before that, if odd, append to result (result=resultx), n-=1def myPow(self, x: float, n: int) -> float:
result=1if n<0: n=-n x=1/x while n: if n%2!=0: result=result*x n-=1 x*=x n//=2 return result
T: O(logn)
S: O(1)
- N-Queens
Hard
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space, respectively.
Example 1:
Input: n = 4
Output: [[“.Q..”,”…Q”,”Q…”,”..Q.”],[”..Q.”,”Q…”,”…Q”,”.Q..”]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
- Backtracking and post processing is slightly tricky.
- p=len(curr) and p+q in anti_diag and p-q in diag and q not in curr
- remaining dot is n-p-1def solveNQueens(self, n: int) -> List[List[str]]:
res=[]
self.solve_n_queens(n, [], [], [], res)result=[] for r in res: curr=[] for pos in r: st=('.'*pos) + 'Q' + '.'*(n-pos-1) curr.append(st) result.append(curr) return resultdef solve_n_queens(self, n, curr, diag, anti_diag, result):
p=len(curr)
if p==n:
result.append(curr.copy())
returnfor q in range(n): if q not in curr and (p+q) not in anti_diag and (p-q) not in diag: self.solve_n_queens(n, curr+[q], diag+[p-q], anti_diag +[p+q], result)
T: O(n!)
S: O(n^2) - board is of size N*N
- Jump Game
Medium
You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
Example 1:
Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
- if i>max_reach (initialized to 0), return False
- max_reach=max(max_reach, i+num)def canJump(self, nums: List[int]) -> bool:
max_reach=0 for i, num in enumerate(nums): if i>max_reach: return False max_reach=max(max_reach, i+num) return True
T: O(n)
S: O(1)
- Merge Intervals
Medium
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.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
- set start interval to be mstart and mend
- Iterate through intervals[1:]
- If mstartmend, then
1. add old mstart and mend to result
2. mstart,mend=cstart,cend - Finally before exiting, add mstart, mend to result to capture dangling onedef merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return Noneintervals.sort(key=lambda x: x[0]) mstart,mend=intervals[0] result=[] for cstart, cend in intervals[1:]: if cstart<=mend and mstart<=cend: mstart=min(cstart, mstart) mend=max(cend, mend) elif cstart>mend: result.append([mstart, mend]) mstart, mend=cstart, cend result.append([mstart, mend]) return result
T:O(nlogn)
S:O(n) - for sorting
- Insert Interval
Medium
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.
Note that you don’t need to modify intervals in-place. You can make a new array and return it.
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
- Three conditions.
- if cendnend: #the new interval has passed
result.append(nstart,nend)
result.extend(intervals[i:])
return result - else: #overlap
nstart=min(nstart, cstart)
nend =max(nend,cend) - finally, add residual - result.append(nstart,nend)def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
nstart, nend=newIntervalresult=[] for i,interval in enumerate(intervals): cstart, cend=interval if cendnend: result.append([nstart, nend]) result.extend(intervals[i:]) return result else: nstart=min(nstart, cstart) nend=max(nend, cend) result.append([nstart, nend]) return result
T:O(n)
S:O(1)
- Unique Paths
Medium
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
Input: m = 3, n = 7
Output: 28
- DP - recursive and tabulation.
- For tabulation, populate a m*n dp with 1 and start R,C loop with 1,R and 1,C
- For recursion, the way to think about is a tree.
- base case is (r,c)=(R-1, C-1): return 1
- if r=R or c==C: return 0
- counts=self.helper(R, C, r+1, c) + self.helper(R, C, r, c+1)def uniquePaths(self, m: int, n: int) -> int:
return self.helper(m, n, 0,0, {})def helper(self, R, C, r, c, memo):
if (r,c) in memo:
return memo[(r,c)]if (r,c) == (R-1, C-1): return 1 if r==R or c==C: return 0 counts=self.helper(R, C, r+1, c, memo) counts+=self.helper(R, C, r, c+1, memo) memo[(r,c)]=counts return countsdef uniquePaths(self, m: int, n: int) -> int:
R = m
C = n
dp = [[1] * C for _ in range(R)]
for r in range(1, R):
for c in range(1, C):
dp[r][c] = (dp[r - 1][c] + dp[r][c - 1])
return dp[-1][-1]
T: O(nm)
S: O(nm)
- Valid Number
Hard
Given a string s, return whether s is a valid number.
For example, all the following are valid numbers: “2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”, while the following are not valid numbers: “abc”, “1a”, “1e”, “e3”, “99e2.5”, “–6”, “-+3”, “95a54e53”.
Formally, a valid number is defined using one of the following definitions:
An integer number followed by an optional exponent.
A decimal number followed by an optional exponent.
An integer number is defined with an optional sign ‘-‘ or ‘+’ followed by digits.
A decimal number is defined with an optional sign ‘-‘ or ‘+’ followed by one of the following definitions:
Digits followed by a dot ‘.’.
Digits followed by a dot ‘.’ followed by digits.
A dot ‘.’ followed by digits.
An exponent is defined with an exponent notation ‘e’ or ‘E’ followed by an integer number.
The digits are defined as one or more digits.
Example 1:
Input: s = “0”
Output: true
- Key principles:
1. Dot cannot come after e
2. Sign has to be [0] or just after e [i-1]. If i>0 and s[i-1].lower()!=e: return False
3. If e seen, then number must be seen after that. So, return number_seen - Four variables: is_e_seen, is_number_seen, is_dot_seen and is_sign_seen
- If digit faced, number_seen=True
- If dot seen and (dot already seen or e_seen), return False. Else, set the var
- If e_seen and (e already seen or not number_seen) (first e), return False. Else set var and number_seen=False
- else, return False
- return number_seendef isNumber(self, s: str) -> bool:
s=s.strip()is_dot_seen=False is_e_seen=False is_number_seen=False is_sign_seen=False for i,c in enumerate(s): if c in '1234567890': is_number_seen=True elif c=='.': if is_dot_seen or is_e_seen: return False is_dot_seen=True elif c in '+-': if i>0 and s[i-1].lower()!='e': return False is_sign_seen=True elif c in 'eE': if is_e_seen or not is_number_seen: return False is_e_seen=True is_number_seen=False else: return False return is_number_seen
T: O(N)
S: O(1)
- Text Justification
Hard
Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified, and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
Example 1:
Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
“This is an”,
“example of text”,
“justification. “
]
Example 2:
Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
“What must be”,
“acknowledgment “,
“shall be “
]
Explanation: Note that the last line is “shall be “ instead of “shall be”, because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = [“Science”,”is”,”what”,”we”,”understand”,”well”,”enough”,”to”,”explain”,”to”,”a”,”computer.”,”Art”,”is”,”everything”,”else”,”we”,”do”], maxWidth = 20
Output:
[
“Science is what we”,
“understand well”,
“enough to explain to”,
“a computer. Art is”,
“everything else we”,
“do “
]
- Very hard problemdef fullJustify(self, words, maxWidth):
N = len(words)
L = maxWidth
i = 0
result = []def get_kwords(i): curr_len = len(words[i]) k = 1 while i + k < N: next_len = len(words[i + k]) + 1 if curr_len + next_len <= L: k += 1 curr_len += next_len else: break return k def insert_space(i, k): line = ' '.join(words[i:i + k]) if k == 1 or i + k == N: spaces = L - len(line) line += ' ' * spaces return line else: spaces = L - len(line) + (k - 1) space = spaces // (k - 1) left_words = spaces % (k - 1) if left_words > 0: line = (" " * (space + 1)).join(words[i:i + left_words]) line += (" " * (space + 1)) line += (" " * space).join(words[i + left_words: i + k]) else: line = (" " * space).join(words[i:i + k]) return line i = 0 while i < N: word_count = get_kwords(i) line = insert_space(i, word_count) result.append(line) i += word_count return result
T: O(n) - length of words*average length of the word
S: O(n)
- Simplify Path
Medium
Given an absolute path for a Unix-style file system, which begins with a slash ‘/’, transform this path into its simplified canonical path.
In Unix-style file system context, a single period ‘.’ signifies the current directory, a double period “..” denotes moving up one directory level, and multiple slashes such as “//” are interpreted as a single slash. In this problem, treat sequences of periods not covered by the previous rules (like “…”) as valid names for files or directories.
The simplified canonical path should adhere to the following rules:
It must start with a single slash ‘/’.
Directories within the path should be separated by only one slash ‘/’.
It should not end with a slash ‘/’, unless it’s the root directory.
It should exclude any single or double periods used to denote current or parent directories.
Return the new path.
- Stack
- Split on ‘/’ and iterate
- If c in [’’, ‘ ‘, ‘.’] - single space, no space or dot, then continue
- If c==’..’ and stack, pop()
- Else append to stack
- return ‘/’+’/’.join(stack)def simplifyPath(self, path: str) -> str:
path=path.split(‘/’)stack=[] for p in path: if p in ['.', ' ', '']: continue elif p=='..': if stack: stack.pop() else: stack.append(p) return '/'+'/'.join(stack)
T: O(n)
S: O(n)
- Edit Distance
Medium
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
Example 1:
Input: word1 = “horse”, word2 = “ros”
Output: 3
Explanation:
horse -> rorse (replace ‘h’ with ‘r’)
rorse -> rose (remove ‘r’)
rose -> ros (remove ‘e’)
- dp = [0]* C+1*R+1
- dp[r][0]=r, dp[0][c]=cdef minDistance(self, word1: str, word2: str) -> int:
R=len(word1)
C=len(word2)
dp=[[0] * (C+1) for _ in range(R+1)]
for r in range(R+1):
dp[r][0]=rfor c in range(C+1): dp[0][c]=c for r in range(1, R+1): for c in range(1, C+1): if word1[r-1]==word2[c-1]: dp[r][c]=dp[r-1][c-1] else: dp[r][c]=1+min(dp[r-1][c-1], dp[r][c-1], dp[r-1][c]) return dp[-1][-1]
T: O(MN)
S: O(MN)
- Sort Colors
Medium
Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.
We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.
You must solve this problem without using the library’s sort function.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]
- left, right, one_start
- If 1, just increment left
- if 2, swap with right and decrement right
- if 0, swap os with left and increment osdef sortColors(self, nums: List[int]) -> None:
left=0
right=len(nums)-1
ostart=0while left<=right: if nums[left]==2: nums[left],nums[right]=nums[right],nums[left] right-=1 elif nums[left]==0: nums[left], nums[ostart]= nums[ostart], nums[left] ostart+=1 left+=1 elif nums[left]==1: left+=1
T: O(n)
S: O(1)
- Minimum Window Substring
Hard
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.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output: “BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output: “a”
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = “a”, t = “aa”
Output: “”
Explanation: Both ‘a’s from t must be included in the window.
Since the largest window of s only has one ‘a’, return empty string.
- Sliding window.
class Solution:
def minWindow(self, s: str, t: str) -> str:
if len(t)>len(s):
return “”
counter=Counter(t)
ws=0
matches=0
min_window=float('inf')
min_string=""
for we, swe in enumerate(s):
if swe in counter:
counter[swe]-=1
if counter[swe]==0:
matches+=1
while matches ==len(counter):
sws=s[ws]
if we-ws+10:
matches-=1
ws+=1
return min_string
T: O(S+T)
S: O(S+T)
- Subsets
Medium
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
- Backtracking - Skip, Pick
- helper has index and current
- if index==len(nums), then add to result and return
- skip: self.bt(nums, result, index+1, curr)
- pick: self.bt(nums, result, index+1, curr+[nums[index]])def subsets(self, nums: List[int]) -> List[List[int]]:
result=[]
self.bt(nums, 0, [], result)
return resultdef bt(self, nums, index, curr, result):
if index==len(nums):
result.append(curr.copy())
returnself.bt(nums, index+1, curr, result) self.bt(nums, index+1, curr+[nums[index]], result)
T: O(N* 2^n) - Copying is another N
S:O(n) - Curr space
- Largest Rectangle in Histogram
Hard
Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Example 1:
Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.
- Monotonic increasing stack
- append 0 to heights so that it pops off based on the last element
- initialize stack to -1 because it makes it easier for calculating the width (W=i-stack[-1]-1)def largestRectangleArea(self, heights: List[int]) -> int:
heights.append(0)
stack = [-1]
max_area = 0
for i, height in enumerate(heights):
while stack and heights[stack[-1]] > height:
ii = stack.pop()
H = heights[ii]
W = i - stack[-1]-1
max_area = max(max_area, H * W)
stack.append(i)
return max_area
T: O(n)
S: O(n)
- Validate Binary Search Tree
Medium
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.
Example 1:
Input: root = [2,1,3]
Output: true
- Helper with -sys.maxsize and sys.maxsize as mini and maxi
- Validate left and right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.is_valid(root, -sys.maxsize, sys.maxsize)
def is_valid(self, node, mini, maxi):
if not node:
return True
if not mini bool:
stack=[]
node=root
prev=float('-inf')
while node or stack:
if node:
stack.append(node)
node=node.left
elif stack:
node=stack.pop()
if prev>=node.val:
return False
prev=node.val
node=node.right
return True
T: O(n)
S: O(n)
- Binary Tree Level Order Traversal
Medium
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).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
- Generic level order traversal
- for _ in range(len(queue)def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return None
node=rootqueue=deque([root]) result=[] while queue: level=[] for _ in range(len(queue)): node=queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result
T: O(n)
S: O(n)
- Binary Tree Zigzag Level Order Traversal
Medium
Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
- Level order traversal. But for level use deque (append and appendleft)def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []node=root queue=deque([root]) left_to_right=True result=[] while queue: level=deque([]) for _ in range(len(queue)): node=queue.popleft() if left_to_right: level.append(node.val) else: level.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) left_to_right=not left_to_right result.append(level) return result
T: O(n)
S: O(n)
- Path Sum II
Medium
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
- Root to leaf with a target_sum - DFS (track target_sum, curr)
- In the helper, if node.val==target_sum and not node.left and not node.right: result.add(curr.copy())
- if not node: return
- if node.left:
self.dfs(node.left, target_sum-node.val, curr+[node.val], result) - same with node.right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return None
result=[]
self.path_sum(root, targetSum, [], result)
return result
def path_sum(self, node, target, curr, result):
if not node.left and not node.right and target==node.val:
curr+=[node.val]
result.append(curr.copy())
return
if node.left:
self.path_sum(node.left, target-node.val, curr+[node.val], result)
if node.right:
self.path_sum(node.right, target-node.val, curr+[node.val], result)
BFS has a lot of space overhead, since we need to maintain all the paths in the queue
T: O(n^2) - Worst case, if it is a complete binary tree, we need to traverse through N/2 leaves.
S: O(n)
- Populating Next Right Pointers in Each Node
Medium
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example 1:
Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with ‘#’ signifying the end of each level.
- Level order traversal
- prev = None
- If prev, prev.next=node
- prev=nodedef connect(self, root: ‘Optional[Node]’) -> ‘Optional[Node]’:
if not root:
return root
queue = deque([root])
while queue:
prev = None
for _ in range(len(queue)):
node = queue.popleft()
if not prev:
prev = node
else:
prev.next = node
prev = node
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
T: O(n)
S: O(n)
- Best Time to Buy and Sell Stock II
Medium
You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
- Just keep comparing current price to previous price and accumulate them into profitdef maxProfit(self, prices: List[int]) -> int:
profit=0
for i in range(1, len(prices)):
if prices[i-1]
COVERED
COVERED
- Longest Consecutive Sequence
Medium
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
- Hold all the nums in a set
- Entry when num-1 is not in set (least number)
- count=1, while count+num is not in set: count+=1
- set max_countdef longestConsecutive(self, nums: List[int]) -> int:
hset=set(nums)max_count=0 for num in nums: if num-1 not in hset: count=1 while num+count in hset: count+=1 max_count=max(count, max_count) return max_count
T:O(n)
S:O(n)
- Sum Root to Leaf Numbers
Medium
You are given the root of a binary tree containing digits from 0 to 9 only.
Each root-to-leaf path in the tree represents a number.
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
A leaf node is a node with no children.
- BFS - queue.append((root, str(root.val))
- Keep adding to the str. If not node.left and not node.right, total+=int(str_val)def sumNumbers(self, root: Optional[TreeNode]) -> int:
if not root:
return 0queue=deque([(root, str(root.val))]) result=0 while queue: node, sval=queue.popleft() if not node.left and not node.right: result+=int(sval) continue if node.left: queue.append((node.left, sval+str(node.left.val))) if node.right: queue.append((node.right, sval+str(node.right.val))) return result
T:O(n)
S:O(n)
- Palindrome Partitioning
Medium
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.
Example 1:
Input: s = “aab”
Output: [[“a”,”a”,”b”],[“aa”,”b”]]
Example 2:
Input: s = “a”
Output: [[“a”]]
- Simple BT recursion (helper has curr and result)
- At each level iterate from 1, len(s)+1 and check if s[:i] is palindrome.
- If yes, then call the helper recursively with s[i:], curr=[s[:i]]
S: O(N2^N) - 2N - there could be 2N possible substrings in the worst case
T: N2^N
N=3, aaa, the first level of the tree is [a]aa, [aa][a], [aaa]
Essentially, there are 8 nodes in the tree, which is 2^3
- Clone Graph
Medium
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}
Test case format:
For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
- BFS
- Keep a copy dictionary, copy={root:Node(root.val)}
- Upon popping, iterate through neis,
if nei not in copy:
copy[nei]=Node(nei.val)
queue.append(nei)
copy[node].neighbours.append(copy[nei]) - return copy[root]
from typing import Optional
class Solution:
def cloneGraph(self, root: Optional[‘Node’]) -> Optional[‘Node’]:
if not root:
return root
queue=deque([root])
copy={root: Node(root.val)}
while queue:
node=queue.popleft()
for nei in node.neighbors:
if nei not in copy:
copy[nei]=Node(nei.val)
queue.append(nei)
copy[node].neighbors.append(copy[nei])
return copy[root]
T: O(V+E)
S: O(V)
- Copy List with Random Pointer
Medium
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.
- Have a copy map and do two traversals.
- First time copy[node]=Node(node.val)
- Next time, copy[node].next=copy.get(node.next) & copy[node].random=copy.get(node.random)
- return copy[head]def copyRandomList(self, head: ‘Optional[Node]’) -> ‘Optional[Node]’:
if not head:
return None
copy={head:Node(head.val)}node=head while node: if node not in copy: copy[node]=Node(node.val) node=node.next node=head while node: copy[node].next=copy.get(node.next) copy[node].random=copy.get(node.random) node=node.next return copy[head]
T: O(N)
S: O(N)
- Word Break II
Hard
Share
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
Output: [“cats and dog”,”cat sand dog”]
- DP. Recursion
- Helper has curr and result
- if not s: result.append(curr.copy())
- for i in range(len(s)), call helper by skipping i (s[:i]+s[i+1:])def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words=set(wordDict)
N=len(s)
dp=[False]*(N+1)
dp[0]=Truefor i in range(N+1): for j in range(i): word=s[j:i] if word in words and dp[j]==True: dp[i]=True return dp[-1]
T: O(nmk), n being the size of the string, m is the length of the worddict and k is the average length of the word in the worddict
S: O(n)
- Word Break II
Hard
Share
Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
Output: [“cats and dog”,”cat sand dog”]
- DP. Recursion
- Helper has curr and result
- if not s: result.append(curr.copy())
- for i in range(len(s)+1). Remember to loop until len(s)+1def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
result=[]
self.helper(s, 0, set(wordDict), [], result)
return resultdef helper(self, s, index, words, curr, result):
if not s:
result.append(‘ ‘.join(curr))
returnfor i in range(len(s)+1): if s[:i] in words: self.helper(s[i:], i, words, curr+[s[:i]], result)
T: O(2^n) - Worst case, every letter is a word. String concat O(n), since for each recursive call n/k (k=average length of a valid word) = O(2^n*n)
S: O(n)
- Reorder List
Medium
You are given the head of a singly linked-list. The list can be represented as:
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.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
- Find mid
- Reverse the second half
- Merge both lists.def reorderList(self, head: Optional[ListNode]) -> None:
fast=head
slow=headwhile fast.next and fast.next.next: slow=slow.next fast=fast.next.next second=slow.next slow.next=None #reverse mid prev=None while second: nxt=second.next second.next=prev prev=second second=nxt #merge head1=head head2=prev while head2: nxt=head1.next head1.next=head2 head1=head2 head2=nxt
T: O(n)
S: (1)
- LRU Cache
Medium
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.
Example 1:
Input
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
- init - head.next=tail, tail.prev=head, self.mapp={}
- get - if not key in self.mapp, return -1
else:
ret_node=self.mapp[key],
self.remove_node(ret_node)
del self.mapp[key]
self.move_to_first(ret_node)
self.mapp[key]=ret_node - put - nnode=Node(key,val)
if key in self.mapp:
per_node=self.mapp[key]
self.remove_node(per_node)
del self.mapp[key]
self.move_to_first(nnode)
self.mapp[key]=nnodeif len(self.mapp)>self.capacity: last_node=self.tail.prev self.remove_node(last_node) del self.mapp[last_node.key] - move_to_first
nxt=self.head.next
self.head.next=node
node.prev=self.head
node.next=nxt
next.prev=node - remove_node
prev=node.prev
node.prev.next=node.next
node.next.prev=prev
class Node:
def __init__(self, key, val, prev=None, next=None):
self.key=key
self.val=val
self.prev=prev
self.next=next
class LRUCache:
def \_\_init\_\_(self, capacity: int):
self.capacity=capacity
self.head=Node(0,0)
self.tail=Node(0,0)
self.head.next=self.tail
self.tail.prev=self.head
self.mapp={}
def get(self, key: int) -> int:
if key not in self.mapp:
return -1
node=self.mapp[key]
self.remove_node(node)
self.add_to_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.mapp:
node=self.mapp[key]
node.val=value
self.remove_node(node)
self.add_to_front(node)
else:
node=Node(key, value)
self.add_to_front(node)
self.mapp[key]=node
if len(self.mapp)>self.capacity:
last_node=self.tail.prev
self.remove_node(last_node)
del self.mapp[last_node.key]
def remove_node(self, node):
prev=node.prev
node.prev.next=node.next
node.next.prev=prev
def add_to_front(self, node):
pnext= self.head.next
self.head.next=node
node.prev=self.head
pnext.prev=node
node.next=pnext
T: O(1)
S: O(capacity)
- Min Stack
Medium
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
- Unlike assumption, we have to maintain two stacks - one for values and the other one for min so far.
- While adding a value, check if the current value is lesser than the top most value on the min_stack
- Add the minimum of the top value, incoming value to the top of the min_stack.
class MinStack:
def \_\_init\_\_(self):
self.stack=[]
self.min_stack=[]
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack:
self.min_stack.append(val)
else:
mini=min(val, self.min_stack[-1])
self.min_stack.append(mini)
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
T: O(1)
S: O(n)
- Find Peak Element
Medium
A peak element is an element that is strictly greater than its neighbors.
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.
You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
- Binary search.
- if (mid==0 or nums[mid]>nums[mid-1]) and (mid==N-1 or nums[mid]>nums[mid+1], return mid
- elif nums[low]<=nums[mid]: low+=1 (too far - we need mid-1, so moving left ahead)
- else, high-=1
Remember that unlike binary search, we aren’t doing low=mid+1, It’s just low+=1
def findPeakElement(self, nums: List[int]) -> int:
N=len(nums)
left=0
right=N-1
while left<=right:
mid=(left+right)//2
if (mid==0 or nums[mid]>nums[mid-1]) and (mid==N-1 or nums[mid]>nums[mid+1]):
return mid
elif nums[left]<=nums[mid]:
left+=1
else:
right-=1
Alternative:
def findPeakElement(self, nums: List[int]) -> int:
N=len(nums)
left=0
right=N-1
if left==right:
return left
while left
- Binary Search Tree Iterator
Medium
Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):
BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.
You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.
Do an inorder traversal
- init - set node=root and stack=[]
- next - modified inorder.(ensure that stack is always populated)
while node:
stack.append(node)
node=node.left
nxt=stack.pop()
return_val=nxt.val
node=node.right
return return_val - has_next:
return stack or node
class BSTIterator:
def \_\_init\_\_(self, root: Optional[TreeNode]):
self.stack=[]
self.node=root
def next(self) -> int:
while self.node:
self.stack.append(self.node)
self.node=self.node.left
nxt=self.stack.pop()
ret_val=nxt.val
self.node=nxt.right
return ret_val
def hasNext(self) -> bool:
return self.stack or self.node
T: O(n)
S: O(n)
- Consecutive Numbers
Medium
SQL Schema
Table: Logs
+————-+———+
| Column Name | Type |
+————-+———+
| id | int |
| num | varchar |
+————-+———+
In SQL, id is the primary key for this table.
id is an autoincrement column.
Find all numbers that appear at least three times consecutively.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input:
Logs table:
+—-+—–+
| id | num |
+—-+—–+
| 1 | 1 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 1 |
| 6 | 2 |
| 7 | 2 |
+—-+—–+
Output:
+—————–+
| ConsecutiveNums |
+—————–+
| 1 |
+—————–+
Explanation: 1 is the only number that appears consecutively for at least three times.
select
distinct l1.num as ConsecutiveNums
from
Logs l1
join
Logs l2
on
l2.id=l1.id+1
join
Logs l3
on
l3.id=l2.id+1
where
l1.num=l2.num and l2.num=l3.num
- House Robber
Medium
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.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
- DP - initialize to N+1
- dp[1]=nums[0
- Iterate from 1 to N and
dp[i+1]=max(dp[i-1]+nums[i], dp[i])def rob(self, nums: List[int]) -> int:
dp=[0]*(len(nums)+1)
dp[1]=nums[0]for i in range(1, len(nums)): dp[i+1]=max(dp[i-1]+nums[i], dp[i]) return dp[-1]
T: O(n)
S: O(n)
- Binary Tree Right Side View
Medium
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.
- Level order traversal
- if i==level-1 (N-1), add to resultdef rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root: return None queue=deque([root]) result=[] while queue: level=len(queue) for i in range(level): node=queue.popleft() if i==level-1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result
T: O(n)
S: O(d) - tree diameter
- Number of Islands
Medium
Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input: grid = [
[“1”,”1”,”1”,”1”,”0”],
[“1”,”1”,”0”,”1”,”0”],
[“1”,”1”,”0”,”0”,”0”],
[“0”,”0”,”0”,”0”,”0”]
]
Output: 1
DFS
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
R=len(grid)
C=len(grid[0])
count=0
for r in range(R):
for c in range(C):
if grid[r][c]=='1':
self.dfs(grid, r, c, R, C)
count+=1
return count
def dfs(self, grid, r, c, R, C):
grid[r][c]='0'
neis = [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]
for nr, nc in neis:
if -1
- Course Schedule
Medium
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
- BFS and check if cycle exists
WHITE, GRAY, BLACK = 0,1,2
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph=defaultdict(list)
for u,v in prerequisites:
graph[u].append(v)
colors=defaultdict(int)
for u in range(numCourses):
if colors[u]==WHITE and self.has_cycle(u, graph, colors):
return False
return True
def has_cycle(self, node, graph, colors):
colors[node] = GRAY
for nei in graph[node]:
if colors[nei]==GRAY:
return True
elif colors[nei]==WHITE:
if self.has_cycle(nei, graph, colors):
return True
else:
continue
colors[node]=BLACK
return False
T: O(V+E)
S: O(V+E)
- Course Schedule II
Medium
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
- Topsort while checking is there’s no cycle
WHITE,GRAY,BLACK=0,1,2
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph=defaultdict(list)
for u,v in prerequisites:
graph[u].append(v)
colors=defaultdict(int)
tops=[]
for node in range(numCourses):
if colors[node]==WHITE:
if self.has_cycle(node, colors, graph, tops):
return []
return tops if len(tops)==numCourses else []
def has_cycle(self, node, colors, graph, tops):
colors[node]=GRAY
for nei in graph[node]:
if colors[nei]==GRAY:
return True
elif colors[nei]==WHITE:
if self.has_cycle(nei, colors, graph, tops):
return True
else:
continue
tops.append(node)
colors[node]=BLACK
return False
T: O(V+E)
S: O(V+E)
N/A
- Construct a Trie and add all words
- Do a dfs on Trie.
class TrieNode:
def __init__(self, val=None):
self.val = val
self.children = {}
self.end_node = False
class Trie:
def __init__(self):
self.root = TrieNode()
def add_word(self, word):
node = self.root
for c in word:
if c not in node.children:
nnode = TrieNode(c)
node.children[c] = nnode
node = node.children[c]
node.end_node = True
#
# def search(self, word):
# node = self.root
# for c in word:
# if c not in node.children:
# return False
# node = node.children[c]
# return node.end_node
class WordSearch:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
R = len(board)
C = len(board[0])
trie = Trie()
for word in words:
trie.add_word(word)
# print(trie)
result = []
self.num_words = len(words)
for r in range(R):
for c in range(C):
if board[r][c] in trie.root.children:
self.dfs(board, r, c, R, C, trie.root, result, "")
return result
def dfs(self, board, r, c, R, C, troot, result, curr):
if self.num_words == 0:
return
if troot.end_node:
result.append(curr)
troot.end_node = False
self.num_words -= 1
neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)]
for nr, nc in neis:
if -1 < nr < R and -1 < nc < C and board[nr][nc] in troot.children:
self.dfs(board, nr, nc, R, C, troot.children[board[nr][nc]], result, curr + board[nr][nc])
T: O(n4^L) - L is the length of the word in the dictionary
S: O(kL) - k number of words in the dictionary and L average length of the words
- House Robber II
Medium
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.
Example 1:
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
- Do houserobber twice (once with nums[1:] and second with nums[:-1]def rob(self, nums: List[int]) -> int:
if not nums: return 0
if len(nums)==1: return nums[0]skip_first=self.helper(nums[1:]) skip_last=self.helper(nums[:-1]) return max(skip_first, skip_last)
def helper(self, nums):
N=len(nums)
dp=[0]*(N+1)
dp[1]=nums[0]for i in range(1, N): dp[i+1]=max(dp[i-1]+nums[i], dp[i]) return dp[-1]
T: O(n)
S: O(n)
- Kth Largest Element in an Array
Medium
Given an integer array nums and an integer k, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
- For finding largest, create min_heap
- Keep pushing to heap. If len(heap)>k, pop
- return pq[0]
T: O(NlogK)
S: O(k)
(Also consider quickselect)
def findKthLargest(self, nums: List[int], k: int) -> int:
if not nums:
return -1
pivot=random.choice(nums)
left=[num for num in nums if num>pivot]
mid=[num for num in nums if num==pivot]
right=[num for num in nums if numL+M:
return self.findKthLargest(right, k-L-M)
return mid[0]
T: O(n) - average case - balanced partitioning. O(n^2) worst case - when the pivot is always chosen to be the smallest or largest in the array.
S: O(n) - storage of partitioned lists
- Basic Calculator II
Medium
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = “ 3/2 “
Output: 1
Example 3:
Input: s = “ 3+5 / 2 “
Output: 5
- Regular basic calculator
- Create an opset
- For digit. num*10+int(c)
- For open parens, just append op to stack and reset op and num (this is for starting a new context)
- For close parens or c in opset:
self.update()
set op=c
num=0
if c==’)’:
temp_num and while loop until stack[-1] is in opset
self.update(temp_num, stack.pop()) - the previous op - for c in s+’+’def calculate(self, s: str) -> int:
op=’+’
num=0
opset={‘+’,’-‘,’*’,’/’}stack=[] for c in s+'+': if c.isdigit(): num=num*10 + int(c) elif c==')' or c in opset: self.update(num, op, stack) op=c num=0 if c==')': tmp_num=0 while stack[-1] not in opset: tmp_num+=stack.pop() self.update(tmp_num, stack.pop(), stack) elif c=='(': stack.append(op) op='+' num=0 return sum(stack)def update(self, num, op, stack):
if op==’+’:
stack.append(num)
elif op==’-‘:
stack.append(-num)
elif op==’’:
prev=stack.pop()
stack.append(numprev)
elif op==’/’:
prev=stack.pop()
stack.append(int(prev/num))
T: O(n)
S: O(n)
- Basic Calculator II
Medium
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Example 1:
Input: s = “3+2*2”
Output: 7
Example 2:
Input: s = “ 3/2 “
Output: 1
Example 3:
Input: s = “ 3+5 / 2 “
Output: 5
- op=”+’, num=’0’, stack=[]
- Iterate through s and keep accumulating num if digit.
- If an operator is faced, call self.update(num, op, stack). Reset num and op to defaults
- return sum(stack)def calculate(self, s: str) -> int:
op=’+’
num=0stack=[] for c in s+'+': if c.isdigit(): num=num*10 +int(c) elif c in '+-/*': self.update(num, op, stack) op=c num=0 return sum(stack)def update(self, num, op, stack):
if op==’+’:
stack.append(num)
elif op==’-‘:
stack.append(-num)
elif op==’’:
prev=stack.pop()
stack.append(prevnum)
elif op==’/’:
prev=stack.pop()
stack.append(int(prev/num))
T: O(n)
S:O(n)
- Lowest Common Ancestor of a Binary Search Tree
Medium
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).”
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
- If p_valnode_val and q_val>node_val: node=node.right
- Else, we’ve found the split point, return node
T: O(N)
S: O(N)
- Lowest Common Ancestor of a Binary Tree III
Medium
Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).
Each node will have a reference to its parent node. The definition for Node is below:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”
- Similar to meeting point of LinkedList
- Find depth of both nodes using simple iteration (while node, node=node.parent)
- Compare the longest and shortest. Move longest to the level of shortest (for _ in range(ldepth-sdepth), lnode=lnode.parent)
- Move both lnode and snode up, lnode=lnode.parent, snode=snode.parent
- If they are equal return
T: O(N)
S: O(1)
- Delete Node in a Linked List
Medium
There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:
The value of the given node should not exist in the linked list.
The number of nodes in the linked list should decrease by one.
All the values before node should be in the same order.
All the values after node should be in the same order.
Custom testing:
For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
We will build the linked list and pass the node to your function.
The output will be the entire list after calling your function.
def deleteNode(self, node):
node.val=node.next.val
node.next=node.next.next
T: O(1)
S: O(1)
- Product of Array Except Self
Medium
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.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
- left and right =[1]*N
- left =(1,N) , right = reversed (range(N-1)
- left[i]=left[i-1]*nums[i-1]
- right[i]=right[i+1]*nums[i+1]def productExceptSelf(self, nums: List[int]) -> List[int]:
result = []
N = len(nums)left = [1] * (N) right = [1] * (N) for i in range(1, N): left[i] = left[i - 1] * nums[i - 1] for i in reversed(range(N - 1)): right[i] = right[i + 1] * nums[i + 1] for l, r in zip(left, right): result.append(l * r) return result
T: O(n)
S: O(n)
- Strobogrammatic Number II
Medium
Given an integer n, return all the strobogrammatic numbers that are of length n. You may return the answer in any order.
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Example 1:
Input: n = 2
Output: [“11”,”69”,”88”,”96”]
Example 2:
Input: n = 1
Output: [“0”,”1”,”8”]
- Recursion and build from inside.
- if num==0: return [’’]
- If num==1: return [‘0’,’1’,’8’]
- temp=build_strobogrammatic(num-2)
- for l in temp:
result.append(‘1’+l+’1’) (do for 69, 88, and 96) - if n!=num, result prefix and suffix 0def findStrobogrammatic(self, n: int) -> List[str]:
if not n:
return []
return self.find_stobogrammatic(n, n)def find_stobogrammatic(self, n, num):
if num == 0:
return [’’]
elif num == 1:
return [‘0’, ‘1’, ‘8’]
result = []
temp = self.find_stobogrammatic(n, num - 2)
for l in temp:
if num != n:
result.append(‘0’ + l + ‘0’)
result.append(‘1’ + l + ‘1’)
result.append(‘6’ + l + ‘9’)
result.append(‘8’ + l + ‘8’)
result.append(‘9’ + l + ‘6’)
return result
T: O(5^n)
S: O(5^n) - O(n/2) for call stack
- Group Shifted Strings
Medium
We can shift a string by shifting each of its letters to its successive letter.
For example, “abc” can be shifted to be “bcd”.
We can keep shifting the string to form a sequence.
For example, we can keep shifting “abc” to form the sequence: “abc” -> “bcd” -> … -> “xyz”.
Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.
Example 1:
Input: strings = [“abc”,”bcd”,”acef”,”xyz”,”az”,”ba”,”a”,”z”]
Output: [[“acef”],[“a”,”z”],[“abc”,”bcd”,”xyz”],[“az”,”ba”]]
- Maintain result=defaultdict(list)
- Iterate through each string. Calculate key for each string and push it to map
- Key calculation: Iterate through each s and compare against it’s first character (ord(c)-ord(s[0])) %26. Return a tuple of the ords as key. Note the s[0] instead of the usual ord(‘a’)
If it is not tuple and keep it as just a num string, then there’s no difference between 112 - 11,2 and 1,12
def groupStrings(self, strings: List[str]) -> List[List[str]]:
mapp=defaultdict(list)
for s in strings:
key=self.get_key(s)
mapp[key].append(s)
return [v for k,v in mapp.items()]
def get_key(self, s):
key=[]
for c in s:
k=(ord(c)-ord(s[0]))%26
key.append(k)
return tuple(key)
T: O(nk) - we iterate over all the characters of all the strings.
S: O(nk) - we store the string and their hashvalue in the map
- Meeting Rooms II
Medium
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]]
Output: 1
- Sort the meeting rooms by start time
- Add only the end to the pq
- if the next meeting has start time which is >= than the end time of the top of the pq, then pop from pq
4 return size of pqdef minMeetingRooms(self, intervals: List[List[int]]) -> int:
min_conf=-sys.maxsize
intervals.sort(key=lambda i: i[0])pq=[] for ms, me in intervals: if pq and ms>=pq[0]: heapq.heappop(pq) heapq.heappush(pq, me) return len(pq)
T: O(nlogn)
S: O(n)
- Graph Valid Tree
Medium
You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.
Return true if the edges of the given graph make up a valid tree, and false otherwise.
Example 1:
Input: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
Output: true
- Undirected graph. Check if there are cycles in the loop.
- Also check if len(colors)==len(graph) - disconnected graph. Do DFS only from 0.
- Check if gray and nei!=parent: then return False. Else, gray is fine because this is an undirected graph
WHITE,GRAY,BLACK=0,1,2
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if not edges and n == 1:
return True
if not edges and n > 1:
return False
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
if len(graph) != n:
return False
colors = defaultdict(int)
if self.has_cycle(0, graph, colors, -1):
return False
if len(colors) != len(graph):
return False
return True
def has_cycle(self, node, graph, colors, parent):
colors[node] = GRAY
for nei in graph[node]:
if colors[nei] == GRAY and nei != parent:
return True
elif colors[nei] == WHITE:
if self.has_cycle(nei, graph, colors, node):
return True
colors[node] = BLACK
return False
T: O(V+E)
S: O(V+E)
