Master sliding window and two-pointer techniques to solve substring, subarray, and array manipulation problems efficiently. Learn templates for expanding/shrinking windows, fast/slow pointers, and greedy two-pointer strategies.
Two fundamental techniques for optimizing string and array problems from O(n²) to O(n).
Maintain a window [left, right] that slides across the input. Expand right to include new elements, shrink left when constraints are violated.
Time Complexity: O(n) — each element enters and exits the window once.
Space Complexity: O(min(n, alphabet size)) for frequency maps.
Start with one pointer at the beginning and one at the end. Move inward based on comparisons. Works best on sorted data.
Variants: Fast/slow pointers for linked lists, 3+ pointers for complex problems.
Find the length of the longest substring without repeating characters.
Given a string s, find the length of the longest substring without repeating characters.
Use sliding window with a HashSet to track characters in the current window.
left = 0, maxLen = 0, and a HashSet.right from 0 to n-1. Add s[right] to the set.s[right] is a duplicate, remove s[left] and increment left.maxLen = max(maxLen, right - left + 1).public int LengthOfLongestSubstring(string s) { var charSet = new HashSet<char>(); int left = 0, maxLen = 0; for (int right = 0; right < s.Length; right++) { while (charSet.Contains(s[right])) { charSet.Remove(s[left]); left++; } charSet.Add(s[right]); maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; }
Input: s = "abcabcbb"
| right | char | window | maxLen |
|---|---|---|---|
| 0 | a | [a] | 1 |
| 1 | b | [a,b] | 2 |
| 2 | c | [a,b,c] | 3 |
| 3 | a | [b,c,a] | 3 |
| 4 | b | [c,a,b] | 3 |
| 5 | c | [a,b,c] | 3 |
| 6 | b | [b] | 3 |
| 7 | b | [b] | 3 |
Find two numbers that add up to a target value.
Given an array of integers and a target value, return the indices of the two numbers that add up to the target.
As you iterate, store each number and its index. For each number, check if target - num exists in the map.
value → index.complement = target - num.num → index to map and continue.public int[] TwoSum(int[] nums, int target) { var map = new Dictionary<int, int>(); for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; if (map.ContainsKey(complement)) { return new int[] { map[complement], i }; } if (!map.ContainsKey(nums[i])) { map.Add(nums[i], i); } } return new int[] { }; }
public int[] TwoSumSorted(int[] nums, int target) { int left = 0, right = nums.Length - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) return new int[] { left, right }; else if (sum < target) left++; else right--; } return new int[] { }; }
Find two vertical lines that form a container holding the most water.
Given an array of integers representing heights, find the two lines that form a container with maximum area.
Use two pointers starting at both ends. Area = min(left, right) × (right - left). Move the pointer with smaller height inward (greedy).
left = 0, right = n-1, maxArea = 0.maxArea if this area is larger.public int MaxArea(int[] height) { int left = 0, right = height.Length - 1; int maxArea = 0; while (left < right) { int h = Math.Min(height[left], height[right]); int w = right - left; int area = h * w; maxArea = Math.Max(maxArea, area); if (height[left] < height[right]) left++; else right--; } return maxArea; }
The height is limited by the shorter line. Moving the taller line inward only decreases width without potentially increasing height, so it's suboptimal. Moving the shorter line might find a taller line that compensates for lost width.
Find the starting position of a contiguous slice with minimal average.
Find the starting position of a slice with minimum average. A slice has length ≥ 2.
The minimum average slice has length 2 or 3. If a slice of length ≥ 4 has minimum average, one of its length-2 or length-3 subarrays will also have that or better average.
public int MinAvgTwoSlice(int[] A) { double minAvg = double.MaxValue; int minIdx = 0; // Check all slices of length 2 for (int i = 0; i < A.Length - 1; i++) { double avg = (A[i] + A[i + 1]) / 2.0; if (avg < minAvg) { minAvg = avg; minIdx = i; } } // Check all slices of length 3 for (int i = 0; i < A.Length - 2; i++) { double avg = (A[i] + A[i + 1] + A[i + 2]) / 3.0; if (avg < minAvg) { minAvg = avg; minIdx = i; } } return minIdx; }
Count the number of distinct contiguous slices without repeating elements.
Count all contiguous slices with no repeating elements. Cap the result at 1 billion.
For each position i, find the longest valid slice starting at i (no repeats). If the slice length is k, it contributes k valid slices ending at or before the right boundary.
public int CountDistinctSlices(int[] A) { const int MAX = 1000000000; var seen = new HashSet<int>(); int left = 0; long count = 0; for (int right = 0; right < A.Length; right++) { while (seen.Contains(A[right])) { seen.Remove(A[left]); left++; } seen.Add(A[right]); // All slices ending at right and starting at or after left count += (right - left + 1); if (count > MAX) return MAX; } return (int)count; }
Find all unique triplets that sum to a target value.
Find all unique triplets in an array that sum to zero (or a target).
Sort the array. Fix one element and use two pointers to find pairs that complete the triplet.
public IList<IList<int>> ThreeSum(int[] nums) { var result = new List<IList<int>>(); Array.Sort(nums); for (int i = 0; i < nums.Length - 2; i++) { if (nums[i] > 0) break; // No positive triplets possible if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates int left = i + 1, right = nums.Length - 1; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.Add(new List<int> { nums[i], nums[left], nums[right] }); while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates left++; right--; } else if (sum < target) left++; else right--; } } return result; }
Find the minimum window substring containing all characters of a pattern.
Given two strings s and t, find the minimum window substring in s that contains all characters in t.
Use sliding window with frequency maps. Expand right until all characters are matched, then shrink left while valid.
public string MinWindow(string s, string t) { if (t.Length > s.Length) return ""; var dictT = new Dictionary<char, int>(); var windowCounts = new Dictionary<char, int>(); foreach (char c in t) { if (!dictT.ContainsKey(c)) dictT[c] = 0; dictT[c]++; } int required = dictT.Count; int formed = 0; int left = 0; int minLen = int.MaxValue; int minLeft = 0; for (int right = 0; right < s.Length; right++) { char c = s[right]; if (!windowCounts.ContainsKey(c)) windowCounts[c] = 0; windowCounts[c]++; if (dictT.ContainsKey(c) && windowCounts[c] == dictT[c]) formed++; while (left <= right && formed == required) { char lc = s[left]; int windowLen = right - left + 1; if (windowLen < minLen) { minLen = windowLen; minLeft = left; } windowCounts[lc]--; if (dictT.ContainsKey(lc) && windowCounts[lc] < dictT[lc]) formed--; left++; } } return minLen == int.MaxValue ? "" : s.Substring(minLeft, minLen); }
Calculate how much rainwater can be trapped after raining on an elevation map.
Given an array of heights, calculate the total amount of rainwater trapped after raining.
Water at position i is trapped between leftMax and rightMax. Use two pointers moving inward to track maxima.
left = 0, right = n-1. Track leftMax and rightMax.public int Trap(int[] height) { int left = 0, right = height.Length - 1; int leftMax = 0, rightMax = 0; int water = 0; while (left < right) { if (height[left] < height[right]) { if (height[left] >= leftMax) leftMax = height[left]; else water += leftMax - height[left]; left++; } else { if (height[right] >= rightMax) rightMax = height[right]; else water += rightMax - height[right]; right--; } } return water; }
Find the longest substring with at most k character replacements to make all same.
Find the length of the longest substring you could create with at most k replacements.
Sliding window: track the frequency of the most common character. If (window size - max freq) ≤ k, the window is valid.
public int CharacterReplacement(string s, int k) { var charCount = new Dictionary<char, int>(); int left = 0, maxFreq = 0, maxLen = 0; for (int right = 0; right < s.Length; right++) { if (!charCount.ContainsKey(s[right])) charCount[s[right]] = 0; charCount[s[right]]++; maxFreq = Math.Max(maxFreq, charCount[s[right]]); // Number of changes needed = window size - max frequency int changes = (right - left + 1) - maxFreq; while (changes > k) { charCount[s[left]]--; left++; changes = (right - left + 1) - maxFreq; } maxLen = Math.Max(maxLen, right - left + 1); } return maxLen; }
Maximize fruits collected when using at most 2 distinct basket types.
Given an array of fruit types, maximize fruits collected with at most 2 distinct types.
Sliding window with hashmap to track fruit frequencies. Maintain at most 2 distinct fruits.
public int TotalFruit(int[] fruits) { var fruitCount = new Dictionary<int, int>(); int left = 0, maxFruits = 0; for (int right = 0; right < fruits.Length; right++) { if (!fruitCount.ContainsKey(fruits[right])) fruitCount[fruits[right]] = 0; fruitCount[fruits[right]]++; while (fruitCount.Count > 2) { fruitCount[fruits[left]]--; if (fruitCount[fruits[left]] == 0) fruitCount.Remove(fruits[left]); left++; } maxFruits = Math.Max(maxFruits, right - left + 1); } return maxFruits; }
Check if s1 is a permutation of any substring in s2.
Given two strings s1 and s2, return true if s1 is a permutation of a substring in s2.
Fixed-size sliding window of size len(s1). Compare character frequencies.
public bool CheckInclusion(string s1, string s2) { if (s1.Length > s2.Length) return false; int[] freq1 = new int[26]; int[] freq2 = new int[26]; for (int i = 0; i < s1.Length; i++) { freq1[s1[i] - 'a']++; freq2[s2[i] - 'a']++; } if (ArraysEqual(freq1, freq2)) return true; for (int i = s1.Length; i < s2.Length; i++) { freq2[s2[i] - 'a']++; freq2[s2[i - s1.Length] - 'a']--; if (ArraysEqual(freq1, freq2)) return true; } return false; } private bool ArraysEqual(int[] a, int[] b) { for (int i = 0; i < a.Length; i++) if (a[i] != b[i]) return false; return true; }
Find the maximum average of a contiguous subarray of fixed size k.
Find the maximum average of all contiguous subarrays of size k.
Compute sum of first k elements. Slide the window: subtract left element, add new right element.
public double FindMaxAverage(int[] nums, int k) { double sum = 0; for (int i = 0; i < k; i++) sum += nums[i]; double maxSum = sum; for (int i = k; i < nums.Length; i++) { sum += nums[i] - nums[i - k]; maxSum = Math.Max(maxSum, sum); } return maxSum / k; }
Count the number of contiguous subarrays with product less than k.
Count all contiguous subarrays whose product is less than k.
Sliding window: expand right while product < k. When invalid, shrink left. For each position right, all subarrays [left..right] to [right..right] are valid → count = right - left + 1.
public int NumSubarrayProductLessThanK(int[] nums, int k) { if (k <= 1) return 0; int left = 0, product = 1, count = 0; for (int right = 0; right < nums.Length; right++) { product *= nums[right]; while (product >= k) { product /= nums[left]; left++; } // All subarrays [left..right] to [right..right] have product < k count += (right - left + 1); } return count; }
Sort an array of colors (0, 1, 2) in-place using three pointers.
Sort an array containing only 0, 1, 2 (colors) in-place without using sort function.
Use three pointers: left (0s), mid (current), right (2s).
public void SortColors(int[] nums) { int left = 0, mid = 0, right = nums.Length - 1; while (mid <= right) { if (nums[mid] == 0) { Swap(nums, left, mid); left++; mid++; } else if (nums[mid] == 1) { mid++; } else // nums[mid] == 2 { Swap(nums, mid, right); right--; } } } private void Swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }
Remove duplicates in-place and return the new length.
Remove duplicates from a sorted array in-place. Return the length of the array with unique elements.
Use two pointers: left (position to write) and right (position to read). When a new unique element is found, write it to left position and increment left.
left = 1 (first unique element is at index 0).public int RemoveDuplicates(int[] nums) { if (nums.Length == 0) return 0; int left = 1; for (int right = 1; right < nums.Length; right++) { if (nums[right] != nums[right - 1]) { nums[left] = nums[right]; left++; } } return left; }
Input: nums = [1,1,2,2,3]
| right | nums[right] | Action | nums | left |
|---|---|---|---|---|
| 1 | 1 | Skip (same) | [1,1,2,2,3] | 1 |
| 2 | 2 | Write to left | [1,2,2,2,3] | 2 |
| 3 | 2 | Skip (same) | [1,2,2,2,3] | 2 |
| 4 | 3 | Write to left | [1,2,3,2,3] | 3 |