DSA Advanced Techniques

Beyond data structures and basic algorithms, there are several powerful problem-solving patterns that appear repeatedly in coding challenges and real-world optimization. This topic covers three of the most important: Two Pointers, Sliding Window, and Backtracking. Mastering these patterns enables solving a wide variety of problems elegantly and efficiently.

Two Pointers Technique

The Two Pointers technique uses two index variables that move through a data structure — typically from opposite ends or at different speeds. This eliminates the need for nested loops, reducing O(n²) solutions to O(n).

Pattern 1: Opposite Direction Pointers

One pointer starts at the left, one at the right. They move toward each other.


# Check if a string is a palindrome
def is_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome("racecar"))   # Output: True
print(is_palindrome("hello"))     # Output: False

Pattern 2: Two Sum in a Sorted Array


def two_sum_sorted(arr, target):
    left = 0
    right = len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1      # Need larger sum — move left pointer right
        else:
            right -= 1     # Need smaller sum — move right pointer left
    return []

print(two_sum_sorted([1, 3, 6, 8, 11], 9))   # Output: [1, 3] — 3 + 6 = 9 (Wait: indices 1,2)
# Corrected:
print(two_sum_sorted([1, 3, 6, 8, 11], 14))  # Output: [2, 3] — 6 + 8 = 14

Pattern 3: Removing Duplicates from a Sorted Array


def remove_duplicates(arr):
    if not arr:
        return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1   # Number of unique elements

nums = [1, 1, 2, 2, 3, 4, 4, 5]
k = remove_duplicates(nums)
print("Unique count:", k)
print("Array:", nums[:k])   # Output: [1, 2, 3, 4, 5]

Sliding Window Technique

The Sliding Window technique maintains a subset (window) of elements from a sequence and slides it across the data. It avoids recomputing the entire window each time by incrementally adding the new element and removing the old one. This reduces many O(n²) brute-force solutions to O(n).

Fixed-Size Sliding Window


# Maximum sum of any subarray of size k
def max_sum_subarray(arr, k):
    n = len(arr)
    if n < k:
        return None

    # Compute sum of first window
    window_sum = sum(arr[:k])
    max_sum = window_sum

    # Slide the window: add next element, remove first element
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)

    return max_sum

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))   # Output: 9  (5+1+3)

Variable-Size Sliding Window


# Smallest subarray with sum >= target
def min_subarray_length(arr, target):
    left = 0
    current_sum = 0
    min_len = float('inf')

    for right in range(len(arr)):
        current_sum += arr[right]

        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1

    return min_len if min_len != float('inf') else 0

print(min_subarray_length([2, 3, 1, 2, 4, 3], 7))   # Output: 2  (4+3)

Longest Substring Without Repeating Characters


def longest_unique_substring(s):
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

print(longest_unique_substring("abcabcbb"))   # Output: 3  (abc)
print(longest_unique_substring("pwwkew"))     # Output: 3  (wke)

Backtracking

Backtracking is a problem-solving technique that builds solutions incrementally and abandons (backtracks) a partial solution as soon as it determines that it cannot possibly lead to a valid complete solution. It is like navigating a maze — if a path leads to a dead end, step back and try a different direction.

Backtracking is used for problems involving permutations, combinations, subsets, and constraint satisfaction.

Generating All Subsets


def subsets(nums):
    result = []

    def backtrack(start, current):
        result.append(current[:])   # Add a copy of current subset
        for i in range(start, len(nums)):
            current.append(nums[i])       # Include nums[i]
            backtrack(i + 1, current)     # Recurse
            current.pop()                 # Backtrack — remove nums[i]

    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

Generating All Permutations


def permutations(nums):
    result = []

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for num in nums:
            if num not in current:
                current.append(num)
                backtrack(current)
                current.pop()   # Backtrack

    backtrack([])
    return result

print(permutations([1, 2, 3]))
# Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

N-Queens Problem

Place N queens on an N×N chessboard so no two queens threaten each other.


def n_queens(n):
    results = []
    cols = set()
    pos_diag = set()   # row + col
    neg_diag = set()   # row - col

    board = [["." for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:
            results.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row + col) in pos_diag or (row - col) in neg_diag:
                continue   # Invalid position — skip
            # Place queen
            board[row][col] = "Q"
            cols.add(col)
            pos_diag.add(row + col)
            neg_diag.add(row - col)

            backtrack(row + 1)

            # Remove queen (backtrack)
            board[row][col] = "."
            cols.remove(col)
            pos_diag.remove(row + col)
            neg_diag.remove(row - col)

    backtrack(0)
    return len(results)   # Number of valid arrangements

print(n_queens(4))   # Output: 2
print(n_queens(8))   # Output: 92

Comparing the Three Techniques

  • Two Pointers: Works on sorted arrays or linked lists. Reduces O(n²) pair problems to O(n).
  • Sliding Window: Works on contiguous subarrays or substrings. Reduces O(n²) window problems to O(n).
  • Backtracking: Explores all valid solutions via DFS and abandons invalid paths early. Exponential time in the worst case but pruning makes it practical.

Key Points

  • Two Pointers uses two index variables to scan from ends inward or at different speeds — ideal for sorted arrays and pair-sum problems.
  • Sliding Window maintains a moving subset of data, updating incrementally — ideal for subarray or substring optimization problems.
  • Backtracking builds solutions step-by-step, using recursion to explore paths and abandoning dead ends early.
  • These three techniques appear in a large percentage of coding interview problems across all difficulty levels.
  • Recognizing the right pattern is often the key to solving a problem efficiently.
  • Backtracking problems can often be identified by keywords like "all possible," "all combinations," or "generate all."
Previous lessons
Back to courses

Leave a Comment