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.
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
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.
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
0 Comments