Minimal, copy-paste C++ for two pointers, sliding window, prefix sum, binary search, and matrix operations. See also Arrays & Strings and Search.
Contents
Two Pointers
Two Sum on Sorted Array
def two_sum_sorted(a: list[int], target: int) -> bool:
l, r = 0, len(a) - 1
while l < r:
s = a[l] + a[r]
if s == target:
return True
if s < target:
l += 1
else:
r -= 1
return False
Three Sum / Four Sum
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
result: list[list[int]] = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return result
Sliding Window
Fixed Size Window
# Maximum sum of subarray of size k
def max_sum_subarray(nums: list[int], k: int) -> int:
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k]
best = max(best, window)
return best
Variable Size Window
# Longest subarray with sum <= k
def longest_subarray(nums: list[int], k: int) -> int:
left = 0
total = 0
max_len = 0
for right in range(len(nums)):
total += nums[right]
while total > k:
total -= nums[left]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
| ID |
Title |
Link |
Solution |
| 3 |
Longest Substring Without Repeating Characters |
Link |
Solution |
| 209 |
Minimum Size Subarray Sum |
Link |
- |
| 239 |
Sliding Window Maximum |
Link |
Solution |
| 480 |
Sliding Window Median |
Link |
Solution |
| 2799 |
Count Complete Subarrays in an Array |
Link |
Solution |
| 346 |
Moving Average from Data Stream |
Link |
Solution |
| 713 |
Subarray Product Less Than K |
Link |
- |
Prefix Sum
Basic Prefix Sum
def prefix_sum(a: list[int]) -> list[int]:
ps = [0] * (len(a) + 1)
for i in range(len(a)):
ps[i + 1] = ps[i] + a[i]
return ps
def range_sum(prefix: list[int], l: int, r: int) -> int:
return prefix[r + 1] - prefix[l]
Difference Array
# Range addition
def get_modified_array(length: int, updates: list[list[int]]) -> list[int]:
diff = [0] * (length + 1)
for start, end, inc in updates:
diff[start] += inc
diff[end + 1] -= inc
result = [0] * length
cur = 0
for i in range(length):
cur += diff[i]
result[i] = cur
return result
Binary Search
Search in Sorted Array
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Search in Rotated Sorted Array
def search_rotated(nums: list[int], target: int) -> int:
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 -1
| ID |
Title |
Link |
Solution |
| 33 |
Search in Rotated Sorted Array |
Link |
Solution |
| 34 |
Find First and Last Position |
Link |
- |
| 240 |
Search a 2D Matrix II |
Link |
Solution |
Matrix Operations
Rotate Matrix
# Rotate 90 degrees clockwise
def rotate_matrix(matrix: list[list[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix:
row.reverse()
Spiral Matrix
def spiral_order(matrix: list[list[int]]) -> list[int]:
if not matrix:
return []
m, n = len(matrix), len(matrix[0])
top, bottom, left, right = 0, m - 1, 0, n - 1
result: list[int] = []
while top <= bottom and left <= right:
for j in range(left, right + 1):
result.append(matrix[top][j])
top += 1
for i in range(top, bottom + 1):
result.append(matrix[i][right])
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1):
result.append(matrix[bottom][j])
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
result.append(matrix[i][left])
left += 1
return result
Array Manipulation
Merge Intervals
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
merged: list[list[int]] = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])
return merged
Jump Game
# Jump Game II - Minimum jumps
def jump_game_ii(nums: list[int]) -> int:
n = len(nums)
jumps = cur_end = cur_far = 0
for i in range(n - 1):
cur_far = max(cur_far, i + nums[i])
if i == cur_end:
jumps += 1
cur_end = cur_far
return jumps
More templates