Meta Popular Questions Flashcards
(41 cards)
88 - Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n
Have 2 pointers at the end of arrays. Have 3rd pointer pointing at the writing position. break condition is the first part of the while loop
for write_index in range(n + m - 1, -1, -1):
if p2 < 0:
break
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write_index] = nums1[p1]
p1 -= 1
else:
nums1[write_index] = nums2[p2]
p2 -= 1
680 - Valid Palindrome 2
Given a string s, return true if the s can be palindrome after deleting at most one character from it.
Example 1:
Input: s = “aba”
Output: true
Example 2:
Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.
Example 3:
Have an inner function that checks if palindrome is valid for indexes, I and j. Then use that to check if we remove a char from the left pointer or the right pointer.
Be careful to decrement the j pointer. Beware of copy/paste errors.
class Solution:
def validPalindrome(self, s: str) -> bool:
def check_palindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
i = 0
j = len(s) - 1
while i < j:
# Found a mismatched pair - try both deletions
if s[i] != s[j]:
return check_palindrome(s, i, j - 1) or check_palindrome(s, i + 1, j)
i += 1
j -= 1
return True
125 - Valid Palindrome 1
Given a string s, return true if it is a palindrome, or false otherwise.
A palindrome is valid if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.
Remember to use isalnum( ) to check for alpha-numeric
~~~
class Solution:
def isPalindrome(self, s: str) -> bool:
i, j = 0, len(s) - 1
while i < j:
# ignore chars like #$%&@-=|
while i < j and not s[i].isalnum():
i += 1
# ignore chars like #$%&@-=|
while i < j and not s[j].isalnum():
j -= 1
# compare the lowercase values
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True
```
236 - Find Lowest Common Ancestor of 2 nodes in binary tree
See if 2 of 3 conditions are True
Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case we might be visiting all the nodes of the binary tree.
Space Complexity: O(N). This is because the maximum amount of space utilized by the recursion stack would be N since the height of a skewed binary tree could be N.
class Solution:
def \_\_init\_\_(self):
# Variable to store LCA node.
self.ans = None
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
def recurse_tree(current_node: TreeNode) -> bool:
# If reached the end of a branch, return False.
if not current_node:
return False
# Left Recursion
left = recurse_tree(current_node.left)
# Right Recursion
right = recurse_tree(current_node.right)
# If the current node is one of p or q
mid = (current_node == p or current_node == q)
# If any two of the three flags left, right or mid become True.
if mid + left + right >= 2:
self.ans = current_node
# Return True if either of the three bool values is True.
return mid or left or right
# Traverse the tree
recurse_tree(root)
return self.ans
1249 - Remove min parens to make balanced parens
Have a Set for closing paren without opening parent,
and Stack for opening parent without closing paren. iterate through each char in string. merge stack and set . enumerate through string again, check if in newset, build char array. using ““.join
class Solution:
def minRemoveToMakeValid(self, s: str) -> str:
indexes_to_remove = set()
stack = []
for i, c in enumerate(s):
# ignore non-paren characters
if c not in "()":
continue
# for open paren, add index to stack
if c == "(":
stack.append(i)
elif not stack:
# we saw closing paren without seeing open paren,
# so we know that we should remove this index
indexes_to_remove.add(i)
else:
# saw closing paren, pop the open paren index from stack
stack.pop()
# make a new set that is union of removal indexes and leftover open parens
indexes_to_remove = indexes_to_remove.union(set(stack))
# string_builder will hold the characters we want to keep
string_builder = []
for i, c in enumerate(s):
if i not in indexes_to_remove:
string_builder.append(c)
return "".join(string_builder)
TwoSum (not sorted)
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Assume that each input would have exactly one solution, and you may not use the same element twice.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Use a hash to remember the index
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
h = {}
for i, n in enumerate(nums):
delta = target - n
if delta in h:
return [i, h[delta]]
h[n] = i
return []
Return the Kth largest element of an array
Call heapify on the array. Then call heappop( )
Remember to multiply by -1 and return (res * -1)
from heapq import heapify, heappop
class Solution:
def findKthLargest(self, nums, k) -> int:
nums = [-n for n in nums]
heapify(nums)
res = 0
for _ in range(k):
res = heappop(nums)
return -res
Three Sum
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
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.
You should probably provide this solution first, since it builds on TwoSum
# Time Complexity: O(n^2). TwoSumII is O(n), and we call it n times.
# Sorting the array takes O(nlogn), so overall complexity is O(nlogn+n^2).
# This is asymptotically equivalent to O(n^2).
Space Complexity: from O(logn) to O(n),
# depending on the implementation of the sorting algorithm.
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort()
for i in range(len(nums)):
if nums[i] > 0:
break
if i == 0 or nums[i - 1] != nums[i]:
self.twoSumII(nums, i, res)
return res
def twoSumII(self, nums: List[int], i: int, res: List[List[int]]):
lo, hi = i + 1, len(nums) - 1
while lo < hi:
sum = nums[i] + nums[lo] + nums[hi]
if sum < 0:
lo += 1
elif sum > 0:
hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
ThreeSum without sorting
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res, dups = set(), set()
seen = {}
for i, val1 in enumerate(nums):
if val1 not in dups:
dups.add(val1)
for j, val2 in enumerate(nums[i + 1 :]):
complement = -val1 - val2
if complement in seen and seen[complement] == i:
res.add(tuple(sorted((val1, val2, complement))))
seen[val2] = i
return res
Time Complexity: O(n^2). We have outer and inner loops, each going through n elements.
While the asymptotic complexity is the same, this algorithm is noticeably slower than the previous approach. Lookups in a hashset, though requiring a constant time, are expensive compared to the direct memory access.
Space Complexity: O(n) for the hashset/hashmap.
200 - Num Islands
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
Time complexity : O(M×N) where M is the number of rows and
N is the number of columns.
Space complexity : worst case O(M×N) in case that the grid map
is filled with lands where DFS goes by M×N deep.
class Solution:
def numIslands_2024_08_02(self, grid) -> int:
def adjacents(grid, row, col):
adjacents = []
last_row = len(grid) - 1
last_col = len(grid[0]) -1
coords = [[0,1], [0,-1], [1,0], [-1,0]]
for coord in coords:
new_row = row + coord[0]
new_col = col + coord[1]
if new_row >= 0 and new_row <= last_row and new_col >= 0 and new_col <= last_col:
adjacents.append([new_row, new_col])
return adjacents
def explore(grid, row, col):
# mark as visited
grid[row][col] = '2'
for pair in adjacents(grid, row, col):
r = pair[0]
c = pair[1]
# check if visited or ocean
if grid[r][c] != '1':
continue
explore(grid, r, c)
num_islands = 0
num_rows = len(grid)
num_cols = len(grid[0])
for i in range(num_rows):
for j in range(num_cols):
if grid[i][j] == '1':
explore(grid, i, j)
num_islands += 1
return num_islands
408 - Valid Word Abbreviation
Input: word = “internationalization”, abbr = “i12iz4n”
Output: true
Input: word = “apple”, abbr = “a2e”
Output: false
Two pointers,
if p2 is digit do some atoi logic and move the p2 pointer. final check that the two pointers = len of original stuff
class Solution:
def validWordAbbreviation(self, word: str, abbr: str) -> bool:
p1 = p2 = 0
word_len = len(word)
abbr_len = len(abbr)
while p1 < word_len and p2 < abbr_len:
if abbr[p2].isdigit():
if abbr[p2] == '0': # leading zeros are invalid
return False
# atoi logic
shift = 0
while p2 < abbr_len and abbr[p2].isdigit():
shift = (shift*10)+int(abbr[p2])
p2 += 1
p1 += shift
else:
if word[p1] != abbr[p2]:
return False
p1 += 1
p2 += 1
return p1 == word_len and p2 == abbr_len
”””
525. Contiguous Array
Given a binary array nums, return the maximum length of a contiguous subarray
with an equal number of 0 and 1.
Example 1:
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
“””
make use of a HashMap map to store the entries in the form of (index,count).
We make an entry for a count in the map whenever the count is encountered first, and later on use the corresponding index to find the length of the largest subarray with equal no. of zeros and ones when the same count is encountered again.
# Runtime: O(N)
# Space: O(N)
class Solution:
def findMaxLength(self, nums):
count_map = {0: -1}
maxlen = 0
count = 0
for i, num in enumerate(nums):
count += 1 if num == 1 else -1
if count in count_map:
maxlen = max(maxlen, i - count_map[count])
else:
count_map[count] = i
return maxlen
”””
Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.
You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.
We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.
“””
class Solution:
def treeToDoublyList(self, root: ‘Node’) -> ‘Node’:
def helper(node):
“””
Performs standard inorder traversal:
left -> node -> right
and links all nodes into DLL
“””
nonlocal last, first
if node:
# left
helper(node.left)
# node
if last:
# link the previous node (last)
# with the current one (node)
last.right = node
node.left = last
else:
# keep the smallest node
# to close DLL later on
first = node
last = node
# right
helper(node.right)
if not root:
return None
# the smallest (first) and the largest (last) nodes
first, last = None, None
helper(root)
# close DLL
last.right = first
first.left = last
return first
”””
71 - 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.
Example 1:
Input: path = “/home/”
Output: “/home”
Explanation:
The trailing slash should be removed.
Example 2:
Input: path = “/home//foo/”
Output: “/home/foo”
Explanation:
Multiple consecutive slashes are replaced by a single one.
Use a Stack. pop if see “..”, otherwise add to stack
class Solution:
def simplifyPath(self, path: str) -> str:
# Initialize a stack
stack = []
# Split the input string on "/" as the delimiter
# and process each portion one by one
for portion in path.split("/"):
# If the current component is a "..", then
# we pop an entry from the stack if it's non-empty
if portion == "..":
if stack:
stack.pop()
elif portion == "." or not portion:
# A no-op for a "." or an empty string
continue
else:
# Finally, a legitimate directory name, so we add it
# to our stack
stack.append(portion)
# Stich together all the directory names together
final_str = "/" + "/".join(stack)
return final_str
”””
76. Minimum Window Substring
Given two strings s and t of lengths m and n respectively,
return the minimum window substring of s such that
every character in t (including duplicates) is included in the window.
If there is no such substring, return the empty string “”.
The testcases will be generated such that the answer is unique.
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.
“””
Initialize a character array map of size 128 to store the frequency of characters in string t.
Initialize variables count, start, end, minLen, and startIndex.
Iterate through each character in string t and update the character frequency in the map.
Use two pointers (start and end) to slide the window and find the minimum window that contains all characters from string t.
Increment end and decrease the frequency in map for each character encountered until all characters from t are present in the window.
When all characters from t are present, update minLen and startIndex based on the current window size and starting index.
Increment start and increase the frequency in map until the window no longer contains all characters from t.
After the iteration, the minimum window is found, and the result is a substring of s starting from startIndex with length minLen.
Time complexity: O(n), where n is the length of string s.
# Space complexity: O(1), as the map array has a constant size (128).
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t or len(s) < len(t):
return “”
map = [0] * 128
count = len(t)
start = 0
end = 0
min_len = float('inf')
start_index = 0
# UPVOTE !
for char in t:
map[ord(char)] += 1
while end < len(s):
if map[ord(s[end])] > 0:
count -= 1
map[ord(s[end])] -= 1
end += 1
while count == 0:
if end - start < min_len:
start_index = start
min_len = end - start
if map[ord(s[start])] == 0:
count += 1
map[ord(s[start])] += 1
start += 1
return "" if min_len == float('inf') else s[start_index:start_index + min_len]
146 - LRU Cache
get( ) and put( ) functions both running in O(1) time.
”””
Get the current node at the end of the linked list. This is the “real” tail: tail.prev. Let’s call it previousEnd.
node is being inserted after previousEnd. Therefore, set previousEnd.next = node.
Now, we set the pointers of node. First, node.prev = previousEnd.
Next, because the “real” tail is before tail, we set node.next = tail.
Finally, we update tail.prev = node.
“””
class ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dic = {}
# Two sentinel values
self.head = ListNode(-1, -1)
self.tail = ListNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.dic:
return -1
node = self.dic[key]
# move the end of the list
self.remove(node)
self.add(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.dic:
old_node = self.dic[key]
self.remove(old_node)
node = ListNode(key, value)
self.dic[key] = node
self.add(node)
if len(self.dic) > self.capacity:
node_to_delete = self.head.next
self.remove(node_to_delete)
del self.dic[node_to_delete.key]
def add(self, node):
previous_end = self.tail.prev
previous_end.next = node
node.prev = previous_end
node.next = self.tail
self.tail.prev = node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
314 - Binary Tree Vertical Order Traversal
Given the root of a binary tree, return the vertical order traversal of its nodes’ values. (i.e., from top to bottom, column by column).
If two nodes are in the same row and column, the order should be from left to right.
Output:
[[9],[3,15],[20],[7]]
BFS, save vertical level as state,
keep a hash table of the vertical levels. keep inserting
maintain the min and max level amounts.
finally iterate from min to max vertical level and access the hash
class Solution:
def verticalOrder(self, root):
if not root:
return []
vertTable = defaultdict(list)
queue = deque()
min_column = 0
max_column = 0
queue.append([root, 0])
while queue:
node, column = queue.popleft()
vertTable[column].append(node.val)
min_column = min(column, min_column)
max_column = max(column, max_column)
if node.left:
queue.append([node.left, column - 1])
if node.right:
queue.append([node.right, column + 1])
res = []
for i in range(min_column, max_column + 1):
res.append(vertTable[i])
return res
523 Continuous Subarray Sum
Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.
A good subarray is a subarray where:
its length is at least two, and
the sum of the elements of the subarray is a multiple of k.
Note that:
A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
Initialize an integer prefixMod = 0 and a hashmap modSeen. Initialize modSeen[0] with -1 to account for the initial value of prefixMod.
Iterate over all the elements of nums:
Compute the prefixMod as prefixMod = (prefixMod + nums[i]) % k.
If prefixMod exists in the hashmap:
If the size of the longest subarray with modulo k is at least 2.
Return true.
If prefixMod doesn’t exist in the hashmap:
Set modSeen[prefixMod] = i.
Return false.
Time complexity: O(n)
We iterate through the array exactly once.
Space complexity: O(n)
class Solution:
def checkSubarraySum(self, nums, k):
prefix_mod = 0
mod_seen = {0: -1}
for i in range(len(nums)):
prefix_mod = (prefix_mod + nums[i]) % k
if prefix_mod in mod_seen:
# ensures that the size of subarray is at least 2
if i - mod_seen[prefix_mod] > 1:
return True
else:
# mark the value of prefix_mod with the current index.
mod_seen[prefix_mod] = i
return False
- Palindromic Substrings
Given a string s, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
We choose all possible centers for potential palindromes:
Every single character in the string is a center for possible odd-length palindromes
Every pair of consecutive characters in the string is a center for possible
even-length palindromes.
For every center, we can expand around it as long as we get palindromes
(i.e. the first and last characters should match).
class Solution:
def countSubstrings(self, s: str) -> int:
ans = 0
for i in range(len(s)):
# odd-length palindromes, single character center
ans += self.countPalindromesAroundCenter(s, i, i)
# even-length palindromes, consecutive characters center
ans += self.countPalindromesAroundCenter(s, i, i + 1)
return ans
def countPalindromesAroundCenter(self, ss: str, lo: int, hi: int) -> int:
ans = 0
while lo >= 0 and hi < len(ss):
if ss[lo] != ss[hi]:
break # the first and last characters don't match!
# expand around the center
lo -= 1
hi += 1
ans += 1
return ans
- Letter Combinations of a Phone Number
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.
Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
Use the “backtrack” template
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# handle empty case first
if not digits:
return []
phone_map = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
def backtrack(prefix, next_digits):
if len(next_digits) == 0:
output.append(prefix)
else:
for letter in phone_map[next_digits[0]]:
backtrack(prefix + letter, next_digits[1:])
output = []
backtrack("", digits)
return output
- Merge k Sorted Lists
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
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
Pair up k lists and merge each pair.
After the first pairing, k lists are merged into k/2 lists with average 2N/k length, then k/4, k/8 and so on.
Repeat this procedure until we get the final sorted linked list.
Thus, we’ll traverse almost N nodes per pairing and merging, and repeat this procedure about log
2
k times.
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]:
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else None
def merge2Lists(self, l1, l2):
head = point = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l1
l1 = point.next.next
point = point.next
if not l1:
point.next = l2
else:
point.next = l1
return head.next
- Search in Rotated Sorted Array
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
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
33 - Normal binary search, but need to handle the 3 cases
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
left, right = 0, n - 1
while left <= right:
mid = left + (right - left) // 2
# Case 1: find target
if nums[mid] == target:
return mid
# Case 2: subarray on mid's left is sorted
elif nums[mid] >= nums[left]:
if target >= nums[left] and target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Case 3: subarray on mid's right is sorted.
else:
if target <= nums[right] and target > nums[mid]:
left = mid + 1
else:
right = mid - 1
return -1
28 - StrStr - find a substring within a string
Runtime: O(N x M)
Space: O(1)
Chris Solution
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
hlen = len(haystack)
nlen = len(needle)
nlast = nlen - 1
if nlen == 0:
return 0
for i in range(hlen - nlen + 1):
for j in range(nlen):
if haystack[i + j] != needle[j]:
break
if j == nlast:
return i
return -1
38 - Count and Say
RLE = Run Length Encoding
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”
class Solution:
def countAndSay(self, n: int) -> str:
current_string = “1”
for _ in range(n - 1):
next_string = “”
j = 0
k = 0
while j < len(current_string):
while (
k < len(current_string)
and current_string[k] == current_string[j]
):
k += 1
next_string += str(k - j) + current_string[j]
j = k
current_string = next_string
return current_string
