Technical Interviews: Everything You Need to Master the Two Pointers Technique
Every two pointers problem (arrays) follows one of these patterns…
--
Your resume caught the eye of the hiring team, you passed the phone screen, and now you’re preparing for the technical interview of your dream firm.
The stakes are high and your coffee is strong.
As you set the timer, the first challenge appears on the screen, ready to edge you closer to that coveted job offer.
But the smile instantly drops off your face when you start to read…
Q. Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
This article is part of a larger series on Technical Interview patterns. In the previous post, I introduced the Sliding Window Technique common in array problems and how to use it. In this article, I will focus on the infamous Two Pointers Technique.
The Two Pointers Technique
The Two Pointers technique involves using two pointers that either move towards each other or in the same direction to iterate through the data, typically a list or array.
What’s its Advantage?
- Optimises solutions from O(n²) time complexity (naïve brute force approach) to O(n) time complexity.
- Reduces space complexity as no additional data structures are needed.
- Efficiently solves problems without the need for nested loops.
How Can You Recognise it?
- Find Pairs: Find a pair that sums up to a target value.
- Find Optimal Pairs: Find pairs that optimise a condition x, such as the closest sum to a target.
- In-Place Operations: Reverse an array without using additional space.
- Palindrome Checks: Determine whether a string is a palindrome.
Solved Examples in Python — Easy Level
Q1. Given a sorted array arr = [1, 3, 4, 7, 10] and a number 15, find the pair in the array whose sum is closest to 15.
def findClosestPairToSum(arr, x):
# Add your code hereStart by visualising the ‘left’ and ‘right’ pointers in this example. How can you determine when to move one or the other?
One efficient way to move the pointers is by using a while loop with the condition ‘left < right’. This ensures that each element is considered only once and the pointers don’t cross each other.
def findClosestPairToSum(arr, x):
"""
Find the pair of numbers in a sorted array that
has the sum closest to a given sum.
Parameters:
arr (array of int): The sorted array to search
within.
x (int): The target sum to approach.
Returns:
tuple: A pair of integers from the array that
has the closest sum to x.
"""
left, right = 0, len(arr) - 1
min_diff = float('inf')
closest_pair = (None, None)
# Loop until the two pointers meet
while left < right:
cur_sum = arr[left] + arr[right]
diff = abs(cur_sum - x)
# If the difference is smaller than the
# minimum difference, update the closest
# pair
if diff < min_diff:
min_diff = diff
closest_pair = (arr[left], arr[right])
# If the current sum is less than the target
# sum, move 'left' pointer right to increase
# the sum
if cur_sum < x:
left += 1
# If the current sum is greater than the target
# sum, move 'right' pointer left to decrease
# the sum
else:
right -= 1
return closest_pairQ2. Given a string s = “raceacar”, return true if it is a palindrome and false otherwise, ignoring spaces.
def isPalindrome(s):
# Add your code here
When checking for palindromes, both pointers need to move in opposite directions at each step.
def isPalindrome(s):
"""
Check if a given string is a palindrome, ignoring
spaces.
Parameters:
s (str): The string to check.
Returns:
bool: True if s is a palindrome, False otherwise.
"""
# Remove spaces
s = ''.join(s.split()).lower()
left, right = 0, len(s) - 1
# Loop until the two pointers meet
while left < right:
# If both characters don't match, return False
if s[left] != s[right]:
return False
# Move the pointers towards the center
left += 1
right -= 1
# If all characters match, return True
return TrueMedium Level
Q3. Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, and j != i, and j != k, and nums[i] + nums[j] + nums[k] == 0.
def getNetZeroTriplets(nums):
# Add your code hereIn a triplet-sum problem, we use one fixed pointer and two moving pointers within a single loop. Here’s a breakdown of the approach:
- The leftmost pointer, ‘i’, iterates from 0 to len(nums) — 3
- For each position of ‘i’, the ‘left’ pointer is set to ‘i + 1’ and moves to the end of the array but never crosses the ‘right’ pointer
- The ‘right’ pointer is set to len(nums) — 1 and moves to the start of the array but never crosses the ‘left’ pointer
- It is always the case that ‘i’ < ‘left’ < ‘right’
Sorting an array is a strategic first step when finding sums because it allows us to make simpler adjustments. If we want to increase the sum, we can move the ‘left’ pointer to the right and if we want to decrease it, we can move the ‘right’ pointer to the left. This makes search more efficient.
def getNetZeroTriplets(nums):
"""
Find all unique triplets in the array that
give the net sum of zero.
Parameters:
nums (array of int): The array of integers.
Returns:
array of arrays: An array of all unique triplets
that sum up to zero.
"""
# Sort the array to simplify finding
nums.sort()
triplets = []
for i in range(len(nums) - 2):
# Skip duplicate elements to avoid duplicate
# triplets
if i > 0 and nums[i] == nums[i - 1]:
continue
# Initialise two pointers
left, right = i + 1, len(nums) - 1
while left < right:
cur_sum = nums[i] + nums[left] + nums[right]
# If sum is zero, add triplet to array
if cur_sum == 0:
triplets.append([nums[i], nums[left], nums[right]])
# Skip duplicate elements
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
# Move pointers after finding valid triplet
left += 1
right -= 1
# If sum is less than zero, move 'left' pointer
# to the right to increase sum
elif cur_sum < 0:
left += 1
# If sum is greater than zero, move 'right' pointer
# to the left to decrease sum
else:
right -= 1
return triplets
Q4. You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. You may not slant the container.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
def getMaxAmount(height):
# add your code hereThe trick here is to start with the widest possible container and then move the pointers inward, always moving the pointer at the shorter line because this is the only way to find a container with more water.
In other words, when we’re trying to optimise areas with linear constraints, starting with the maximum width and then moving inward allows us to explore all possible areas without missing the optimal solution.
def getMaxAmount(height):
"""
Find the maximum amount of water that can be
contained.
Parameters:
height (array of int): The heights of the lines.
Returns:
int: The maximum area of water that can be
contained.
"""
left, right = 0, len(height) - 1
max_amount = 0
# Loop until the two pointers meet
while left < right:
# Calculate the width of the container
width = right - left
# Calculate the area of water contained and
# update max_amount if it's greater
cur_amount = width * min(height[left], height[right])
max_amount = max(max_amount, cur_amount)
# Move the pointer at the shorter line inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_amountIt’s your turn now! Test your understanding with the Hard Level question at the start of this article and share your solution in the comments below. It’s a real coding question presented to candidates in Google, Microsoft and Amazon interviews.
Thanks for reading this, remember to clap up to 50 times 👏🏻 , highlight 🔍 and share your feedback 💬!
Sources:
