NeFut Logo NeFut
中 Admin Login

In-Depth Analysis of Two Pointers Technique and Sliding Window Applications

Published at: 2026-05-27 09:17 Last updated: 2026-06-17 08:35
#algorithm #C++ #Sliding Window

Core Logic and Mathematical Principles

Two Pointers is not an independent algorithm, but rather a category of state-space pruning strategies built upon sequence monotonicity. Its primary contribution is optimizing the naive double-loop complexity of $O(N^2)$ down to $O(N)$.

At its core, it operates within a two-dimensional state space $(i, j)$, filtering out redundant branches based on boundary monotonicity. If the state function is monotonic (e.g., $f(i, j) \le f(i, j+1)$), as the primary pointer $i$ advances, the critical pointer $j$ that satisfies the constraints only needs to move in a single direction (either converging or advancing together) without ever backtracking. This irreversible topological order keeps the total lifetime of pointer steps proportional to the length of the sequence.

State Design, Topological Evolution, and Specific Problems Solved

1. Collision Pointers (Two-Way Convergence)

The left and right pointers are initialized at opposite ends of the sequence (l = 0, r = N - 1) and move inward toward each other.

  1. Target Convergence in Sorted Sequences: Finding pairs in a sorted array that satisfy a specific algebraic relation (e.g., $A[l] + A[r] == \text{target}$).
  2. Symmetry Verification and Transformation: Checking if a string is a palindrome, or reversing an array/linked list in-place.
  3. Interval Boundary Reduction: Problems like "Container With Most Water," where comparing the heights of both ends allows monotonically pruning boundaries that cannot yield an optimal solution.

Container With Most Water problem: $$V(i, j) = (j - i) \times \min(a_i, a_j)$$ Find $$\max_{(i, j) \in \Omega} V(i, j)$$

2. Fast and Slow Pointers / Sliding Window

Two pointers move in the same direction. The fast pointer r drives the iteration while the slow pointer l lags behind, dynamically maintaining a contiguous interval between them.

  1. Variable-Stride Fast & Slow Pointers (Linked List Topology):
    • Cycle Detection: e.g., Floyd's Cycle-Finding Algorithm (fast pointer steps by 2, slow pointer steps by 1, used to detect cycles and locate the cycle entrance).
    • Position Targeting: Finding the midpoint of a linked list (the slow pointer reaches the middle exactly when the fast pointer hits the end) or finding the $K$-th node from the end.

Floyd's Cycle-Finding Algorithm (Detecting Cycles in Linked Lists) Problem Description: Determine whether a singly linked list contains a cycle, with O(1) space complexity. Algorithm Description: Initialize both fast and slow pointers to the head node. The slow pointer moves forward 1 step at a time, while the fast pointer moves forward 2 steps at a time. If the fast and slow pointers meet during the traversal (fast == slow), the linked list contains a cycle; if the fast pointer reaches the end (nullptr) first, the linked list is acyclic.

Finding the Midpoint of a Linked List (Single-Pass Binary Positioning) Problem Description: Precisely locate the midpoint of a linked list without knowing its total length, and with only one traversal allowed. Algorithm Description: Both fast and slow pointers start at the head node simultaneously. The slow pointer moves 1 step at a time, while the fast pointer moves 2 steps at a time (twice the speed of the slow pointer). When the fast pointer reaches the end of the list, the slow pointer is exactly at the midpoint.

Finding the K-th Node from the End (Fixed-Window Two Pointers) Problem Description: Efficiently locate the K-th node from the end of a singly linked list without knowing its total length and without backward traversal capability. Algorithm Description: Both fast and slow pointers point to the head node. Establish the initial gap: move the fast pointer forward K steps first, creating a fixed-length "window" between the two pointers. Synchronized advancement: then move both the slow and fast pointers forward at the same speed (1 step each) simultaneously. When the fast pointer reaches the end of the list (nullptr), the slow pointer points to the K-th node from the end, due to the fixed window length.

  1. Sliding Window (Contiguous Subarray Extremums/Counting):
    • Longest/Shortest Contiguous Subarray: Finding the maximum or minimum length of a contiguous subarray/substring that satisfies a given constraint (e.g., sum $\ge S$, containing at most $K$ distinct elements, or containing no repeating characters).
    • Fixed-Length Interval Statistics: Maintaining a window of a fixed size to calculate moving sums, character frequencies, or rolling maximum values.

Since both l and r increase monotonically without backtracking, each element enters and exits the window at most once. The total time complexity is represented as:

$$\text{Total Steps} = \sum_{i=1}^N (\Delta l_i + \Delta r_i) \le 2N = O(N)$$

C++ Standard Source Code

The following is a fully compliant sliding window template designed for the NOIP evaluation environment (Linux, GCC, -O2). Problem to solve: Find the length of the longest contiguous subarray containing no more than $K$ distinct elements.

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::max;

