1 month

Coding Patterns: Two Pointers Technique




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                                     

LeetCode 1 - Two Sum [easy]                                                                             

 

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 ComplexityO(N) where N is the number of elements in the input array (nums).

Space ComplexityO(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]                                                              

  • Time Complexity: O(n)                                        
  • Space Complexity: O(n)                                                         

How to identify?                                            

  • The problem involve sorted arrays (or Linked Lists), a set of pair elements, or a triplet or even a subarray.
  • There is a target value to match or duplicates to be removed.

 

 

 

Similar LeetCode Problems


Responses(0)







Related