Ticker

6/recent/ticker-posts

Ad Code

Responsive Advertisement

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.
two pointer

two pointer

two pointer


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 
 

codeforce problems 
 
 
resources
 
join my telegram channel
 













Post a Comment

0 Comments