Given an array of integers sorted in increasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Return k after placing the final result in the first k slots of nums.
This is one of my favorite and easy array problems to start thinking in terms of two pointers to solve array problems. Why two pointers in this case?
We need a pointer that will read the elements of the array one by one. We can use another pointer to overwrite the elements in place. Also whenever we want to modify elements of an array in place – think about whether the two pointer technique can be applied!
The read pointer, let’s say r is pretty straightforward where we increment its value by one during each iteration. The only problem to solve here is to understand when to move the write w pointer.
In this problem, we are going to always compare two elements to each other to find out if it is a repeated value. This naturally leads to maintaining two variables prev and curr to keep track of the previous element to compare the current one with. Now for moving the write pointer,
Each time prev = curr, we move the read pointer r and not the write pointer w. This is so that we keep reading the elements until we find the element to overwrite with.
When prev != curr, we can now overwrite the array element, increment w and r as well as set prev to curr.
Let’s see how this works using the following diagram. Note that only r and w are variables that we use for the two pointer technique here. Prev and curr are variables to keep track of the previous and current elements.
Complexity
O(N) to traverse the array and O(1) space since we modify the array in-place.
Solution
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return 1
r, w = 1, 1
prev = nums[0]
while (r < len(nums) and w < len(nums)):
curr = nums[r]
if prev != curr:
nums[w] = curr
w += 1
prev = curr
r += 1
return w
Hope you enjoyed learning to solve this array problem with the two pointer technique.
To understand the following problem, we will be using what we learnt in the two sum problem. If you haven’t read it yet, do make sure to understand it before proceeding. Here’s the link.
Problem Statement
We have an array of integers called nums. We need to return three numbers let’s call it nums[i] = x, nums[j] = y and nums[k] = z that add up to 0. The indices of the returned numbers should all be unique ie., i != j != k
Assumptions
Solution set should not contain duplicate triplets
Empty array results in an empty set
If there are less than three numbers in the input array, return an empty set
Examples
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Thought process
The brute force way to do this would be to loop using three for loops to search for three numbers in the array that sum up to 0. But this would have an O(n3) time complexity. So we need to be slightly better than that. The next best in time is an O(n2) solution. Remember that we should not return duplicate indices.
Let’s say nums[i] + nums[j] + nums[k] = 0
Then nums[i] + nums[j] = – nums[k]
This now resembles a two sum problem where we need to look for nums[i] and nums[j] such that they add up to a target = – nums[k]
To condense the problem, what we can do is loop through the array from k = 0 to k = n-1 and for every nums[k], find two numbers nums[i] and nums[j] that add up to a target = – nums[k].
How can we avoid adding duplicate triplets to the results list? A naive solution is to add all the duplicates to the result list and in the end return the set(result) to remove duplicates. This way we still do unnecessary work on finding the same two numbers that add up to a target value -nums[k].
To avoid executing a two sum loop on duplicates, let’s reuse our solution from the two sum problem where the input array was sorted and contained duplicates. We can sort the nums list and skip searching for two sum values whenever the current nums[k] = nums[k-1]. Sorting makes it easier to club duplicate values together. For ex:
Input: [-1,0,1,2,-1,-4]
Sorted List: [-4, -1, -1, 0 ,1,2]
One of the solutions here that adds up to 0 will be [-1, 0,1]. Now if we did not skip for target = nums[2] = -1, we will again get a solution set of [-1, 0, 1] in the result.
Complexity
O(N2) time complexity and O(1) extra space
Solution
def three_sum(nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# Edge case when the array is empty
if not nums:
return []
n = len(nums)
# Another edge case when the input array does not have 3 elements
if len(nums) < 3:
return []
results = []
# Sorting helps to club duplicate values together
nums.sort()
for k in range(0, n):
# If the current num is equal to the previous value, then skip execution because we will be getting a duplicate solution set
if k > 0 and nums[k] == nums[k-1]:
continue
target = -1 * nums[k]
start = k + 1
end = n - 1
two_sum(nums, target, results, start, end)
return results
# Same as the two sum solution that we coded in the previous article
def two_sum(nums, target, results, s, e):
while s < e:
if nums[s] + nums[e] == target:
results.append([nums[s], nums[e], -target])
s += 1 # Advance the starting pointer to continue to look for other solutions
# Skip duplicate solutions in two sum
while s < e and nums[s] == nums[s-1]:
s += 1
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
We have an array of integers called nums and a target value. We need to return the indices of two numbers, say x and y that add up to target.
Assumptions
Each given input will have exactly one solution
Same element cannot be used twice
Order of indices does not matter
Examples
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] where x = 2 and y = 7
Input: nums = [4, 4], target = 8
Output: [0, 1] where x = 4 and y = 4
Thought process
What’s the brute force way to check if two numbers add up to a target value in an array?
For each value nums[i] where i = 0 initially, we traverse the list from nums[i+1] and see which two indices add up to a target value. The complexity of this will be O(n2) since we loop through the remaining n-i elements for each i. So the first optimization here would be to try and see if we can reduce the traversal to just once.
For a value x, to check if there is another value y = target – x present in the array, we need a way to do a fast lookup without going through the whole array. A dictionary is the data structure that comes to mind in that case. How to design this data structure? What will our keys and values be?
To search for a value y = target – x, we have to store the values in nums as the keys in dictionary to search for. The value for each key can then be its index in the nums array so that we can directly return the indices as our result.
Complexity
O(N) time to traverse the array once, O(1) to look up values.
O(N) space for the look up dictionary
Solution
def two_sum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
look_up = {}
for i, x in enumerate(nums):
y = target - x
# Additional condition to make sure we don't return the same index twice
if y in look_up and look_up[y] != i:
return [i, look_up[y]]
look_up[x] = i
return []
Two Sum with Sorted Array – Problem Statement
This is a slight variation of the problem above where the input array nums is sorted in ascending order and we need to find two numbers that add up to a target value.
Assumptions
Each input will have exactly one solution
Same element cannot be used twice to add up to a target
Examples
Input: nums[2, 7, 11, 15], target = 9
Output: [0, 1]
Thought Process
Again, the brute force way of solving this problem would be to traverse the array using two for loops to find two numbers that add up to a target. This way we are not using the added benefit that the array is sorted in ascending order.
This means we can apply the two pointer technique here. This works great in many scenarios especially when the input array is sorted. We can use two pointers starting at two ends of the array. If the numbers they are pointing to do not add up to our target value, there are two decisions that can be made from then on. If the sum is greater than target, this means we have to move the end pointer to the left, otherwise move the start pointer to the right. See below.
Two Pointer Technique
Complexity
O(N) time since we traverse the array at most once in case the two elements are at the center of the array.
O(1) space since no additional space is used except for a couple of variables.
Solution
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
while s < e:
if nums[s] + nums[e] == target:
return [s, e]
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return []
Two Sum with Sorted Array and Duplicates
Let’s consider the exact same problem as above but now our result can have multiple solutions that add up to the same target value but it cannot contain duplicates.
Instead of returning the indices, let’s return the numbers to make it easier for understanding.
Assumptions
Each input will have multiple solutions
Same element cannot be used twice to add up to a target
In order to return multiple solutions, once we find nums[s] + nums[e] = target, we have to advance our start s pointer and continue to look for other solutions. We can collect the solutions inside a result list. If we don’t account for duplicate solutions, this is how our code will look. For the given input above, this code will return all solutions including the duplicates [[2, 7], [2, 7], [4, 5], [4, 5]].
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
result = []
while s < e:
if nums[s] + nums[e] == target:
result.append([nums[s], nums[e]])
s += 1 # Advance the starting pointer to continue to look for other solutions
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return result
In order to avoid duplicate solutions since our array is already sorted, we can compare the current value with the previous value. If they are the same, we are about to build the exact same solution that was found in the previous run, so we can skip it. For example, in [2, 2, 4, 4, 5, 7, 7, 9, 11, 15], when i = 1, nums[i] = 2 = nums[i-1] = 2, which will again yield [2, 7] as a duplicate solution, so let’s skip it and advance the starting s pointer. Then our solution can be slightly modified as shown below.
Complexity
O(N) time
O(1) space since we don’t usually include result as additional space
Solution
def two_sum(nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
s = 0
e = len(nums) - 1
result = []
while s < e:
if nums[s] + nums[e] == target:
result.append([nums[s], nums[e]])
s += 1 # Advance the starting pointer to continue to look for other solutions
# Skip duplicate solutions
while s < e and nums[s] == nums[s-1]:
s += 1
elif nums[s] + nums[e] < target:
s += 1
else:
e -= 1
return result
Given an array containing integers 0, 1 and 2 representing the colors red, white and blue, sort them in-place so that the same numbers are adjacent, with the order being 0, 1 and 2.
Example:
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Solution #1:
There are only three different values in the array and those are 0, 1 and 2. We have to return an array arranged in an order with all the numbers with same values clubbed together. A simple approach is to count the number of 0s, 1s and 2s in the given array and overwrite the given array with these three values according to the counts. In the given array,
count(0) = 2
count(1) = 2
count(2) = 2
So let’s say we store these values in an array counts = [[0, 2], [1, 2], [2, 2]]. We can then iterate through this array and overwrite the given input array with 0, 1 and 2 according to their respective counts.
Time Complexity: O(N) to count the values and another O(N) to overwrite the input array, so the overall time complexity will be O(N).
Space Complexity: O(C) since we use constant space to store the values 0, 1, 2 and their counts.
Solution #2:
Notice that we have to shuffle around only three different values. This means that we can use a few pointers to keep track of some of the values.
Dutch National Flag Problem
Let’s use three different pointers as follows.
zero_ptr to keep track of the leftmost index where we can overwrite with a 0.
two_ptr to keep track of the rightmost index where we can overwrite with a 2.
curr pointer to keep track of the current index we are looking at.
Algorithm to get the Dutch National Flag pattern:
When curr points to a 0, we swap it with the element at zero_ptr. After swapping we move curr and zero_ptr one step forward.
When curr points to a 2, we swap it with the element at two_ptr. We then decrement the value of two_ptr. Note that we should not move curr at this step because we may have just swapped a 2 with another 2 and we should re-process it in the next step.
If curr points to a 1, we just move curr to the next element.
The above loop stops when curr > two_ptr. This indicates that we have placed all the values in their appropriate slots. If this is too confusing, look at the picture below to see how the algorithm works step by step.
Step by step algorithm
Time Complexity: O(N)
Space Complexity: O(1) for in-place re-arrangement
Given two strings s and t, check if s is a subsequence of t. A subsequence can be formed by deleting some characters in a string without changing the order of the other characters.
Input: s = “abc”, t = “ahbgdc“ Output: true
The simplest way to solve this problem is to use the two-pointer technique where we designate two different pointers to traverse s and t simultaneously. If the characters match, then we move on to check the next character of s against t, otherwise we move on to the next character in t. By the time we are done, there should be no characters left in s to be compared and therefore s must be a substring of t.
Time Complexity: The loop ends when we run out of characters to compare in either s or t. The worst case happens when we run through all the characters in t, so the time complexity is O(T).
Space Complexity: O(1)
Code:
def isSubsequence(self, s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
Testing:
For this problem, the following test cases will cover various situations.
Empty s
Empty t
s string length greater than t
A few other random test cases
I find all other approaches to be kind of an overkill, so I hope you enjoyed this simple approach. Have a great day!
That Girl Coder 