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 twoSumSorted(self, a, target):
l = 0, r = (int)len(a) - 1
while l < r:
long long sum = (long long)a[l] + a[r]
if (sum == target) return True
if (sum < target) l += 1 else r -= 1
return False
Three Sum / Four Sum
// 3Sum
def threeSum(self, nums):
nums.sort()
list[list[int>> result
n = len(nums)
for (i = 0 i < n - 2 i += 1) :
if (i > 0 and nums[i] == nums[i-1]) continue
left = i + 1, right = n - 1
while left < right:
sum = nums[i] + nums[left] + nums[right]
if sum == 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
else if (sum < 0) :
left += 1
else :
right -= 1
return result
Sliding Window
Fixed Size Window
# Maximum sum of subarray of size k
def maxSumSubarray(self, nums, k):
sum = 0
for (i = 0 i < k i += 1) :
sum += nums[i]
maxSum = sum
for (i = k i < len(nums) i += 1) :
sum = sum - nums[i-k] + nums[i]
maxSum = max(maxSum, sum)
return maxSum
Variable Size Window
# Longest subarray with sum <= k
def longestSubarray(self, nums, k):
left = 0, sum = 0, maxLen = 0
for (right = 0 right < len(nums) right += 1) :
sum += nums[right]
while sum > k:
sum -= nums[left += 1]
maxLen = max(maxLen, right - left + 1)
return maxLen
| 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 prefixSum(self, a):
list[int> ps(len(a)+1)
for (i = 0 i < (int)len(a) i += 1) :
ps[i+1] = ps[i] + a[i]
return ps
# Range sum query
def rangeSum(self, prefix, l, r):
return prefix[r+1] - prefix[l]
Difference Array
# Range addition
def getModifiedArray(self, length, updates):
list[int> diff(length + 1, 0)
for update in updates:
diff[update[0]] += update[2]
diff[update[1] + 1] -= update[2]
list[int> result(length)
result[0] = diff[0]
for (i = 1 i < length i += 1) :
result[i] = result[i-1] + diff[i]
return result
Binary Search
Search in Sorted Array
def binarySearch(self, nums, target):
left = 0, right = 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 searchRotated(self, nums, target):
left = 0, right = len(nums) - 1
while left <= right:
mid = left + (right - left) / 2
if (nums[mid] == target) return mid
if nums[left] <= nums[mid]:
# Left half is sorted
if nums[left] <= target and target < nums[mid]:
right = mid - 1
else :
left = mid + 1
else :
# Right half is sorted
if nums[mid] < target and 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(self, matrix):
n = len(matrix)
# Transpose
for (i = 0 i < n i += 1) :
for (j = i j < n j += 1) :
swap(matrix[i][j], matrix[j][i])
# Reverse each row
for (i = 0 i < n i += 1) :
reverse(matrix[i].begin(), matrix[i].end())
Spiral Matrix
def spiralOrder(self, matrix):
list[int> result
if (not matrix) return result
m = len(matrix), n = matrix[0].__len__()
top = 0, bottom = m - 1, left = 0, right = n - 1
while top <= bottom and left <= right:
# Right
for (j = left j <= right j += 1) :
result.append(matrix[top][j])
top += 1
# Down
for (i = top i <= bottom i += 1) :
result.append(matrix[i][right])
right -= 1
# Left
if top <= bottom:
for (j = right j >= left j -= 1) :
result.append(matrix[bottom][j])
bottom -= 1
# Up
if left <= right:
for (i = bottom i >= top i -= 1) :
result.append(matrix[i][left])
left += 1
return result
Array Manipulation
Merge Intervals
def merge(self, intervals):
intervals.sort()
list[list[int>> merged
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(self, nums):
n = len(nums)
jumps = 0, curEnd = 0, curFar = 0
for (i = 0 i < n - 1 i += 1) :
curFar = max(curFar, i + nums[i])
if i == curEnd:
jumps += 1
curEnd = curFar
return jumps
More templates