Minimal, copy-paste Java 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
static boolean twoSumSorted(int[] a, int target){
int l = 0, r = (int)a.size() - 1;
while (l < r){
long sum = (long)a[l] + a[r];
if (sum == target) return true;
if (sum < target) ++l; else --r;
}
return false;
}
Three Sum / Four Sum
// import java.util.Arrays;
// import java.util.Collections;
// 3Sum
int[][] threeSum(int[] nums) {
Arrays.sort(nums);
int[][] result;
int n = nums.length;
for (int i = 0; i < n - 2; ++i) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Sliding Window
Fixed Size Window
// Maximum sum of subarray of size k
static int maxSumSubarray(int[] nums, int k) {
int sum = 0;
for (int i = 0; i < k; ++i) {
sum += nums[i];
}
int maxSum = sum;
for (int i = k; i < nums.length; ++i) {
sum = sum - nums[i-k] + nums[i];
maxSum = Math.max(maxSum, sum);
}
return maxSum;
}
Variable Size Window
// Longest subarray with sum <= k
static int longestSubarray(int[] nums, int k) {
int left = 0, sum = 0, maxLen = 0;
for (int right = 0; right < nums.length; ++right) {
sum += nums[right];
while (sum > k) {
sum -= nums[left++];
}
maxLen = Math.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
int[]prefixSum(int[] a){
int[]ps(a.size()+1);
for (int i = 0; i < (int)a.size(); ++i) {
ps[i+1] = ps[i] + a[i];
}
return ps;
}
// Range sum query
static int rangeSum(int[] prefix, int l, int r) {
return prefix[r+1] - prefix[l];
}
Difference Array
// Range addition
int[]getModifiedArray(int length, int[][]& updates) {
int[] diff = new int[length + 1];
for (auto update : updates) {
diff[update[0]] += update[2];
diff[update[1] + 1] -= update[2];
}
int[]result(length);
result[0] = diff[0];
for (int i = 1; i < length; ++i) {
result[i] = result[i-1] + diff[i];
}
return result;
}
Binary Search
Search in Sorted Array
static int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int 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
static int searchRotated(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) {
// Left half is sorted
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// Right half is sorted
if (nums[mid] < target && 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
static void rotate(int[][]& matrix) {
int n = matrix.size();
// Transpose
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
swap(matrix[i][j], matrix[j][i]);
}
}
// Reverse each row
for (int i = 0; i < n; ++i) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
Spiral Matrix
int[]spiralOrder(int[][]& matrix) {
int[]result;
if (matrix.length == 0) return result;
int m = matrix.size(), n = matrix[0].length;
int top = 0, bottom = m - 1, left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// Right
for (int j = left; j <= right; ++j) {
result.add(matrix[top][j]);
}
top++;
// Down
for (int i = top; i <= bottom; ++i) {
result.add(matrix[i][right]);
}
right--;
// Left
if (top <= bottom) {
for (int j = right; j >= left; --j) {
result.add(matrix[bottom][j]);
}
bottom--;
}
// Up
if (left <= right) {
for (int i = bottom; i >= top; --i) {
result.add(matrix[i][left]);
}
left++;
}
}
return result;
}
Array Manipulation
Merge Intervals
// import java.util.Arrays;
// import java.util.Collections;
int[][] merge(int[][]& intervals) {
Arrays.sort(intervals);
int[][] merged;
for (auto interval : intervals) {
if (merged.length == 0 || merged.getLast()[1] < interval[0]) {
merged.add(interval);
} else {
merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
}
}
return merged;
}
Jump Game
// Jump Game II - Minimum jumps
static int jump(int[] nums) {
int n = nums.length;
int jumps = 0, curEnd = 0, curFar = 0;
for (int i = 0; i < n - 1; ++i) {
curFar = Math.max(curFar, i + nums[i]);
if (i == curEnd) {
jumps++;
curEnd = curFar;
}
}
return jumps;
}
More templates