Here are the solutions for the remaining problems on the list:
Approach: Iteratively reverse the pointers of the linked list nodes.
Code in Python:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head):
prev = None
current = head
while current:
next_node = current.next
current.next = prev
prev = current
current = next_node
return prevApproach: Use the Boyer-Moore Voting Algorithm to find the majority element in linear time.
Code in Python:
def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidateApproach: Use the mathematical formula for the sum of the first n natural numbers and subtract the sum of the array elements.
Code in Python:
def missingNumber(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sumApproach: Use two pointers to swap characters from the start and end until they meet in the middle.
Code in Python:
def reverseString(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1Approach: Use depth-first search (DFS) to compute the longest path between any two nodes in the tree.
Code in Python:
def diameterOfBinaryTree(root):
diameter = 0
def longest_path(node):
nonlocal diameter
if not node:
return 0
left_path = longest_path(node.left)
right_path = longest_path(node.right)
diameter = max(diameter, left_path + right_path)
return max(left_path, right_path) + 1
longest_path(root)
return diameterApproach: Use two pointers (slow and fast) to find the middle node in one pass.
Code in Python:
def middleNode(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowApproach: Use a recursive approach to construct a balanced BST from the sorted array.
Code in Python:
def sortedArrayToBST(nums):
if not nums:
return None
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = sortedArrayToBST(nums[:mid])
root.right = sortedArrayToBST(nums[mid+1:])
return rootApproach: Use dynamic programming to find the number of ways to reach the top of the stairs.
Code in Python:
def climbStairs(n):
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0], dp[1] = 1, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]Approach: Use recursion to check if the left and right subtrees are mirrors of each other.
Code in Python:
def isSymmetric(root):
def is_mirror(t1, t2):
if not t1 and not t2:
return True
if not t1 or not t2:
return False
return (t1.val == t2.val) and is_mirror(t1.right, t2.left) and is_mirror(t1.left, t2.right)
return is_mirror(root, root)Approach: Use a queue to perform a breadth-first search and collect nodes level by level.
Code in Python:
from collections import deque
def levelOrder(root):
levels = []
if not root:
return levels
queue = deque([root])
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)
levels.append(level)
return levelsApproach: Use a greedy algorithm to accumulate profits from every local increase in price.
Code in Python:
def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitApproach: Use bit manipulation to count the number of 1s in the binary representation of a number.
Code in Python:
def hammingWeight(n):
count = 0
while n:
count += n & 1
n >>= 1
return countApproach: Use recursion to ensure that each node satisfies the BST properties with respect to its value range.
Code in Python:
def isValidBST(root):
def validate(node, low=-float('inf'), high=float('inf')):
if not node:
return True
if node.val <= low or node.val >= high:
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root)Approach: Use two stacks, one for the stack values and another to track the minimum value at each level.
Code in Python:
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]Approach: Perform an in-order traversal to retrieve elements in sorted order and find the kth smallest element.
Code in Python:
def kthSmallest(root, k):
def inorder(node):
return inorder(node.left) + [node.val] + inorder(node.right) if node else []
return inorder(root)[k - 1]Approach: Use a marker for each row and column to track which should be zeroed, then update the matrix accordingly.
Code in Python:
def setZeroes(matrix):
is_col = False
R, C = len(matrix), len(matrix[0])
for i in range(R):
if matrix[i][0] == 0:
is_col = True
for j in range(1, C):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, R):
for j in range(1, C):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if matrix[0][0] == 0:
for j in range(C):
matrix[0][j] = 0
if is_col:
for i in range(R):
matrix[i][0] = 0Approach: Use a queue to perform level-order traversal and reverse the order of nodes at each alternate level.
Code in Python:
def zigzagLevelOrder(root):
if not root:
return []
results = []
queue = deque([root])
left_to_right = True
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)
results.append(list(level))
left_to_right = not left_to_right
return resultsApproach: Use recursion and hash maps to efficiently construct the binary tree using the given order lists.
**
Code in Python:**
def buildTree(preorder, inorder):
if not preorder or not inorder:
return None
root_val = preorder.pop(0)
root = TreeNode(root_val)
inorder_index = inorder.index(root_val)
root.left = buildTree(preorder, inorder[:inorder_index])
root.right = buildTree(preorder, inorder[inorder_index + 1:])
return rootApproach: Use topological sort to determine if the courses can be finished, checking for cycles.
Code in Python:
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
adj_list = defaultdict(list)
indegree = [0] * numCourses
for dest, src in prerequisites:
adj_list[src].append(dest)
indegree[dest] += 1
queue = deque([i for i in range(numCourses) if indegree[i] == 0])
visited = 0
while queue:
node = queue.popleft()
visited += 1
for neighbor in adj_list[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return visited == numCoursesApproach: Implement a Trie using a nested dictionary to support insert, search, and startsWith operations.
Code in Python:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return TrueApproach:
Extend the Trie data structure to support the . character, which can match any letter.
Code in Python:
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
def search_in_node(word, node):
for i, char in enumerate(word):
if char == '.':
for child in node.children.values():
if search_in_node(word[i+1:], child):
return True
return False
else:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
return search_in_node(word, self.root)Here are the solutions for the remaining problems from the provided list that have not already been covered:
Approach: Use a stack to keep track of opening brackets. For each closing bracket, check if it matches the top of the stack.
Code in Python:
def isValid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stackApproach: Use two pointers to merge the two sorted linked lists into one sorted list.
Code in Python:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode()
current = dummy
while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
current.next = l1 or l2
return dummy.nextApproach: Use two pointers to check if a string is a palindrome, ignoring non-alphanumeric characters and case.
Code in Python:
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left, right = left + 1, right - 1
return TrueApproach: Recursively swap the left and right children of each node.
Code in Python:
def invertTree(root):
if root:
root.left, root.right = invertTree(root.right), invertTree(root.left)
return rootApproach: Sort both strings and compare if they are identical.
Code in Python:
def isAnagram(s, t):
return sorted(s) == sorted(t)Approach: Use the binary search algorithm to find a target element in a sorted array.
Code in Python:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Approach: Use two pointers (slow and fast) to detect if there is a cycle in the linked list.
Code in Python:
def hasCycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseApproach: Use recursion to find the maximum depth of the binary tree.
Code in Python:
def maxDepth(root):
if not root:
return 0
return 1 + max(maxDepth(root.left), maxDepth(root.right))Approach: Use the XOR operation to find the single number in a list where every other number appears twice.
Code in Python:
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return resultApproach: Use a hash map to group words that are anagrams of each other.
Code in Python:
from collections import defaultdict
def groupAnagrams(strs):
anagrams = defaultdict(list)
for s in strs:
sorted_str = ''.join(sorted(s))
anagrams[sorted_str].append(s)
return list(anagrams.values())Approach: Use a min-heap to keep track of the k largest elements.
Code in Python:
import heapq
def findKthLargest(nums, k):
return heapq.nlargest(k, nums)[-1]Approach: Use dynamic programming to find the longest palindromic substring.
Code in Python:
def longestPalindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_length = 0, 1
for i in range(n):
dp[i][i] = True
for start_idx in range(n-1, -1, -1):
for end_idx in range(start_idx + 1, n):
if s[start_idx] == s[end_idx]:
if end_idx - start_idx == 1 or dp[start_idx + 1][end_idx - 1]:
dp[start_idx][end_idx] = True
if max_length < end_idx - start_idx + 1:
start = start_idx
max_length = end_idx - start_idx + 1
return s[start:start + max_length]Approach: Use a sliding window approach to find the longest substring without repeating characters.
Code in Python:
def lengthOfLongestSubstring(s):
char_index = {}
left = max_length = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_length = max(max_length, right - left + 1)
return max_lengthApproach: Use dynamic programming to find the largest square of 1s in a binary matrix.
Code in Python:
def maximalSquare(matrix):
if not matrix:
return 0
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * (cols + 1) for _ in range(rows + 1)]
max_side = 0
for i in range(1, rows + 1):
for j in range(1, cols + 1):
if matrix[i-1][j-1] == '1':
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_side = max(max_side, dp[i][j])
return max_side * max_sideApproach: Use dynamic programming to keep track of the maximum and minimum products at each position.
Code in Python:
def maxProduct(nums):
if not nums:
return 0
max_so_far = min_so_far = result = nums[0]
for num in nums[1:]:
candidates = (num, max_so_far * num, min_so_far * num)
max_so_far = max(candidates)
min_so_far = min(candidates)
result = max(result, max_so_far)
return resultApproach: Use a sliding window approach to find the smallest window containing all characters of another string.
Code in Python:
from collections import Counter
def minWindow(s, t):
if not t or not s:
return ""
dict_t = Counter(t)
required = len(dict_t)
l, r = 0, 0
formed = 0
window_counts = {}
ans = float("inf"), None, None
while r < len(s):
character = s[r]
window_counts[character] = window_counts.get(character, 0) + 1
if character in dict_t and window_counts[character] == dict_t[character]:
formed += 1
while l <= r and formed == required:
character = s[l]
if r - l + 1 < ans[0]:
ans = (r - l + 1, l, r)
window_counts[character] -= 1
if character in dict_t and window_counts[character] < dict_t[character]:
formed -= 1
l += 1
r += 1
return "" if ans[0] == float("inf") else s[ans[1]: ans[2] + 1]Approach: Use backtracking to generate all permutations of a list of numbers.
Code in Python:
def permute(nums):
def backtrack(start=0):
if
start == len(nums):
result.append(nums[:])
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack()
return resultApproach: Use two pointers to find and remove the nth node from the end of the list.
Code in Python:
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n + 1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.nextApproach: Use binary search to find a target value in a sorted 2D matrix.
Code in Python:
def searchMatrix(matrix, target):
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
mid_value = matrix[mid // cols][mid % cols]
if mid_value == target:
return True
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return FalseApproach: Use binary search to find a target in a rotated sorted array.
Code in Python:
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1Approach: Use backtracking to generate all subsets of a list of numbers.
Code in Python:
def subsets(nums):
def backtrack(start=0, path=[]):
result.append(path)
for i in range(start, len(nums)):
backtrack(i + 1, path + [nums[i]])
result = []
backtrack()
return resultApproach: Use a hash map and a heap to find the k most frequent elements in a list.
Code in Python:
from collections import Counter
import heapq
def topKFrequent(nums, k):
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)Approach: Use two pointers to calculate the water trapped between the heights of bars.
Code in Python:
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return waterApproach: Use two pointers to find two numbers that add up to a target sum in a sorted array.
Code in Python:
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1]
elif current_sum < target:
left += 1
else:
right -= 1
return []Approach: Use dynamic programming to find the number of unique paths in a grid.
Code in Python:
def uniquePaths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[-1][-1]Approach: Check each row, column, and 3x3 box to see if it contains unique digits.
Code in Python:
def isValidSudoku(board):
rows = [set() for _ in range(9)]
columns = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for i in range(9):
for j in range(9):
num = board[i][j]
if num == '.':
continue
box_index = (i // 3) * 3 + j // 3
if num in rows[i] or num in columns[j] or num in boxes[box_index]:
return False
rows[i].add(num)
columns[j].add(num)
boxes[box_index].add(num)
return TrueApproach: Use dynamic programming to check if a string can be segmented into a space-separated sequence of words.
Code in Python:
def wordBreak(s, wordDict):
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[-1]Approach: Use depth-first search (DFS) to find a word in a grid of letters.
Code in Python:
def exist(board, word):
def dfs(x, y, index):
if index == len(word):
return True
if x < 0 or y < 0 or x >= len(board) or y >= len(board[0]) or board[x][y] != word[index]:
return False
temp = board[x][y]
board[x][y] = '#'
found = (dfs(x + 1, y, index + 1) or dfs(x - 1, y, index + 1) or
dfs(x, y + 1, index + 1) or dfs(x, y - 1, index + 1))
board[x][y] = temp
return found
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0] and dfs(i, j, 0):
return True
return FalseApproach: Use a stack to evaluate arithmetic expressions with parentheses.
Code in Python:
def calculate(s):
stack, num, sign = [], 0, 1
result = 0
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char in ['-', '+']:
result += sign * num
num = 0
sign = 1 if char == '+' else -1
elif char == '(':
stack.append(result)
stack.append(sign)
sign, result = 1, 0
elif char == ')':
result += sign * num
num = 0
result *= stack.pop()
result += stack.pop()
return result + sign * numApproach: Use dynamic programming to find the minimum number of coins needed to make up a given amount.
Code in Python:
def coinChange(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Approach: Use backtracking to find all unique combinations of numbers that sum up to a target.
Code in Python:
def combinationSum(candidates, target):
def backtrack(remain, comb, start):
if remain == 0:
result.append(list(comb))
return
elif remain < 0:
return
for i in range(start, len(candidates)):
comb
.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
result = []
backtrack(target, [], 0)
return resultApproach: Use a hash map to copy a linked list with random pointers.
Code in Python:
def copyRandomList(head):
if not head:
return None
old_to_new = {None: None}
current = head
while current:
copy = Node(current.val)
old_to_new[current] = copy
current = current.next
current = head
while current:
copy = old_to_new[current]
copy.next = old_to_new[current.next]
copy.random = old_to_new[current.random]
current = current.next
return old_to_new[head]Approach: Use topological sorting to determine if a course schedule is possible.
Code in Python:
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for dest, src in prerequisites:
graph[src].append(dest)
in_degree[dest] += 1
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
while queue:
course = queue.popleft()
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return sum(in_degree) == 0Approach: Use a trie to implement add and search functionalities for a word dictionary.
Code in Python:
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(self, word):
current = self.root
for char in word:
if char not in current.children:
current.children[char] = TrieNode()
current = current.children[char]
current.is_end_of_word = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return node.is_end_of_word
if word[i] == '.':
for child in node.children.values():
if dfs(child, i + 1):
return True
return False
else:
if word[i] in node.children:
return dfs(node.children[word[i]], i + 1)
return False
return dfs(self.root, 0)Approach: Merge two sorted arrays into one sorted array.
Code in Python:
def merge(nums1, m, nums2, n):
while m > 0 and n > 0:
if nums1[m - 1] > nums2[n - 1]:
nums1[m + n - 1] = nums1[m - 1]
m -= 1
else:
nums1[m + n - 1] = nums2[n - 1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]Approach: Use two heaps to efficiently find the median of a data stream.
Code in Python:
import heapq
class MedianFinder:
def __init__(self):
self.small = []
self.large = []
def addNum(self, num):
heapq.heappush(self.small, -num)
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
elif len(self.large) > len(self.small):
return self.large[0]
return (-self.small[0] + self.large[0]) / 2Approach: Use an in-place algorithm to simulate the Game of Life.
Code in Python:
def gameOfLife(board):
rows, cols = len(board), len(board[0])
def count_live_neighbors(r, c):
live_neighbors = 0
for i in range(r - 1, r + 2):
for j in range(c - 1, c + 2):
if (i == r and j == c) or i < 0 or j < 0 or i >= rows or j >= cols:
continue
if board[i][j] in [1, -1]:
live_neighbors += 1
return live_neighbors
for r in range(rows):
for c in range(cols):
live_neighbors = count_live_neighbors(r, c)
if board[r][c] == 1 and (live_neighbors < 2 or live_neighbors > 3):
board[r][c] = -1
elif board[r][c] == 0 and live_neighbors == 3:
board[r][c] = 2
for r in range(rows):
for c in range(cols):
if board[r][c] == 2:
board[r][c] = 1
elif board[r][c] == -1:
board[r][c] = 0Approach: Use a greedy algorithm to determine if it's possible to jump to the last index.
Code in Python:
def canJump(nums):
max_reachable = 0
for i, num in enumerate(nums):
if i > max_reachable:
return False
max_reachable = max(max_reachable, i + num)
return TrueApproach: Use backtracking to generate all possible letter combinations for a given phone number.
Code in Python:
def letterCombinations(digits):
if not digits:
return []
phone_map = {
"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
}
def backtrack(index, path):
if index == len(digits):
combinations.append("".join(path))
return
possible_letters = phone_map[digits[index]]
for letter in possible_letters:
path.append(letter)
backtrack(index + 1, path)
path.pop()
combinations = []
backtrack(0, [])
return combinationsApproach: Use dynamic programming to find the longest increasing subsequence in a list of numbers.
Code in Python:
def lengthOfLIS(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)Approach: Use a binary search algorithm to find the median of two sorted arrays.
Code in Python:
def findMedianSortedArrays(nums1, nums2):
A, B = nums1, nums2
if len(A) > len(B):
A, B = B, A
total = len(A) + len(B)
half = total // 2
l, r = 0, len(A) - 1
while True:
i = (l + r) // 2
j = half - i - 2
Aleft = A[i] if i >= 0 else float("-inf")
Aright = A[i + 1] if (i + 1) < len(A) else float("inf")
Bleft = B[j] if j >= 0 else float("-inf")
Bright = B[j + 1] if (j + 1) < len(B) else float("inf")
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1Approach: Use dynamic programming to find the minimum path sum in a grid.
Code in Python:
def minPathSum(grid):
rows, cols = len(grid), len(grid[0
])
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue
elif r == 0:
grid[r][c] += grid[r][c - 1]
elif c == 0:
grid[r][c] += grid[r - 1][c]
else:
grid[r][c] += min(grid[r - 1][c], grid[r][c - 1])
return grid[rows - 1][cols - 1]Approach: Use matrix manipulation to rotate an image (matrix) by 90 degrees.
Code in Python:
def rotate(matrix):
n = len(matrix)
for i in range(n // 2):
for j in range(i, n - i - 1):
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = tempThese solutions cover a variety of algorithmic techniques and are designed to help you understand different approaches to problem-solving in coding interviews. If you have any specific questions about any of these problems or need further clarification, feel free to ask!