by Lead by code Jan 01, 2025 iOS

DSA Two Pointer Approach

The two-pointer approach is a versatile technique in Data Structures and Algorithms (DSA) used to optimize problems that involve linear traversal of arrays, lists, or strings. Here’s a detailed explanation of when to use it and its applications:

When to Use the Two-Pointer Approach

The two-pointer technique is most effective when:

  1. Sorted Input:
    • The array or list is sorted (e.g., for searching pairs or subarrays).
    • Examples: Finding two numbers that add up to a target, removing duplicates from a sorted array.
  2. Traversal from Both Ends:
    • You need to process elements from both the beginning and the end of the array.
    • Examples: Palindrome checking, merging two sorted arrays, or the “container with most water” problem.
  3. Finding Subarrays or Substrings:
    • When searching for specific properties (e.g., sum, maximum length) within a subarray or substring.
    • Example: Sliding window problems like finding the longest substring without repeating characters.
  4. Eliminating Redundant Computations:
    • When you want to avoid nested loops by narrowing the range of exploration.
    • Example: Sorting and then applying two pointers to reduce time complexity.

Common Problem Types

Here are common scenarios where the two-pointer approach is used:

1. Finding Pairs

  • Problem: Find two numbers in a sorted array that sum up to a target.
  • Approach: Use one pointer at the start and another at the end. Move the pointers based on the current sum.
  • Example:swiftCopy code
func twoSum(_ nums: [Int], _ target: Int) -> (Int, Int)? {
    var left = 0, right = nums.count - 1
    while left < right {
        let sum = nums[left] + nums[right]
        if sum == target {
            return (left, right)
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    return nil
}

2. Merging Two Sorted Arrays

  • Problem: Merge two sorted arrays into one sorted array.
  • Approach: Use one pointer for each array and compare elements to construct the result.
func mergeSortedArrays(_ array1: [Int], _ array2: [Int]) -> [Int] {
    var result: [Int] = []
    var pointer1 = 0 // Pointer for array1
    var pointer2 = 0 // Pointer for array2
    
    // Compare elements from both arrays and append the smaller one to the result
    while pointer1 < array1.count && pointer2 < array2.count {
        if array1[pointer1] < array2[pointer2] {
            result.append(array1[pointer1])
            pointer1 += 1
        } else {
            result.append(array2[pointer2])
            pointer2 += 1
        }
    }
    
    // Append remaining elements from array1, if any
    while pointer1 < array1.count {
        result.append(array1[pointer1])
        pointer1 += 1
    }
    
    // Append remaining elements from array2, if any
    while pointer2 < array2.count {
        result.append(array2[pointer2])
        pointer2 += 1
    }
    
    return result
}

// Example usage
let array1 = [1, 3, 5, 7]
let array2 = [2, 4, 6, 8]
let mergedArray = mergeSortedArrays(array1, array2)
print(mergedArray) // Output: [1, 2, 3, 4, 5, 6, 7, 8]

Palindrome Checking

  • Problem: Check if a string is a palindrome.
  • Approach: Use one pointer at the start and one at the end; compare characters while moving inward.
func isPalindrome(_ str: String) -> Bool {
    let characters = Array(str.lowercased().filter { $0.isLetter || $0.isNumber }) // Normalize the string
    var left = 0
    var right = characters.count - 1

    while left < right {
        if characters[left] != characters[right] {
            return false
        }
        left += 1
        right -= 1
    }
    
    return true
}

// Example usage
let testString1 = "A man, a plan, a canal: Panama"
let testString2 = "racecar"
let testString3 = "hello"

print(isPalindrome(testString1)) // Output: true
print(isPalindrome(testString2)) // Output: true
print(isPalindrome(testString3)) // Output: false

4. Removing Duplicates

  • Problem: Remove duplicates from a sorted array in place.
  • Approach: Use two pointers—one for placing unique elements and another for traversing the array.
func removeDuplicates(_ nums: inout [Int]) -> Int {
    guard nums.count > 1 else { return nums.count }

    var i = 0

    for j in 1..<nums.count {
        if nums[i] != nums[j] {
            i += 1
            nums[i] = nums[j]
        }
    }

    return i + 1
  }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:rainwatertrap

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
    func trap(_ height: [Int]) -> Int {
        var left = 0
        var right = height.count - 1
        var leftMax = height[left]
        var rightMax = height[right]
        var trappedWater = 0

        while left < right {
            if height[left] < height[right] {
                leftMax = max(leftMax, height[left])
                trappedWater += leftMax - height[left]
                left += 1
            } else {
                rightMax = max(rightMax, height[right])
                trappedWater += rightMax - height[right]
                right -= 1
            }
        }

        return trappedWater
    }

Limitations

  • Sorted Data: In some problems, the two-pointer approach only works if the data is sorted.
  • Specific to Arrays/Strings: It is less applicable to other data structures like trees or graphs.

When Not to Use

  • For problems involving dynamic structures (e.g., binary trees) or when the relationship between elements isn’t sequential.
  • When the problem explicitly requires examining all possible combinations (e.g., O(n2)O(n^2)O(n2) problems without optimizations).

Table of Contents

→ Index