Two pointers
Definitions:
This is not a data structure, but a pattern of coding interview questions. This is something passed down from languages with pointers such as C++ or Java. The idea is that I will traverse the array in both direction. This operation has use in some problems, particularly palindrome checking.
Problem
1. Valid Palindrome
Intuition
The basic problem of two pointers. The problem can be solved by many ways (strip the string then reverse, etc.), but the most straightforward way if you know two pointers is using two pointers. You will traverse the string in both directions, bypassing non-alphanumeric characters. For each alphanumeric pairs, the lowercase versions of the character must match.
Algorithm
- Initialize two pointers.
- Traverse the array from both ends.
- For both pointers, if I encounter a non-alphanumeric characters, I increment or decrement further.
- If I encounter a differing pair, return False immediately.
- At the end, return True if the right end (or the left end, depending on which pointer is moved first) has moved, else False (this is to resolve edge cases suchas
".,").
Complexity
- Time complexity: \(O(n)\): Traversin the whole array once. g
- Space complexity: \(O(1)\): Pointers are essentially integers.
Code
class Solution:
def isPalindrome(self, s: str) -> bool:
# Edge case
if len(s) < 2:
return True
# General case
leftPointer, rightPointer = 0, len(s) - 1
while leftPointer <= rightPointer:
while (leftPointer < rightPointer) and (not s[leftPointer].isalnum()):
leftPointer += 1
while (leftPointer < rightPointer) and (not s[rightPointer].isalnum()):
rightPointer -= 1
if s[leftPointer].lower() != s[rightPointer].lower():
return False
leftPointer += 1
rightPointer -= 1
return rightPointer < len(s) - 12. Two Sum II - Input Array Is Sorted
Intuition
If I set up two pointers at the start and the end, if the sum of the two numbers is larger, the only way to make it smaller is to decrement the right pointer. Likewise, the only way to make it larger is to increment the left pointer.
Algorithm
- Initialize two pointers.
- Traverse the array, decrement the right and increment the left accordingly.
- Return the required indices when found.
Complexity
Time complexity: \(O(n)\): Traversin the whole array once.
Space complexity: \(O(1)\): Pointers are essentially integers.
Code
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers)-1
while left < right:
while numbers[left] + numbers[right] > target:
right -= 1
while numbers[left] + numbers[right] < target:
left += 1
if numbers[left] + numbers[right] == target:
return [left+1, right+1]3. 3Sum
Intuition
If I sort the array, the problem can be turned into a two-pointer problem, where I fix the first value and then use two pointers to search for the remaining two values. There arises a bigger problem though: dealing with duplicates. The best approach is to deal with duplicates after I have found a satisfying triplet.
Algorithm
- Sort the array
- Nested for loop: Traverse the array. For each value, traverse the remaining array with two pointers to look for the satisfying triplets. Take care to deal with duplicates after finding a satisfying triplet.
- Return the result.
Complexity
Time complexity: \(O(n^2)\): I use a nested for loop to traverse the array.
Space complexity: \(O(1)\): If I ignore the returning array. If not, the complexity is \(O(k)\) for k the number of triplets.
Code
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) == 3:
return [nums] if sum(nums) == 0 else []
nums.sort()
cur, res = 0, []
while cur < len(nums) - 2:
# A nice little improvement: once the smallest value is positive, I
# can safely conclude the search.
if nums[cur] > 0:
break
left, right = cur + 1, len(nums) - 1
remain = - nums[cur]
while left < right:
# print('Sum:', nums[left] + nums[right])
if nums[left] + nums[right] < remain:
left += 1
elif nums[left] + nums[right] > remain:
right -= 1
elif nums[left] + nums[right] == remain:
res.append([nums[left], nums[right], nums[cur]])
# This is where I decrement and increment the pointers to deal with duplicates.
while left < len(nums)-1 and nums[left+1] == nums[left]:
left += 1
while left < len(nums)-1 and nums[right-1] == nums[right]:
right -= 1
left += 1
right -= 1
while cur < len(nums) - 2 and nums[cur+1] == nums[cur]:
cur += 1
cur += 1
return res4. Container With Most Water
Intuition
The trick is the idea of maximum so far. This appears a lot in problems where I need to iterate the array and update an extremum as I go along. The rule for moving the pointer comes from the question: How do I potentially increase the value of maximum area so far?. The answer is by moving the smaller pointer, the bottleneck in calculating the amount of water the container can hold.
An improvement on the solution is a simple check-up. Taking the width constant, the best container is the one with the maximum height. Therefore, at any moment the volume of the best container possible with the current width cannot surpass the maximum so far, I can safely break out of the for loop.
Algorithm
- Initialize: 2 pointers, maximum so far, and maximum height.
- Traverse the array with two pointers. Update the maximum height as I go along.
- Once the terminating condition is met, return the maximum so far.
Complexity
- Time complexity: \(O(n)\): I need to traverse the array once…
- Space complexity: \(O(1)\): … and store a bunch of integers.
Code
class Solution:
def maxArea(self, height: List[int]) -> int:
maxSoFar = -1
left, right = 0, len(height)-1
maxHeight = max(height)
while left < right:
minHeight = min(height[left], height[right])
maxSoFar = max(maxSoFar, (right-left)*minHeight)
if height[left] == minHeight:
left += 1
else:
right -= 1
if maxHeight*(right - left) <= maxSoFar:
break
return maxSoFar 5. Trapping Rain Water
Intuition
- Deal with the calculation one element at a time.
- Need to keep the maximum left and right heights.
- The water trapped depends on the smaller maximum height.
- Let’s say the maximum left height is smaller. The water trapped is the difference between the maximum left height and the current left height, which is >= 0.
- I need to increment the side with the smaller maximum height.
Algorithm
- Initialize pointer and maximum height for each side.
- Traverse the array. Increment the side with the smaller maximum height. Update the maximum height at that side and the water trapped so far.
- Return the result.
Complexity
- Time complexity: \(O(n)\): I need to traverse the array once…
- Space complexity: \(O(1)\): … and store a bunch of integers.
Code
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
leftMax, rightMax= height[left], height[right]
res = 0
while left < right:
if leftMax < rightMax:
left += 1
leftMax = max(leftMax, height[left])
res += leftMax - height[left]
else:
right -= 1
rightMax = max(rightMax, height[right])
res += rightMax - height[right]
return res6. Reverse Words in a String
Intuition
Let’s forget about the Python one-liner despite its performance - you can take a look at it at the end. It will not help you learn anything besides the power of reading the documentation.
Back to the problem. If I am not in Python, I will need to convert the string into a mutable array, reverse every character in the array, and then iterate and reverse every character in word, which came before a white space or at the end. The last bit can be done with two pointers.
(I can also define a function to reverse every element in a list. I don’t want to go that far so I will just use the built-in Python one.)
Algorithm
- Process the string to remove extra whitespaces.
- Convert the string to a list of character and reverse it.
- Iterate the list of character, reverse every character in a word.
- Join the characters back and return.
Complexity
Time complexity: \(O(n)\): I need to iterate the list of characters two times. Note that the two times are not nested.
Space complexity: \(O(n)\): I need to create the list of characters #### Code
import re
class Solution:
def reverseWords(self, s: str) -> str:
if len(s) < 2:
return s
sentence = re.sub(' +', ' ', s.strip())
# General one
# Convert the string into a list of characters and reverse it
sentence = list(sentence)
sentence = sentence[::-1]
# Iterate and reverse each word back
# A word exists before each space
start, end = 0, 1
while start < len(sentence):
while end < len(sentence) and sentence[end] != ' ':
end += 1
self._reverseWords(sentence, start, end-1)
start = end + 1
end += 1
return ''.join(sentence)
def _reverseWords(self, sentence, start, end):
while start <= end:
temp = sentence[start]
sentence[start] = sentence[end]
sentence[end] = temp
start += 1
end -= 1
Trivial Python solution
# Trivial Python solution
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(s.split()[::-1])7. Valid Palindrome II
Intuition
This problem builds upon Valid Palindrome I. The intuition is this: if I iterate the string with two pointers as before, at the first pair where two characters are different, the string is valid if the substring from the element right next to the right of the left character in the pair to the right character in the pair is a valid palindrome, or the substring from the left character in the pair to the element right next to the left of the right character in the pair is a valid palindrome.
Algorithm
- Iterate the string with two pointers. Check for similarity as with normal valid palindrome problem.
- If encountered dissimilarity, check valid palindrome for the two substrings mentioned above and return.
- Return result at the end.
Complexity
There are two ways to write solutions: hidden class method and nonlocal keyword.
Time complexity: \(O(n)\): I need to iterate through the input string once in both cases.
Space complexity: \(O(1)\): I only need to store pointers.
Code
This is the proper hidden class method solution.
class Solution:
def validPalindrome(self, s: str) -> bool:
start, end = 0, len(s) - 1
while start < end:
if s[start] != s[end]:
return (self._checkPalindrome(s[start+1:end+1]) or self._checkPalindrome(s[start:end]))
start += 1
end -= 1
return True
def _checkPalindrome(self, s: str) -> bool:
left, right = 0, len(s)-1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return TrueAnd this is the nested function solution.
class Solution:
def validPalindrome(self, s: str) -> bool:
def _checkPalindrome(left: int, right: int) -> bool:
# nonlocal s
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
start, end = 0, len(s) - 1
while start < end:
if s[start] != s[end]:
return (_checkPalindrome(start+1,end) or _checkPalindrome(start,end-1))
start += 1
end -= 1
return TrueThe hidden class function is preferred as it adheres to the single responsibility principle, bringing the benefits including readability, maintainability, and modularity.
8. Two Sum III - Data Structure Design
Intuition
The question asks for a data structure that supports adding elements and checking if there exists a pair of number adding up to a sum. The problem may look straight forward as if it is just refactoring of the code for two sums, but there are nuances.
The most straightforward way is to use a list to store the elements, appending it in add(), and find() is just normal Two Sum solution. However, this means that every time find() is called, a new set or dictionary has to be created. This could be saved by storing the elements inside a dictionary instead. To account for the case of the sum being double the element (say, keys currently [2, 3] but sum asks for 4), the value will be the number of elements of each key.
Algorithm
add(): Store or increment the count of that element inside a dictionary.find(): Iterate the dictionary to find the required sum.
Complexity
add():- Time complexity: \(O(1)\)
find():- Time complexity: \(O(n)\)
Code
class TwoSum:
"""
@param: nothing
@return: nothing
"""
def __init__(self):
self.numbers = {}
"""
@param number: An integer
@return: nothing
"""
def add(self, number):
# write your code here
self.numbers[number] = self.numbers.get(number, 0) + 1
"""
@param value: An integer
@return: Find if there exists any pair of numbers which sum is equal to the value.
"""
def find(self, value):
for number in self.numbers:
if value - number in self.numbers and \
(value - number != number or self.numbers[number] > 1):
return True
return False