LeetBook: Sliding Window & Two Pointers (C++
Edition)
Author: Recreated for you. Language: C++ examples. This PDF includes: full chapters, 20+ practice
problems per chapter (listed), explanations, templates, and worked C++ solutions for key problems.
Use it as your interview cheat-sheet.
Chapter 1 — Introduction
Sliding window & two-pointer techniques convert brute-force O(n^2) approaches into O(n) by moving
pointers smartly over arrays or strings. Know when to use them: continuous subarrays/ substrings,
sorted arrays (pairs/triplets), and constraints over counts/sums.
Part I — Sliding Window
Overview:
- Fixed-size window: sum/average of length k
- Variable-size window: expand/shrink by constraints (≤k distinct, sum >= target, no repeats)
Patterns & Templates
Fixed-size window template (C++):
long long max_sum_subarray_k(const vector<int>& nums, int k) { long long window = 0;
for (int i = 0; i < k; ++i) window += nums[i]; long long best = window; for (int i =
k; i < [Link](); ++i) { window += nums[i] - nums[i-k]; best = max(best, window); }
return best; }
Variable-size sliding window template (C++):
int longest_k_distinct(const string& s, int k) { vector<int> freq(256, 0); int left =
0, best = 0, distinct = 0; for (int right = 0; right < [Link](); ++right) { if
(freq[(unsigned char)s[right]]++ == 0) ++distinct; while (distinct > k) { if
(--freq[(unsigned char)s[left]] == 0) --distinct; ++left; } best = max(best, right -
left + 1); } return best; }
Worked Examples — Sliding Window
1) Longest Substring Without Repeating Characters (C++) — Sliding window with last-seen indices.
int lengthOfLongestSubstring(const string& s) { vector<int> last(256, -1); int left
= 0, best = 0; for (int right = 0; right < [Link](); ++right) { left = max(left,
last[(unsigned char)s[right]] + 1); last[(unsigned char)s[right]] = right; best =
max(best, right - left + 1); } return best; }
2) Minimum Window Substring (C++) — classic hard problem using counters and a sliding window.
string minWindow(string s, string t) { if ([Link]()) return ""; vector<int>
need(128, 0); for (char c: t) need[c]++; int missing = [Link](), left = 0, start = 0,
len = INT_MAX; for (int right = 0; right < [Link](); ++right) { if (need[s[right]] >
0) --missing; --need[s[right]]; while (missing == 0) { if (right - left + 1 < len) {
start = left; len = right - left + 1; } ++need[s[left]]; if (need[s[left]] > 0)
++missing; ++left; } } return len == INT_MAX ? "" : [Link](start, len); }
3) Subarray Sum Equals K (C++) — use prefix sums and hash map; can be implemented with
sliding-window only when all numbers non-negative.
int subarraySum(vector<int>& nums, int k) { unordered_map<int,int> count; count[0] =
1; int sum = 0, res = 0; for (int x : nums) { sum += x; if ([Link](sum - k)) res
+= count[sum - k]; count[sum]++; } return res; }
Practice problems (Sliding Window) — 20+ (use these on LeetCode/HackerRank):
1. Maximum Sum Subarray of Size K
2. Longest Substring Without Repeating Characters
3. Longest Substring with At Most K Distinct Characters
4. Minimum Window Substring
5. Sliding Window Maximum (deque)
6. Subarray Sum Equals K
7. Longest Repeating Character Replacement
8. Fruit Into Baskets (at most 2 distinct)
9. Permutation in String
10. Minimum Size Subarray Sum ( >= target )
11. Max Consecutive Ones III
12. Longest Subarray of 1's After Deleting One Element
13. Number of Subarrays with Bounded Maximum
14. Count Number of Nice Subarrays (k odd numbers)
15. Find All Anagrams in a String
16. Smallest Subarray with Sum at Least K
17. Longest Subarray with Sum <= K (nonnegative)
18. Replace the Substring for Balanced String
19. Longest Turbulent Subarray
20. Maximum Number of Vowels in Substring of Given Length
21. Sliding Window Median (hard)
Part II — Two Pointers
Two-pointer techniques are ideal for sorted arrays, pair/triplet sum problems, and linked list
middle/merge operations. Main variants: inward pointers (l,r), slow-fast pointers (linked lists), and
partitioning pointers.
Templates (C++)
Two-sum on sorted array (two pointers):
vector<int> twoSumSorted(const vector<int>& nums, int target) { int l = 0, r =
[Link]() - 1; while (l < r) { int s = nums[l] + nums[r]; if (s == target) return
{l+1, r+1}; // or indices depending on problem else if (s < target) ++l; else --r; }
return {}; }
Slow/fast pointer template (linked list cycle detection / middle node):
// Example: find middle of linked list ListNode* middleNode(ListNode* head) {
ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow =
slow->next; fast = fast->next->next; } return slow; }
Worked Examples — Two Pointers
1) Container With Most Water (C++)
int maxArea(vector<int>& height) { int l = 0, r = [Link]() - 1; int best = 0;
while (l < r) { int h = min(height[l], height[r]); best = max(best, h * (r - l)); if
(height[l] < height[r]) ++l; else --r; } return best; }
2) 3Sum (C++) — sort then two-pointers for pairs
vector<vector<int>> threeSum(vector<int>& nums) { sort([Link](), [Link]());
vector<vector<int>> res; for (int i = 0; i < [Link](); ++i) { if (i > 0 && nums[i]
== nums[i-1]) continue; int l = i+1, r = [Link]()-1; while (l < r) { int s =
nums[i] + nums[l] + nums[r]; if (s == 0) { res.push_back({nums[i], nums[l],
nums[r]}); ++l; --r; while (l < r && nums[l] == nums[l-1]) ++l; while (l < r &&
nums[r] == nums[r+1]) --r; } else if (s < 0) ++l; else --r; } } return res; }
3) Remove Duplicates from Sorted Array (in-place)
int removeDuplicates(vector<int>& nums) { if ([Link]()) return 0; int slow = 1;
for (int fast = 1; fast < [Link](); ++fast) { if (nums[fast] != nums[fast-1]) {
nums[slow++] = nums[fast]; } } return slow; }
Practice problems (Two Pointers) — 20+ (use these on LeetCode/HackerRank):
1. Two Sum II - Input array is sorted
2. Container With Most Water
3. 3Sum
4. 3Sum Closest
5. 4Sum
6. Move Zeroes (maintain relative order)
7. Sort Colors (Dutch National Flag)
8. Valid Palindrome (two pointers)
9. Reverse String (in-place)
10. Squares of a Sorted Array (merge two pointers)
11. Partition Array by Parity
12. Merge Two Sorted Lists (linked list pointers)
13. Linked List Cycle / Detect & Find Cycle Start
14. Reorder List (L0→Ln→L1→Ln-1)
15. Remove Element (in-place)
16. Intersection of Two Arrays II
17. Minimum Size Subarray Sum (also sliding window)
18. Find Pair with Given Sum in BST (inorder + two pointers)
19. Longest Palindromic Substring (expand-around-center variant)
20. Subarray Product Less Than K (two pointers)
21. Partition to K Equal Sum Subsets (pointer based heuristics)
Chapter: Tips, Complexity & Recognizing Patterns
How to pick the pattern quickly:
- Problem mentions subarray/substring → sliding window
- Mentions sorted/input order irrelevant but asks pairs/triplets → sort + two pointers
- Mentions linked list middle/cycle → slow/fast pointers
- Wants min window/shortest substring satisfying condition → sliding window
Complexity reminders: Sliding window and inward two-pointer scans are O(n). Sorting before
two-pointers adds O(n log n). Hashmaps give O(n) expected time but with extra space.
Interview Micro-checklist
- Clarify constraints and edge cases (empty inputs, negatives, very large N)
- Choose correct pattern and state complexity
- Code a correct solution, then optimize
- Run through sample & edge tests out loud
- If stuck, present a brute force then optimize
Appendix: Extra Resources & Next Steps
Want this expanded into a 60–80 page PDF with diagrams and full solutions for all 40+ problems? I
can. For now this PDF includes core templates, 40+ problem list, and 9 worked C++ solutions as
examples. If you want more full solutions, tell me which problems and I'll add them.
