Complete DSA Pattern Templates (with Explanations)
1. Sliding Window Pattern
Use When:
You need to process a contiguous subarray or substring efficiently.
Common Problems:
- Maximum sum subarray of size k
- Longest substring with k distinct characters
Template (Fixed-size window):
int maxSumSubarray(vector<int>& nums, int k) {
int maxSum = 0, windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
maxSum = windowSum;
for (int i = k; i < nums.size(); i++) {
windowSum += nums[i] - nums[i - k];
maxSum = max(maxSum, windowSum);
}
return maxSum;
}
2. Two Pointers Pattern
Use When:
Array is sorted or checking pairs/subarrays.
Template:
bool hasTwoSum(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) return true;
else if (sum < target) left++;
else right--;
}
return false;
}
3. Fast and Slow Pointers
Use When:
Detecting cycles in linked lists or arrays.
Template:
bool hasCycle(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
Complete DSA Pattern Templates (with Explanations)
}
return false;
}
