Learn Optimizing the Coding Problems using Two pointer Technique

Hello, and welcome to a wonderful series of competitive programming and data structures where we are preparing for coding interviews and contests. If you are following the series then I must say that you have the initial spark to solve the questions and gain a little confidence over coding that I can think and implement a code. If you are following the series and keep on solving the questions we would also request you to with this spark try to explore more problems on the corresponding topics on any competitive sites. In this tutorial, we will take the series forward and start with Two Pointer Technique which is very simple, important, and help in optimizing the brute force approaches in linear time in many problems.

popular coding problems on two pointer technique for interviews


What is Two Pointer Technique?

Two Pointer is an algorithmic technique which the name suggests we maintain two pointers to keep track of array or string indices. We prove that based on the certain condition the pointer is going to move forward or backward, and by how much to reach the desired solution. In this way, we efficiently solve the problems and bring out the brute-force square complexity to linear time complexity.

Two Types of Two Pointer Technique

1) Equi-Directional ~ In this we have a two-pointer that initially points out at the same index (start or end) and we have a fixed or variable sliding window. This is also known as the sliding window algorithm that we will study in our next article.

2) Opposite-Directional ~ In this we have two pointers that point at different indexes (start and end) and based on requirements and conditions we move both pointers towards each other and they meet somewhere in between to meet the desired solution. This is our point of study at the current point and we will pick very simple problems and learn how to optimize them using two pointers.

How to Identify the problems based on Two Pointers?

This is one of the most asked, and confusing questions in every programmer's mind when he/she starts studying any new topic. And it is important also to figure out after studying the vast amount of topics how we would figure out which technique to use or to which technique the question belongs.

  • Whenever you are asked to find pairs in an array in form of 2 pairs, triplets the two-pointer technique is an optimal solution to use.
  • When we are asked to find such point of pair between which area is the maximum or certain condition then a two-pointer is used.

πŸ‘‰ I hope that the theoretical part is clear to you. Now let us start solving some questions and if something is missing it will automatically get resolved while solving problems.

1) Solve the Two Sums problem using the two-pointer technique

Given a sorted array of integers, and a target K. your task is to find a pair in an array that sums to the required target.

Example

First Line contains a single integer N denoting the size of an array. The second line contains the array of elements in sorted order. And the third line contains a number that is a required target.


Two pointer approach to finding pairs that sum to K.

We know that the array is sorted so what we can do is place two-pointer at two different ends of an array (start and end). Now we start iterating till the start is less than the end and sum both the element present at both pointers. Now we have three cases here.

  • First, if the current sum is equal to the target then terminate the loop and we got our answer.
  • The second is if the current sum is smaller than a target. In this case, we have to increase the current sum so we move to the start pointer ahead because the array is sorted so as we move forward then only we will find a greater element to increase the sum.
  • The third is current sum is greater than the target. So we decrease the end pointer to decrease the current sum.

πŸ’» Code ~ Now we can easily implement the code in a few lines.

def TwoSums(arr, target):
    start = 0
    end = len(arr)-1
    pairs = []
    
    while start < end:
        curr_sum = arr[start] + arr[end]
        
        if curr_sum == target:
            pairs.extend([arr[start], arr[end]])
            break
            
        elif curr_sum < target:
            start += 1
            
        else:
            end -= 1
            
    return pairs
    
arr = [1,2,3,4,6]
target = 6
pair = TwoSums(arr, target)
if pair:
    print(pair)
else:
    print("Not Found")

✌ Now most of you would have used the brute-force approach in O(N^2) complexity to solve this problem and using the two-pointer technique we have easily optimized the solution to linear time.

2) Find Triplet where Sum of Two elements is equal to third

One more similar problem statement where given an array of N integers. You need to find a valid triplet. A triplet is said to be valid if there exist three indices (i, j, k) in array such that array[i] + array[j] = array[k] or array[j] + array[k] = array[i] or array[i] + array[k] = array[j].

Example

  • The first line contains T denoting the number of test cases.
  • the first line of each test case contains the size of the array
  • the second line of the test case contains array elements.


πŸ‘‰ Take a reference to the above question and try to implement this question.

How to find a Triplet in an array using the Two pointer technique

