Recursion, two pointers and sliding window — Data Structures & Algorithms

9. Recursion, two pointers and sliding window

Intermediate★ Must knowLesson 9 of 10

Recursion = a function calling itself with a smaller input until a base case. Every recursion uses stack space; convert to iteration when depth may be large.

csharp

long Factorial(int n) => n <= 1 ? 1 : n * Factorial(n - 1);

Two pointers — walk from both ends or at two speeds, O(n) instead of O(n²):

csharp

bool IsPalindrome(string s)
{
    int i = 0, j = s.Length - 1;
    while (i < j)
    {
        if (!char.IsLetterOrDigit(s[i])) { i++; continue; }
        if (!char.IsLetterOrDigit(s[j])) { j--; continue; }
        if (char.ToLowerInvariant(s[i++]) != char.ToLowerInvariant(s[j--])) return false;
    }
    return true;
}
// Fast/slow pointers detect a cycle in a linked list (Floyd's algorithm).

Sliding window — maintain a window over a sequence and move its edges:

csharp

int LongestUniqueSubstring(string s)          // "abcabcbb" → 3
{
    var lastSeen = new Dictionary<char, int>();
    int best = 0, start = 0;
    for (int end = 0; end < s.Length; end++)
    {
        if (lastSeen.TryGetValue(s[end], out int prev) && prev >= start) start = prev + 1;
        lastSeen[s[end]] = end;
        best = Math.Max(best, end - start + 1);
    }
    return best;
}

Other patterns: prefix sums (range sums in O(1)), binary search on the answer, monotonic stack (next greater element), intervals (sort by start, merge).