// Constraints: N <= 100000, element values within [0, 100000]
const int MAX_VAL = 100005;
int cnt[MAX_VAL]; // Frequency hash table, avoiding std::map to prevent introducing O(log N) complexity

int main() {
    // Optimize standard I/O stream performance; never mix with scanf/printf
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int l = 0;
    int distinct_types = 0;
    int max_len = 0;

    // r is the fast pointer, l is the slow pointer
    for (int r = 0; r < n; ++r) {
        // 1. Shift in the right-bound element, update state
        if (cnt[a[r]] == 0) {
            distinct_types++;
        }
        cnt[a[r]]++;

        // 2. When the window state is invalid (distinct types > k), continuously shrink the left bound l
        while (distinct_types > k) {
            cnt[a[l]]--;
            if (cnt[a[l]] == 0) {
                distinct_types--; // A type of element completely exits the window
            }
            l++; // Pitfall Alert: l++ must execute AFTER the state update logic
        }

        // 3. At this point, [l, r] is guaranteed to be a valid window; update global optimum
        max_len = max(max_len, r - l + 1);
    }

    cout << max_len << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Slow Pointer Out-of-Bounds Trap (Conditional Variances in Range Optimization)

Whether you need to strictly enforce l <= r inside your while loop depends entirely on the problem model:

2. Counter Updates and Pointer Increment Sequencing

When shrinking the left boundary, never write cnt[a[l++]]-- solely to save code lines. If the current cnt[a[l]] is exactly 1, this compound statement extracts the old index l to perform the subtraction, but increments l immediately afterward. If subsequent coupled states like if (cnt[a[l]] == 0) depend on it, they will read the value of a[l] at the new, incremented memory slot, collapsing your code logic.

Golden Rule: Under high-pressure contest environments, never combine ++/-- operators with complex array indexing on the same line. Keep it cleanly split: Update count $\rightarrow$ Check dependencies $\rightarrow$ Increment pointer.

Classic NOIP/Luogu Problems

1. Luogu P1638 Visiting Art Exhibition

2. Luogu P1102 A-B Pairs

The following is the core algorithmic code for these two classic problems, written to NOIP contest standards (high efficiency, avoiding high-constant containers).

Reference Code

  1. Luogu P1638 Visiting Art Exhibition (Shortest Valid Sliding Window)

Core Logic: The fast pointer r extends to include new artists. When the number of distinct artist types in the window curr_kinds == m, continuously update the global optimal solution inside the while loop while shrinking the slow pointer l to the right.

// Key variable definitions: n = total paintings, m = total artists
// a[] stores the paintings, cnt[] acts as a frequency hash table
int l = 1, curr_kinds = 0;
int ans_l = 1, ans_r = n, min_len = n + 1;

for (int r = 1; r <= n; ++r) {
    // 1. Shift in the right-bound element, update state
    if (cnt[a[r]] == 0) {
        curr_kinds++;
    }
    cnt[a[r]]++;

    // 2. When the window is valid (contains all artists), continuously shrink the left bound l
    while (curr_kinds == m) {
        // For shortest interval: update optimal solution inside the while loop (valid state)
        if (r - l + 1 < min_len) {
            min_len = r - l + 1;
            ans_l = l;
            ans_r = r;
        }

        // Remove the left-bound element
        cnt[a[l]]--;
        if (cnt[a[l]] == 0) {
            curr_kinds--; // A color type completely disappears; window becomes invalid, exiting the loop next iteration
        }
        l++; // Slow pointer moves right
    }
}

// Output the final locked shortest interval boundaries
cout << ans_l << " " << ans_r << "\n";
  1. Luogu P1102 A-B Pairs (Unidirectional Non-Backtracking Three Pointers)

Core Logic: Rearrange the equation to $A = B + C$. After sorting the array in ascending order, for each fixed slow pointer l (acting as $B$), use two non-backtracking fast pointers r1 and r2 to lock onto the left-closed, right-open interval of the target value $B + C$.

// Key variable definitions: n = number of elements, c = target difference
// a is a vector<long long>, ans must be long long because counts may exceed int range
std::sort(a.begin(), a.end());

long long ans = 0;
int r1 = 0; // Fast pointer 1: points to the first position where >= B + C
int r2 = 0; // Fast pointer 2: points to the first position where > B + C

for (int l = 0; l < n; ++l) {
    long long target = a[l] + c; // The target A value corresponding to the current B

    // 1. Move r1 until a[r1] begins to satisfy >= target (enter the left boundary of the equal-value interval)
    while (r1 < n && a[r1] < target) {
        r1++;
    }
    // 2. Move r2 until a[r2] begins to strictly exceed target (exit the right boundary of the equal-value interval)
    while (r2 < n && a[r2] <= target) {
        r2++;
    }

    // 3. At this point, all elements in the interval [r1, r2) are exactly equal to target
    // Since the array is monotonically increasing, r1 and r2 absolutely never need to backtrack across the entire main loop
    ans += (r2 - r1);
}

cout << ans << "\n";
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS