Sorting gives you a direction. Two pointers converging from the ends turn that direction into an O(n) search over all n² pairs.
The sliding window walks two indices forward together. Two pointers, in the classic sense, sends them toward each other from opposite ends. Each step throws away a whole family of candidate pairs at once, which is why a doubly-nested loop collapses into a single pass.
left at index 0 and right at index n-1. Evaluate the pair. Because the array is sorted, the comparison tells you which pointer cannot possibly be part of the answer with any remaining partner, so you move that one inward and never look at it again. Each step eliminates an entire row or column of the n×n pair grid.Reading the figure. The pointers start at both ends. The sum is too small, so left moves right. Every pair that used the old left value is gone in one step.
This is the proof to have ready, because it is the only interesting thing to say about the pattern.
nums[left] + nums[right] < target. Since the array is sorted, nums[right] is the largest value still available. So nums[left] paired with anything left in the range gives a sum no bigger than the one just computed, which is already too small. Therefore nums[left] is in no solution, and dropping it loses nothing. The symmetric argument covers the too-large case.Each iteration moves exactly one pointer inward by one, and the pointers start n-1 apart, so the loop runs at most n-1 times. O(n) after the sort.
public static class ConvergeTemplate
{
/// <summary>Find a pair in a sorted array summing to target.</summary>
/// <param name="nums">Sorted integers.</param>
/// <param name="target">The required sum.</param>
/// <returns>The 0-based index pair, or null if no pair exists.</returns>
/// <example><c>Converge([1, 3, 4, 9], 13)</c> returns (2, 3).</example>
public static (int Left, int Right)? Converge(int[] nums, int target)
{
// 0: first index. nums.Length - 1: last index, since indices start at 0.
int left = 0, right = nums.Length - 1;
// Invariant: no pair that uses an index outside left..right can sum to target.
while (left < right) // strict: never pair an element with itself
{
long total = (long)nums[left] + nums[right]; // long: two ints can overflow
if (total == target)
return (left, right);
if (total < target)
left++; // +1: nums[left] is too small even with the biggest partner
else
right--; // -1: nums[right] is too big even with the smallest partner
}
return null; // the pointers met: no pair exists
}
}
Use left < right, not <=, whenever the two pointers must select two different elements.
public static class CompactTemplate
{
/// <summary>Filter in place. Returns the length of the kept prefix.</summary>
/// <param name="nums">Values to filter. Mutated in place.</param>
/// <param name="keep">Placeholder test that says "this value stays".
/// Example: <c>x => x != 0</c> drops zeros.</param>
/// <returns>The count of kept values, now in nums[0..count-1].</returns>
/// <example><c>Compact([0, 1, 0, 3], x => x != 0)</c> returns 2.</example>
public static int Compact(int[] nums, Func<int, bool> keep)
{
int write = 0; // 0: nothing kept yet. Next kept goes in slot 0
// read: index of the value being judged.
// Invariant: nums[0..write-1] holds every kept value from nums[0..read-1].
for (int read = 0; read < nums.Length; read++) // 0: judge from the first value
{
if (keep(nums[read]))
{
nums[write] = nums[read]; // write never overtakes read, so this is safe
write++; // +1: the kept prefix grew by one slot
}
}
return write; // write = count of kept values
}
}
The in-place filter. write <= read always holds, so the write can never clobber an element that has not been read yet.
Reading the figure. Green cells are the kept prefix, nums[0..write-1]. Amber is the value being read. Red is a value that is skipped. Grey cells past write hold leftovers that no longer matter.
public static class TripletsTemplate
{
/// <summary>Reduce a 3-sum to n independent 2-sums.</summary>
/// <param name="nums">Integers in any order. Sorted in place.</param>
/// <param name="target">The sum each triplet must reach.</param>
/// <returns>Every unique triplet, each ascending.</returns>
/// <example><c>Triplets([1, 2, 3, 4], 6)</c> returns [[1, 2, 3]].</example>
public static List<List<int>> Triplets(int[] nums, int target)
{
Array.Sort(nums); // sorted order is what lets Template A work
var output = new List<List<int>>();
// i: index of the anchor. - 2: leave room for two partners after i.
for (int i = 0; i < nums.Length - 2; i++)
{
// i > 0: slot 0 has no left neighbour to compare. i - 1: the previous anchor.
if (i > 0 && nums[i] == nums[i - 1])
continue; // skip duplicate anchors
// i + 1: partners come after the anchor. nums.Length - 1: the last index.
int left = i + 1, right = nums.Length - 1;
int want = target - nums[i]; // Template A on nums[left..right] for this sum
while (left < right)
{
int pair = nums[left] + nums[right];
if (pair < want) left++; // +1: need a bigger sum
else if (pair > want) right--; // -1: need a smaller sum
else
{
output.Add([nums[i], nums[left], nums[right]]);
left++; // +1: step past the low partner
right--; // -1: step past the high partner
// left - 1: the value just used. Skip while it repeats.
while (left < right && nums[left] == nums[left - 1]) left++;
}
}
}
return output;
}
}
The template is filled in here so it compiles and runs, with the target as a parameter. k-sum is a for loop wrapped around (k-1)-sum. 3Sum is O(n²), 4Sum is O(n³).
Reading the figure. Violet is the fixed anchor i. Amber cells are left and right. Blue cells are still in range. Red is an anchor skipped because it repeats the one before.
left <= right when you need two distinct elements. It lets an element pair with itself.Array.Sort(nums) sorts in place. Mention it, or sort a copy made with (int[])nums.Clone() or nums.Order().ToArray().int values can add past int.MaxValue and wrap to a negative. Add them as long when the range is not small.Given a 1-indexed array numbers sorted in non-decreasing order, find the two numbers that add up to target and return their 1-based indices. Exactly one solution exists, and you may not use an element twice. Extra space must be O(1).
public static class TwoSumSorted
{
/// <summary>Indices of the two values in a sorted array that sum to target.</summary>
/// <param name="numbers">Non-decreasing integers.</param>
/// <param name="target">The required sum.</param>
/// <returns>The 1-based indices (i, j) with i < j.</returns>
/// <exception cref="ArgumentException">No pair sums to target.</exception>
/// <example><c>Find([2, 7, 11, 15], 9)</c> returns (1, 2).</example>
public static (int, int) Find(int[] numbers, int target)
{
// 0: first index. numbers.Length - 1: last index, since indices start at 0.
int left = 0, right = numbers.Length - 1;
// Invariant: the answer pair, if any, lies inside left..right.
while (left < right) // strict: an element cannot pair with itself
{
long total = (long)numbers[left] + numbers[right]; // long: avoid overflow
if (total == target)
return (left + 1, right + 1); // +1: the problem wants 1-based indices
if (total < target)
left++; // numbers[left] is too small even with the largest partner
else
right--; // numbers[right] is too large even with the smallest partner
}
throw new ArgumentException("no pair sums to target");
}
}
numbers = [2, 7, 11, 15], target = 18:
left 0, right 3. Sum 17. Too small, so left++.left 1, right 3. Sum 22. Too large, so right--.left 1, right 2. Sum 18. A match, so return (2, 3).Reading the figure. Amber cells are the two pointers. Blue cells are still in range. Red cells are dropped, since no remaining partner can work with them. Green is the answer pair.
[3, 3] with target = 6: works, and the two pointers land on different indices.(-1, -1) that a caller may not check.numbers[left] + numbers[right] can overflow an int. The code adds them as long.Dictionary in one pass. With it, sortedness lets me converge.”Given a sorted array nums, remove duplicates in place so each value appears once, keeping the relative order. Return the number of unique elements k. The first k slots of nums must hold the result. What follows does not matter.
read scans every element. write marks where the next kept element goes. Because duplicates are removed, write can only fall behind read, never overtake it, so writing is always safe.public static class RemoveDuplicates
{
/// <summary>Compact a sorted array in place so each value appears once.</summary>
/// <param name="nums">Sorted integers. Mutated in place.</param>
/// <returns>k, the number of unique values. nums[0..k-1] holds them in order.</returns>
/// <example><c>Once([0, 0, 1, 1, 1, 2, 2, 3])</c> returns 4,
/// and the first 4 slots become 0, 1, 2, 3.</example>
public static int Once(int[] nums)
{
if (nums.Length == 0)
return 0; // 0: an empty array has no unique values
int write = 1; // nums[0] is always kept, so the next slot is 1
// read: index of the value being judged. Start at 1: slot 0 is already kept.
// Invariant: nums[0..write-1] are the unique values of nums[0..read-1].
for (int read = 1; read < nums.Length; read++)
{
// nums[write - 1] is the last value we decided to keep.
// Sorted input means a new value only has to differ from that one.
if (nums[read] != nums[write - 1])
{
nums[write] = nums[read]; // copy the new value into the next free slot
write++; // +1: the kept prefix grew by one
}
}
return write;
}
}
nums[write - 1] and not nums[read - 1]Both work for this problem, because sorted duplicates are adjacent and the prefix mirrors the source. But nums[write - 1] is the honest expression of the intent: is this different from the last thing I kept. That version generalises without change to the common follow-up, allow each value at most twice, where you compare against nums[write - 2]. The read - 1 version does not generalise.
nums = [1, 1, 2]:
read = 1. nums[read] = 1 and nums[write - 1] = 1. Equal, so skip. write stays 1.read = 2. nums[read] = 2 and nums[write - 1] = 1. Write nums[1] = 2. write becomes 2.Reading the figure. Green cells are the kept prefix. Amber is the value being copied. Red is a skipped duplicate. Grey cells are not kept yet or are leftovers.
public static class RemoveDuplicatesTwice
{
/// <summary>Same idea, but each value may survive twice.</summary>
/// <param name="nums">Sorted integers. Mutated in place.</param>
/// <returns>k. nums[0..k-1] holds each value at most twice.</returns>
/// <example><c>AtMostTwice([1, 1, 1, 2, 2, 3])</c> returns 5.</example>
public static int AtMostTwice(int[] nums)
{
int write = 0; // 0: nothing kept yet. Next kept goes in slot 0
// read: index of the item being judged.
// Invariant: nums[0..write-1] holds each value seen so far, at most twice.
for (int read = 0; read < nums.Length; read++) // 0: judge from the first value
{
int value = nums[read];
// Keep it unless the last two kept values are already this value.
// write < 2: fewer than 2 kept, so no value can have 2 copies yet.
// write - 2: two slots back. Sorted input means a match there also
// matches the slot in between. So value would be a third copy.
if (write < 2 || value != nums[write - 2])
{
nums[write] = value;
write++; // +1: the kept prefix grew by one
}
}
return write;
}
}
One changed constant. This is why the write - 1 framing is worth the habit.
0.1.write never passes read, so writing into the prefix cannot destroy data I still need to read.”Given an array nums, return all unique triplets [a, b, c] with a + b + c == 0. The result must not contain duplicate triplets.
nums[i], then the problem becomes: find pairs in nums[(i + 1)..] summing to -nums[i]. That is Two Sum II.left and repeated right values.public static class ThreeSum
{
/// <summary>All unique triplets from nums that sum to zero.</summary>
/// <param name="nums">Integers, in any order. Sorted in place as a side effect.</param>
/// <returns>A list of triplets, each sorted ascending, with no duplicates.</returns>
/// <example><c>Find([-1, 0, 1, 2, -1, -4])</c> returns [[-1, -1, 2], [-1, 0, 1]].</example>
public static List<List<int>> Find(int[] nums)
{
Array.Sort(nums); // sorted order makes the two-pointer scan valid
int n = nums.Length;
var triplets = new List<List<int>>();
// i: index of the anchor. n - 2: leave room for two partners after i.
for (int i = 0; i < n - 2; i++)
{
// Sorted, so once the anchor is positive the three smallest remaining
// values are all positive and no triplet can reach zero.
if (nums[i] > 0) // 0: the target sum
break;
// Dedup 1: an anchor value already used produces the same triplets.
// i > 0: slot 0 has no earlier anchor. i - 1: the previous anchor.
if (i > 0 && nums[i] == nums[i - 1])
continue;
// i + 1: partners sit after the anchor. n - 1: the last index.
int left = i + 1, right = n - 1;
// Invariant: every new triplet for this anchor uses partners in left..right.
while (left < right)
{
int total = nums[i] + nums[left] + nums[right];
if (total < 0) // 0: target. Too small, so raise the low end
left++;
else if (total > 0) // too big, so lower the high end
right--;
else
{
triplets.Add([nums[i], nums[left], nums[right]]);
left++; // +1: step past the low partner just used
right--; // -1: step past the high partner just used
// Dedup 2 and 3: slide past repeats of the values just used.
// left - 1: the value just used. Skip while it repeats.
while (left < right && nums[left] == nums[left - 1])
left++;
// right + 1: the value just used. Skip while it repeats.
while (left < right && nums[right] == nums[right + 1])
right--;
}
}
}
return triplets;
}
}
nums = [-2, 0, 0, 2, 2] after sorting. With anchor -2 at i = 0, the pointers find (0, 2) and record [-2, 0, 2]. Both pointers move, landing on the second 0 and the second 2, which are repeats, so both dedup loops advance past them and the pointers cross. Without those loops the same triplet is recorded twice.
Reading the figure. Violet is the anchor i. Amber cells are left and right. Blue cells are still in range. Red is a repeat that the skip loop steps over.
HashSet<(int, int, int)> also produces the right answer. Value tuples hash and compare by their parts, so this works out of the box. It is easier to write under pressure. It costs extra memory and hashing, and it hides the fact that you understand where the duplicates come from. Write the explicit skips if you can. Mention the set as the fallback you would use if short on time.The outer loop runs n times, each inner converge is O(n). Output space is not counted. Array.Sort works in place, so the sort adds only O(log n) stack.
i < n - 2 fails at once, so it returns an empty list.[0, 0, 0, 0]: returns exactly [[0, 0, 0]]. A good test of the dedup logic.[].nums[i] > 0 break is an optimisation, not a correctness fix. Say which it is.height[i] is the height of a vertical line at position i. Pick two lines so that the container they form with the x-axis holds the most water. Return that maximum area. The area for a pair is (j - i) * min(height[i], height[j]).
public static class ContainerWithMostWater
{
/// <summary>Largest area of water trapped between two vertical lines.</summary>
/// <param name="height">Non-negative line heights, indexed by position.</param>
/// <returns>The maximum area. 0 if fewer than two lines.</returns>
/// <example><c>MaxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])</c> returns 49.</example>
public static int MaxArea(int[] height)
{
// 0: leftmost line. height.Length - 1: rightmost line. Widest pair first.
int left = 0, right = height.Length - 1;
int best = 0; // 0: no container measured yet
// Invariant: every pair with an end outside left..right is no better than best.
while (left < right)
{
int span = right - left; // width between the two lines
// The shorter line caps the water level.
best = Math.Max(best, span * Math.Min(height[left], height[right]));
// Only moving the shorter line can raise the min, so only that move
// has any chance of beating the current area.
if (height[left] < height[right])
left++; // +1: give up the short left line
else
right--; // -1: give up the short right line
}
return best;
}
}
height[left] < height[right]. Consider any pair (left, j) with j < right. Its width is smaller than right - left, and its height is at most height[left], which is the current minimum. So its area is strictly less than the area just computed. Every remaining pair that uses left is therefore dominated, and discarding left cannot lose the optimum. That is exactly the exchange argument from the top of the page, with width in place of sortedness.height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:
left 0, right 8. Span 8, min height 1, area 8. best = 8.left 1, right 8. Span 7, min height 7, area 49. best = 49.left 1, right 7. Span 6, min height 3, area 18. best = 49.left 1, right 6. Span 5, min height 8, area 40. best = 49.Reading the figure. Each chart is one step. Amber bars are left and right. Blue bars are still in range. The shaded box is the water, as wide as the span and as tall as the shorter line. Green marks the best area.
The scan continues but never beats 49.
0.left < right whenever the two picks must be distinct elements.Pattern 3, Fast and Slow Pointers, keeps two pointers moving in the same direction but at different speeds. That difference in speed is what detects a cycle in a structure you cannot index into.