Competition Patterns

March 2026 · 22 min read

This final post in the two pointers series covers advanced problems that combine multiple pointer techniques. These are the patterns you will encounter most often in coding interviews and competitive programming.

Problem 1: Three Sum

Problem: Given an array of integers, find all unique triplets that sum to zero.

Example: [-1, 0, 1, 2, -1, -4] produces [[-1, -1, 2], [-1, 0, 1]].

The Strategy: Fix One, Two-Pointer the Rest

Sort the array first. Then for each element nums[i], run the opposite-end two-pointer technique on the subarray nums[i+1..n-1] looking for pairs that sum to -nums[i].

The outer loop runs O(n) times and each two-pointer scan takes O(n), giving O(n²) total. This is a significant improvement over the O(n³) brute force.

Step-Through Animation: Three Sum

Sorted array: [-4, -1, -1, 0, 1, 2]. Target sum = 0. The fixed element (blue, circled) is set by the outer loop. Left (green) and Right (orange) scan the remainder.

C++ Solution

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    int n = nums.size();

    for (int i = 0; i < n - 2; i++) {
        // Skip duplicate fixed elements
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        // Early termination: smallest triple too large
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
        // Skip: even largest triple too small
        if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;

        int left = i + 1, right = n - 1;
        int target = -nums[i];

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                result.push_back({nums[i], nums[left], nums[right]});
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

Four Sum Extension

The same idea extends to 4Sum: fix two elements with nested loops, then two-pointer the rest. This gives O(n³). In general, k-Sum can be solved in O(n^k-1) by fixing k-2 elements and running the two-pointer scan.

// 4Sum: O(n^3)
for (int i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] == nums[i-1]) continue;
    for (int j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] == nums[j-1]) continue;
        int left = j + 1, right = n - 1;
        long long target = (long long)goal - nums[i] - nums[j];
        // ... standard two-pointer scan for target
    }
}

Problem 2: Dutch National Flag (Sort Colors)

Problem: Given an array containing only 0s, 1s, and 2s, sort it in-place in a single pass. This is LeetCode 75: Sort Colors.

Example: [2, 0, 1, 2, 0, 1] becomes [0, 0, 1, 1, 2, 2].

Three Pointers, One Pass

This problem uses three pointers, making it a natural extension of two-pointer partitioning. The idea, credited to Edsger Dijkstra:

• low: boundary of the 0-region. Everything before low is 0.
• mid: current element being examined. Scans left to right.
• high: boundary of the 2-region. Everything after high is 2.

The array is partitioned into four zones:

• [0, low): all 0s (red zone, finalized)
• [low, mid): all 1s (white zone, finalized)
• [mid, high]: unprocessed elements
• (high, n-1]: all 2s (blue zone, finalized)

Step-Through Animation: Dutch National Flag

Array: [1, 2, 0, 1, 0, 2]. Three pointers: Low (green), Mid (blue), High (orange).

C++ Solution

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else { // nums[mid] == 2
            swap(nums[mid], nums[high]);
            high--;
            // do NOT advance mid
        }
    }
}

Problem 3: Trapping Rain Water

Problem: Given an array of non-negative integers representing an elevation map, compute how much water it can trap after rain.

Example: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] traps 6 units of water.

The Two-Pointer Approach

The key insight for trapping rain water: the water level at any position is determined by min(maxLeft, maxRight) - height[i], where maxLeft and maxRight are the tallest bars to the left and right of position i.

Instead of precomputing left-max and right-max arrays (which takes O(n) space), we can use two pointers to compute the answer in O(1) space:

• Maintain leftMax (tallest bar seen from the left) and rightMax (tallest bar seen from the right).
• Move the pointer on the side with the smaller max height.
• The water at the current position is guaranteed to be currentMax - height[current] because the other side is at least as tall.

Step-Through Animation: Trapping Rain Water

Heights: [3, 0, 2, 0, 4]. Left pointer (green) and Right pointer (orange) track max heights from each side.

C++ Solution

int trap(vector<int>& height) {
    int left = 0, right = height.size() - 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;
}

Pattern Recognition Guide

Here is a decision framework for choosing the right two-pointer pattern in competition settings:

More Competition Problems

vector<int> partitionLabels(string s) {
    int last[26] = {};
    for (int i = 0; i < s.size(); i++)
        last[s[i] - 'a'] = i;
    vector<int> result;
    int start = 0, end = 0;
    for (int i = 0; i < s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {
            result.push_back(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

Practice Problems

Series Summary

Across this four-part series, we covered the full spectrum of two-pointer techniques:

• Opposite Ends: Converge from both extremes. Best for sorted pair searches, palindromes, and container problems. O(n) time, O(1) space.
• Same Direction: Both pointers move forward. The read/write pattern handles in-place filtering and compaction. O(n) time, O(1) space.
• Fast/Slow: One pointer moves at double speed. Detects cycles and finds midpoints. O(n) time, O(1) space.
• Competition Patterns: Combine the basics into harder problems. k-Sum nests two pointers in loops. Dutch National Flag uses three pointers. Trapping rain water uses max-tracking from both sides.

The unifying principle: by maintaining two (or three) strategic positions and moving them according to problem-specific rules, you replace nested loops with linear scans. The key is always understanding which pointer to move and why.