We have to find three numbers among which the sum of two numbers is equal to the third number, and using the two pointer approach we can easily find pair (two numbers) that is equal to the target so using this as a reference we can take the first element of an array as target and in remaining array try to find the pair that sum to find the first number.

  • First, we sort the array in ascending order.
  • Then we iterate through an array and take the loop element as a target.
  • And in the remaining array elements, we apply the two-pointer technique to find pairs that sum to the target. And if we found a pair then this is a triplet.

This is the way we can easily solve the question.

πŸ’» Code ~ two pointer technique code is already with you and now you must implement the remaining discussed approach.

def TwoSums(arr, target):
    start = 0
    end = len(arr)-1
    pair = []
    
    while start < end:
        curr_sum = arr[start] + arr[end]
        
        if curr_sum == target:
            pair.extend([arr[start], arr[end]])
            break
            
        elif curr_sum < target:
            start += 1
            
        else:
            end -= 1
            
    return pair
    
def findTriplet(arr,n):
	pairs = []
	arr.sort()
	for i in range(n):
	    temp = arr[:i]+arr[i+1:]
	    pairs = TwoSums(temp, arr[i])
	    if pairs:
	        #also add the target element to complete triplet
	        pairs.append(arr[i])
	        break
	        
	return pairs
    
arr = [10, 5, 5, 6, 2]
n = len(arr)
triplet = findTriplet(arr, n)
if triplet:
    print(True)
else:
    print(False)

3) Find All Triplets with Given Sum in array

Given an array of N integers. your task is to find all the distinct valid triplets in an array that sums to a given target value.

πŸ”° NOTE -

  • The elements in an array need not be distinct (There may be duplicate elements present in an array)
  • You can return the list of values in any order. For example if a valid triplet is {2, 3, -1} then {-1, 2, 3} or {3, -1, 2}, etc all are the valid combinations but do not include it multiple times (distinct triplet). Also if there is more than one triplet in an array then you can return them in any order.
  • If no valid triplet is found, return an empty list and the output will be -1.

Example

  • The first line of the test case contains N denoting the size of the array.
  • Second-line contains a space-separated array of elements.
  • The third line contains the target value as K.


Two Pointer Approach to find all valid triplets that sum to K

Here, you are required to think about it a bit by taking a reference to the above 2 questions and find the answer of how we can fit two pointer approach to a particular problem.

  • The idea is like array[i] + array[j] = target - array[k]. So what we can do is loop over the array and find a difference between the target and current array element. Now taking this difference as a target try to find pair using a two-pointer that sums the difference. Add the triplet to the final result.
  • Create an empty result list to store all the valid triplets.
  • Loop through the array and find a difference between the target and current element and then find pair that sums to the difference.
  • Add the triplet to the result and check any same element not present in the array to avoid any duplicates in triplets.

πŸ’» CODE ~ Let us code the algorithm using python

def findTriplets(arr, n, k):
    ans = list()
    # Sorting the arraylist.
    arr = sorted(arr)

    i = 0
    while i < n:
        target = k-arr[i]
        front, back = i + 1, n - 1
        while front < back:
            sum = arr[front] + arr[back]
            # Finding answer which starts from arr[i].
            if sum < target:
                front += 1

            elif sum > target:
                back -= 1

            else:
                x, y = arr[front], arr[back]
                ans.append([arr[i], x, y])
            #Incrementing front pointer until we reach different number.
                while front < back and arr[front] == x:
                    front += 1
            # Decrementing last pointer until we reach different number.
                while front < back and arr[back] == y:
                    back -= 1
                    
	# Ensuring that we don't encounter duplicate values for arr[i].
        while i + 1 < n and arr[i] == arr[i + 1]:
            i += 1

        i += 1
    return ans


t = int(input())
while t > 0:
    n = int(input())
    arr = list(map(int, input().split()))
    k = int(input())
    ans = findTriplets(arr, n, k)
    if len(ans) > 0:
        for triplet in ans:
            print(*triplet)
    else:
        print(-1)
        
    t = t-1

4) Find the Largest Mountain subarray

Given an array of N integers where each number denotes the height of the mountain. Your task is to find the length of the longest subarray that forms the shape of a mountain.

