Two-Pointer Technique Explained

Exploring the Two-Pointer Technique for Solving Array and String Problems

Overview

In this post, we will explore the Two-Pointer technique to solve array or string-related problems. This powerful method helps to reduce time and space complexity, making it an invaluable tool in competitive programming.

Definition

The two-pointer technique is a method used to solve array or string problems by using two variables (pointers) to track values. It is designed to optimize time and space complexity, making problem-solving more efficient.

Problem Patterns

1. Finding Two Numbers That Sum to a Target

    Input: A sorted array of integers and a target number
    Output: Indices of two numbers from the array that sum up to the target number
    Approach: Place the first pointer at the beginning of the array and the second pointer at the end. Adjust pointers based on the sum compared to the target.


def twoSum(nums, target):
    left = 0
    right = len(nums) - 1
    cur_sum = 0
    while nums[left] + nums[right] != target:
        cur_sum = nums[left] + nums[right]
        if cur_sum < target:
            left += 1
        else:
            right -= 1
    return [left+1, right+1]

2.Checking if an Array is Sorted

    Input: Array of integers
    Output: True if the array is sorted in non-decreasing order, False otherwise
   Approach: Use two parallel pointers to compare adjacent elements.

Implementation


def isSorted(nums):
    left = 0
    right = 1
    size = len(nums)
    while right < size:
      if nums[left] > nums[right]:
          return False
      left += 1
      right += 1
	return True

3. Merging Two Sorted Arrays

    Input: Two sorted arrays in non-decreasing order
    Output: A single sorted array
    Approach: Place one pointer in each array, compare their values, and add the smaller value to the merged array. Move the pointer with the smaller value to the next element.

Implementation

def mergeLists(list1, list2):
    merged = []
    first, second = 0, 0
    while first < len(list1) and second < len(list2):
        if list1[first] < list2[second]:
            merged.append(list1[first])
            first += 1
        else:
            merged.append(list2[second])
            second += 1
    merged.extend(list1[first:])
    merged.extend(list2[second:])
    return merged

4. Grouping Non-Zero Elements

    Input: An array of integers
    Output: The array modified in-place, with all non-zero numbers at the beginning while maintaining their relative order
   Approach: Use two pointers (seeker and placeholder).The placeholder   pointer finds the next spot for a non-zero element, while the seeker finds non-zero elements to place.

Implementation


  def moveNonZeroes(nums):
      holder = 0
      seeker = 0
      while seeker < len(nums):
      if nums[seeker] != 0 and nums[holder] == 0:
          nums[seeker], nums[holder] = nums[holder], nums[seeker]
      if nums[holder] != 0:
          holder += 1
      seeker += 1

Common Pitfalls

1. Index Out of Range: This error occurs if edge cases are not handled properly.
2. Pointer Conditions:
    When to move the pointers
    When to stop the loop
    How to handle pointer values

Practice Problems

leetcode problems

27. Remove Element

344. Reverse String

167. Two Sum II - Input Array Is Sorted

881. Boats to Save People

codeforce problems