Two pointers pattern is typically used for searching pairs in a sorted array. Given a sorted array nums (sorted in ascending order), having N integers, find if there exists any pair of elements (nums[i], nums[j]) such that their sum is equal to the target.
We start the sum of extreme values (smallest and largest) and conditionally move both pointers. We move the left pointer ‘i’ when the sum of nums[i] and nums[j] is less than the target. We do not miss any pair because the sum is already smaller than the target. The same logic applies to the right pointer j.
Problem: Pair with Target Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Using two-pointers:
class Solution:
def twoSum(self, nums: List[int], target: int):
left = 0
right = len(nums) - 1
while left <= right:
if nums[left] + nums[right] == target:
return [left, right]
right -= 1
if right == left:
left += 1
right = len(nums)-1
return [-1,-1]
We take two pointers, one representing the first element and the other representing the last element of the array, and then we add the values kept at both pointers. If their sum is smaller than the target then we shift the left pointer to right or if their sum is greater than the target then we shift the right pointer to left, in order to get closer to the sum. We keep moving the pointers until we get the sum as the target.
Time Complexity: O(N) where N is the number of elements in the input array (nums).
Space Complexity: O(1), algorithm runs in constant space.
Using HashMap:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_map = {} # to store numbers and their indices
for i, num in enumerate(nums):
if target - num in num_map:
return [num_map[target - num], i]
else:
num_map[nums[i]] = i
return [-1, -1]
How to identify?
