Python Problem-Solving Patterns
Two Pointers
Description: Use two pointers to traverse the data structure in different directions.
Example:
# Example: Check if a list has a pair with a given sum
def has_pair_with_sum(nums, target):
[Link]()
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return True
elif current_sum < target:
left += 1
else:
right -= 1
return False
print(has_pair_with_sum([10, 15, 3, 7], 17))
Sliding Window
Description: A dynamic window to optimize for problems involving contiguous subarrays.
Example:
# Example: Maximum sum of a subarray of size k
def max_sum_subarray(nums, k):
max_sum, window_sum = 0, 0
for i in range(len(nums)):
window_sum += nums[i]
if i >= k - 1:
max_sum = max(max_sum, window_sum)
window_sum -= nums[i - (k - 1)]
return max_sum
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))
Divide and Conquer
Description: Divide the problem into subproblems and solve recursively.
Example:
# Example: Merge Sort
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
sorted_list = []
while left and right:
if left[0] < right[0]:
sorted_list.append([Link](0))
else:
sorted_list.append([Link](0))
return sorted_list + left + right
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Dynamic Programming
Description: Optimize recursive solutions by storing subproblem results.
Example:
# Example: Fibonacci sequence using DP
def fibonacci(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fibonacci(10))
Backtracking
Description: Explore all solutions and backtrack when constraints are violated.
Example:
# Example: N-Queens problem
def solve_n_queens(n):
def is_safe(board, row, col):
for i in range(row):
if board[i] == col or abs(board[i] - col) == row - i:
return False
return True
def solve(board, row):
if row == n:
[Link](board[:])
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
solve(board, row + 1)
board[row] = -1
solutions = []
solve([-1] * n, 0)
return solutions
print(solve_n_queens(4))