πŸ‘‰ The resultant subarray is known as the mountain subarray where elements are in ascending order at the initial level until the peak element is reached and after that, all other elements of the subarray will be in decreasing order.πŸ’₯

Example

  • The first line of the test case contains a single integer N denoting the size of an array.
  • The second line contains space-separated array elements.


Two Pointer approach to finding maximum length subarray

At this point, I can request you to before reading an approach give a try to implement something on yourself and try to think of like how we can use a two-pointer to find a solution. Let us discuss the approach and all the possible cases in an algorithmic way.

  1. If the length of an array is less than 3 then return 0. Because mountains cannot be formed, we need the array to first strictly increase and then strictly decrease.
  2. Else we keep track of two pointers say peak and valley. Both are boolean pointers and initially marked as False. Peak denotes that we found a peak element before which all elements are in ascending order. and valley denotes after the peak element there are elements in decreasing order.
  3. Iterate through an array and check till when peak element is reached. After the peak finds the end of the valley element. If found then change them to True and update the mountain length.

πŸ‘² I hope that approach is pretty clear to you. If not then observe the below-solved example and then each doubt will get resolved. And I request you also solve the sample input using pen, and paper to gain a better understanding of the problem and approach. πŸ‘Œ

πŸ’» Code ~ Now we are ready to implement the algorithm.

def longestMountain(arr, n):
    if n < 3:
        return 0
        
    res = 0 #to store maximum length
    i = 0
    
    while i < n-1:
        #initialize two pointer as peak and valley
        peak = False
        valley = False
    
        if arr[i] < arr[i+1]:
            start = i #keep start pointer to find len of subarray
            
            #find peak element
            while i < n-1 and arr[i] < arr[i+1]:
                i += 1
                peak = True  #we find greater then prev
                
            #find valley
            while i < n-1 and arr[i] > arr[i+1]:
                i += 1
                valley = True
                
            #If both are true means we found a mountain
            if peak == True and valley == True:
                res = max(res, i-start+1)
                
        else:
            i += 1
            
    return res
    
arr = [1,3,1,4,3,1]
n = len(arr)
print(longestMountain(arr, n))

5) Find the Container with the Most water

Given an array of N non-negative integers where each number in a sequence represents a height of a line drawn at index i. Your task is to find two lines that together on the x-axis form a container, such that the container contains maximum water.

NOTE -

πŸ‘‰ You can not slant the container means the height of the water is equal to the minimum height of two lines that define the container.

πŸ‘‰ Area is defined as a minimum of both elements into the distance between them.

Example

  • The first line contains an integer T denoting the number of test cases. The next 2*T lines represent T test cases.
  • The first line of the test case contains the size of the array (Number of elements in sequence)
  • The second line contains a space-separated array of elements


Two Pointer approach to finding a maximum area in an array

After solving the questions of different types using Two pointers I hope that you can think over the approach to this problem and also implement it.

😏 The basic idea is to use two pointers one is placed at the start of the array and one is placed at end of an array. Find the area between them as per the given formula. Now move that pointer in its respective direction which is minimum because we have taken its maximum devotee length what it can give and if ahead we found greater than the minimum element then also the area will be less. So move the minimum pointer and update the maximum area. πŸ‘Š

πŸ’» Code ~ Let us implement the algorithm to find the maximum area.

def maxArea(height):
    n = len(height)
    start = 0
    end = n-1
    area = 0
    
    while start < end:
        #minimum height between both element
        min_h = min(height[start], height[end])
        #calculate area
        area = max(area, (min_h * (end-start)))
        
        if height[start] < height[end]:
            start += 1
            
        else:
            end -= 1
            
    return area
    
arr = [12, 4, 6, 8, 1]
print(maxArea(arr))

End Notes

These are the top-level questions that are mostly asked in interviews and the candidate keeps applying the brute-force method to solve them. I hope that the article will help you build more optimized codes with the Two pointer technique and you can identify the problem where and how we can use the two-pointer approach to solve problems in efficient time complexity.

πŸ‘‰In this article we have learned two pointer technique that is used from the same end and both pointers move in the same direction. The next article will cover the sliding window technique where both pointers will move in opposite directions. So keep reading and solve as many questions as you can.

Thank You for your time! 😊

Post a Comment

If you have any doubt or suggestions then, please let me know.

Previous Post Next Post