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.
Today let us learn about monotonic stacks and their usage.
A monotonic stack is one in which the elements of the stack are always increasing or decreasing. This ensures that the stack is always sorted in some order. Some interesting applications of monotonic stacks are to
Find the next smaller or greater element in an array
Find the previous smaller or greater element in an array
Find the minimum or maximum element in a sliding window etc.
Let’s take a look at an example problem below.
Find the next greater element in an array
The next greater of an element X in an array is the first greater element to the right side of X. For example:
[1, 2, 3, 4]
Next greater element (1) => 2
Next greater element (2) => 3
Next greater element (3) => 4
In this problem, we can use a monotonic stack to push elements into and keep popping the elements as long as the top most element has a value smaller than the current element whose next greater element we want to find. That’s a mouthful, so let’s look at an example!
We have the following array.
Input: [1, 3, 4, 2, 5] and here’s an array of the next first greater elements to the right of each element in the array.
Output: [3, 4, 5, 5, -1] (-1 when no next greater element exists)
Algorithm:
Iterate the given array from i = 0 to i = N – 1.
Push the element array[i] in the monotonic stack if either the stack is empty or the top of stack > array[i]. We are thereby building a monotonic stack decreasing from the bottom to top.
In this process, we have to pop the elements in stack if they are lesser than array[i] which is the first greater element found to the right of the popped one.
Look at how the stack and the mapping changes as we iterate the array in the following diagram.
Finally push 5.
Time Complexity: O(N) where N is the size of the array that is iterated. This is because we iterate the array only once and each element is pushed and popped exactly once.
Space Complexity: O(N) since the mapping and the stack will contain at most N elements.
Code:
In the following code nums1 contains the elements whose next greater element should be found in nums2.
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
num_to_next_greater_mapping = collections.defaultdict(lambda: -1)
mono_stack = []
for index, val in enumerate(nums2):
if mono_stack and val > mono_stack[-1]:
while mono_stack and mono_stack[-1] < val:
num_to_next_greater_mapping[mono_stack[-1]] = val
mono_stack.pop(-1)
mono_stack.append(val)
results = []
for n in nums1:
results.append(num_to_next_greater_mapping[n])
return results
Stay tuned for more of these problems in this space.
This is a follow up on the previous post where we solved Regular Expression Matching using simple recursion. In this post we will solve the same problem using Dynamic Programming. Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems where the optimal solution to the problem is obtained by solving for optimal solutions to the subproblems.
Problem Statement
Given an input string and a regex pattern, implement regular expression matching with support for ‘.’ and ‘*’.
‘.’ matches any single character
‘*’ matches zero or more of the preceding element (the char before *)
Examples
s = ‘aa’, p = ‘ab’ Not a match
s= ‘bbbbb’, p = ‘b*’ Match because ‘*’ matches zero or more of the preceding element b
s= ‘fljflf’, p = ‘.*’ Match because we want to match zero or more of the preceding element which is any character in this case
s = ‘oop’, p = ‘r*o*p’ Match because r is present 0 times, o is present twice and p is a direct match
Thought Process
In any dynamic programming problem we should first define the subproblem. Let’s consider an example where s = ‘bbbbb’ and p = ‘b*b*c*’. If we use the recursive solution to solve the problem, the recursion tree will branch out as shown below. Although not all the branches are represented in the diagram, we can clearly see that some of the subproblems are repeatedly solved over and over again and this is an expensive computation. One way to avoid solving repeated problems is to remember the results of a computation using a technique called Memoization.
Each subproblem call will resemble isRegexMatch(s[i:], pattern[j:]) where i and j are indexes used to slice the string and the pattern respectively. So we do not have to memoize the entire substring and substring of the pattern. So instead of
mem[(s[i:], pattern[j:])) = result
We will use only i and j to index the result in mem such as
mem[(i, j)] = result
We will therefore use the exact same solution from our previous solution except this time we will store the results for future lookup.
Complexity
For a string of length S and pattern of length P, we call dp(i, j) at the worst case for all the possible subproblems for i = 0 to S and j = 0 to P. So the time complexity will be O(SP).
Same for space complexity since we are caching the results of the subproblems O(SP).
Solution
def isRegexMatch(s, pattern):
mem = {}
def dp(i, j):
if (i, j) not in mem:
if j == len(pattern): # Check if pattern is empty, if so string s should also be empty
mem[(i,j)] = i == len(s)
else:
# Check the first character match in s and pattern
# String should not be empty
# The first characters exactly match (Or)
# pattern's first char contains "." to match any char in s
is_first_char_match = len(s) > i and (s[i] == pattern[j] or pattern[j] == ".")
# When '*' is present in the second char of pattern
if j < len(pattern) - 1 and pattern[j+1] == "*":
mem[(i,j)] = dp(i, j+2) or (is_first_char_match and dp(i+1, j))
else:
# Continue checking the remaining characters using recursion
mem[(i,j)] = is_first_char_match and dp(i+1, j+1)
return mem[(i,j)]
return dp(0, 0)
Hope you enjoyed solving this dynamic programming example using Memoization technique. See you in the next post!
Given an input string and a regex pattern, implement regular expression matching with support for ‘.’ and ‘*’.
‘.’ matches any single character
‘*’ matches zero or more of the preceding element (the char before *)
Examples
s = ‘aa’, p = ‘ab’ Not a match
s= ‘bbbbb’, p = ‘b*’ Match because ‘*’ matches zero or more of the preceding element b
s= ‘fljflf’, p = ‘.*’ Match because we want to match zero or more of the preceding element which is any character in this case
s = ‘oop’, p = ‘r*o*p’ Match because r is present 0 times, o is present twice and p is a direct match
Thought Process
Let’s approach this problem step by step.
Case 1: The simplest case would be when the given string and the pattern do not contain any ‘.’ or ‘*’ characters but only alphabets.
s = 'aa' and p = 'ab'
In this case we would check the string and the pattern from left to right to see if each character in the string matches the characters in the pattern.
a = a matched so far
b != a Match failed so return False
Case 2: When no ‘*’ characters are present but only ‘.’. In this case ‘.’ can match any single character. So we check for that condition and continue to check the remaining characters in the given string and the pattern using recursion.
def isRegexMatch(s, pattern):
# If pattern is empty, as long as string is also empty => true
# If pattern is empty but string is not empty => return false
if not pattern:
return not s
# Check the first character match in s and pattern
# String should not be empty
# The first characters exactly match (Or)
# pattern's first char contains "." to match any char in s
is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
# Continue checking the remaining characters using recursion
return is_first_char_match and isRegexMatch(s[1:], pattern[1:])
Case 3: When the regex pattern contains both ‘.’ and ‘*’ characters, things get a little complicated.
Note that the pattern will never begin with ‘*’ because it denotes that a preceding character can be present 0 or more times. So it will ALWAYS be present only as the second character when that part of the pattern is being processed after a recursive call, For example: a*, .*
So we can have a condition that evaluates this logic as shown below.
if len(pattern) >= 2 and pattern[1] == "*"
If the above condition holds true, then we check regex match differently due to the presence of ‘*’. Let’s think about how we can do that. There are two valid scenarios that are allowed here.
Scenario 1: s = "aaaa", pattern = "c*a*"
In this case len(pattern) = 4which is >= 2 and pattern[1] = ‘*‘. We see that c is not present in the string s but it can occur zero 0 or more times. In this case we can ignore checking the first two characters of the pattern and continue the recursion as shown below.
In this case len(pattern) = 2 which is >= 2 and pattern[1] = ‘*‘. s contains ‘a’ which is a direct match with the first character in the pattern. So we check for first character match and continue recursion on the rest of the string.
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aaa", "a*")
Note that we pass the full pattern string to the recursion call here because ‘*’ can match zero or more characters of ‘a’. So we want to check the string for that as well. The following recursive calls will hold true.
isRegexMatch("aaa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("aa", "a*")
isRegexMatch("aa", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("a", "a*")
isRegexMatch("a", "a*") =>
is_first_char_match and isRegexMatch(s[1:], pattern) => a = a and isRegexMatch("", "a*")
isRegexMatch("", "a*") =>
isRegexMatch(s, pattern[2:]) => isRegexMatch("", "") so final result will be true.
if len(pattern) >= 2 and pattern[1] == "*":
return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))
Complexity
For a given string of length S and pattern P, we make recursive calls using indexes s[i:] and pattern[2j:] (When ‘*’ is present). The recursive tree can go to a depth of (S+P/2) which will have 2h leaf nodes where h = (S+P/2), so 2(S+P/2) leaf nodes. This means the recursion will branch into 2(S+P/2) sub-problems.
If we pass the entire string and pattern at the worst case, the complexity of solving a sub-problem will be O(S+P). So the time complexity will roughly be
O((S+P) * 2(S+P/2))
To read more about the complexity calculation for this problem, here’s a detailed article.
Putting it all together.
Solution
def isRegexMatch(s, pattern):
# If pattern is empty, as long as string is also empty => true
# If pattern is empty but string is not empty => return false
if not pattern:
return not s
# Check the first character match in s and pattern
# String should not be empty
# The first characters exactly match (Or)
# pattern's first char contains "." to match any char in s
is_first_char_match = len(s) > 0 and (s[0] == pattern[0] or pattern[0] == ".")
# When '*' is present in the second char of pattern
if len(pattern) >= 2 and pattern[1] == "*":
return isRegexMatch(s, pattern[2:]) or (is_first_char_match and isRegexMatch(s[1:], pattern))
else:
# Continue checking the remaining characters using recursion
return is_first_char_match and isRegexMatch(s[1:], pattern[1:])
Hope you enjoyed solving the regular expression problem. In the next post, we will look at how to improve upon this solution using Dynamic Programming!
Given a string s, we have to return the longest palindromic substring.
Note: Palindromes are words or phrases that read the same backward and forward, letter for letter, number for number, or word for word. Source: Grammarly
Examples
Input: s = “babad”
Output: “bab”
Input: s = “dfgggggkl”
Output: “ggggg”
Input s = “a”
Output: “a”
Thought Process
In any given string, to find the longest palindromic substring, the brute force approach would be to consider every possible substring and then have a helper function to check if it is a palindrome. This results in a cubic complexity for a string of length N. Why O(N3) complexity? To check if a string is a palindrome or not, we will have to traverse through the whole substring. At the worst case, this will be the entire string s. This takes O(N). We will then have to use two for loops to check each possible substring which will be O(N2). Now let’s think of an efficient way of doing this.
There are two types of palindromes.
Palindromes with an even number of letters. Examples: “aa”, “abba”, “cdeedc”
Palindromes with an odd number of letters. Examples: “a”, “aba”, “cdedc”
The speciality of palindromes is that they expand from a central point and mirror each other on the left and right. How to define what is the center? In an even length palindrome, the center is in between two letters. In “abba”, the center is in between the two “b”s. In “aba”, which is an odd length palindrome, the center is “b”.
How many possible centers are there in a given palindrome?
Example 1: “aba”
The possible centers to consider are a, a <-> b, b, b <-> a, a ie., 5 centers
Example 2: “abba”
The possible centers are a, a <-> b, b, b <-> b, b, b <-> a, a ie., 7 centers
For N = 2, possible centers = 3
For N = 3, possible centers = 5
For N = 4, possible centers = 7
For N = 5, possible centers = 9
Let’s look at the possible centers and see by how much does it go up for each value of N.
(5 – 3) = (7 – 5) = (9 – 7) = 2
We can calculate the number sequence by using xn. In this case x = 2, so 2N. We notice that for N = 3, the possible centers are not 2N = 6, we have to subtract 1. So the generalized sequence will be 2N – 1.
To solve the given problem, we can iterate through each character in the string while considering it as a possible center for a palindrome. We can then expand around this center while checking its left and right side for mirroring. Since there can be odd length and even length palindromes, we have to consider the max length between them.
To get the max odd palindrome, we pass the left and right pointers as the current character since the center is a single character. Example: “aba”, when i = 1 (b), the left and right starting points to expand around will both be “b”, i = 1.
To get the max even palindrome, we pass the left and right pointers as the current and next character since the center is in between two characters. Example: “abba”, when i = 1 (b), the left and right starting points to expand around will be “b”, i = 1 and the next “b”, i = 2.
We can then take the string with the max length between these two values.
longest_palindromic_substring = ""
for i in range(len(s)):
odd_max = check_palindrome(s, i, i)
even_max = check_palindrome(s, i, i+1)
longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len)
Now let’s write a helper function to check if the given string is a palindrome.
def check_palindrome(s, left, right):
while left >= 0 and right < len(s):
if s[left] == s[right]: # check mirroring
left -= 1
right += 1
else: # Break the loop if the characters mismatch
break
return s[left+1: right]
Complexity
O(N2) time – O(N) to expand around each center and O(N) to check if the substring is a palindrome
O(1) space
Putting it all together.
Solution
def find_longest_palindromic_substring:
if not s:
return s
def check_palindrome(s, left, right):
while left >= 0 and right < len(s):
if s[left] == s[right]: # check mirroring
left -= 1
right += 1
else: # Break the loop if the characters mismatch
break
return s[left+1: right]
longest_palindromic_substring = ""
for i in range(len(s)):
odd_max = check_palindrome(s, i, i)
even_max = check_palindrome(s, i, i+1)
longest_palindromic_substring = max(longest_palindromic_substring, odd_max, even_max, key = len) # This will return the max value based on string length (key = len)
return longest_palindromic_substring
Hope you enjoyed this step by step problem solving approach for the longest palindromic substring problem and learnt a thing or two about palindromes!
In a string s, find the length of the longest substring without repeating characters.
Example
Input: s = “abcabcbb” Output: 3 (“abc”)
Note: Substring means that the letters in the string should be continuous.
Thought Process
The brute force approach to this problem is to construct every possible substring from the given string and keep track of the longest seen substring so far without any repeating characters. This is highly inefficient.
Whenever we want to optimize array or string problems which have some kind of order in them, in this case the continuity of a substring, it’s good to pause and consider whether we can apply the two pointer technique or the sliding window approach. Think about using two pointers in the following situations.
Using two pointers starting at the beginning and end of the array to shrink our search space while comparing the specific elements at start and end pointers
Two pointers starting at the beginning of the array and one moving at a faster speed than the other
Think of sliding window approach in the following situation.
This technique can be used when we need to solve contiguous subarray/ substring problems to solve the overall problem. The window size may be fixed or variable. The window size is variable when we need to find the subarray or the substring in the given problem that meets a certain criteria which is the scenario in this current problem.
Let’s use two pointers called start and end to shrink and expand our sliding window accordingly.
Expand the window when there are no repeated characters in the sliding window
Shrink it when we see a repeated character
Now that we are certain about how we will be using the pointers, the next step is to think about how to formulate shrinking and expansion.
How do we keep track of characters already seen?
As we expand our sliding window considering each additional character added to the substring, let’s store a mapping of a character and the last index where it was seen in a hash map.
lastSeenIndexes = {a: 0, b: 1} etc.
To expand:
We can use the end pointer to traverse the string from left to right for every iteration fromi = 0 to i = n-1.
To shrink:
Shrinking the sliding window means determining the position of the start pointer.
The start pointer may have already advanced past the last repeated character
Or we need to move it to the index right after the index of the last seen character
start = max(start, lastSeenIndexes[c] + 1)
Logic Walkthrough
Complexity
O(N) time complexity and O(N) space
Solution
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
start, maxLen = 0, 0
lastSeenIndexes = {}
for end in range(len(s)):
c = s[end]
if c in lastSeenIndexes:
start = max(start, lastSeenIndexes[c] + 1)
lastSeenIndexes[c] = end
maxLen = max(maxLen, end - start + 1)
return maxLen
Hope you enjoyed this step by step problem solving approach for the longest substring without any repeating characters problem!
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
Pre-order: root, left, right – F, B, A, D, C, E, G, I, H
Recursive Implementation:
The recursive implementation is quite simple and intuitive. We process the root and then its left and right children until there are no nodes left, recursively.
What happens beneath recursion is the use of stack space to store nodes. In the iterative implementation, we can explicitly mimic the use of stack. Note that we need to process the root, the left child and then the right child. In stacks, the rule is Last In First Out (LIFO) or First In Last Out (FILO). This means, to process the left node before the right node in pre-order, we have to add the right node to the stack before adding the left node. See the code below.
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
nodes, stack = [], [root]
while stack:
curr = stack.pop()
nodes.append(curr.val)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return nodes
In-order: left, root, right – A, B, C, D, E, F, G, H, I
Recursive Implementation:
This is very similar to pre-order traversal except that we process the left node before the root and then the right child.
The iterative implementation of in-order traversal is a little tricky. In in-order, we have to process the left node first and then the root followed by the right child. For this, we have to get to the left most node in the tree first which is the leftmost leaf node if it is present.
Do this by using a pointer called curr which points to the root at first.
Traverse the left subtree while adding nodes to the stack, setting curr = curr.left until there are no more nodes left which means until curr is NULL. This will capture the entire left subtree of a node.
Once curr is NULL, start traversing the right subtree. Before traversing the right subtree, pop the stack and add the top most element to the nodes list.
To traverse the right subtree, set curr = curr.right
Basically we keep going as left as possible from a given node until there are no more nodes left. We then pop the stack, add to the results and start traversing the right subtree of the node that we just processed. We keep repeating this process as long as curr is not NULL or the stack is not empty. I recommend that you hand simulate a simple example to understand how the algorithm works.
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
nodes, stack = [], []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
nodes.append(curr.val)
curr = curr.right
return nodes
Post-order: left, right, root – A, C, E, D, B, H, I, G, F
Recursive Implementation:
In post order, we process the left and right child before the root node, recursively.
In the post-order traversal implementation, we will take a simple approach where our stack contains the reverse of post order sequence. Once we are done processing, we will return the results by reversing the stack.
Note that in post-order, we need to return left, right and then root. The reverse of this is root, right and then left. This is the order in which we will be processing the nodes.
To begin with, add the root to the stack.
Pop the stack and add the top most element to nodes list.
Add the left child of this node and then the right child to the stack. This will make sure that we pop and process the right child first and then the left child.
Notice that the order of processing/ popping is root, right and then the left child which is the reverse of post-order traversal.
Upon processing the whole tree, return the reverse of nodes list.
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
nodes = []
while stack:
node = stack.pop()
nodes.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return nodes[::-1]
Level-order: F, B, G, A, D, I, C, E, H
Level-order traversal is also known as Breadth First Search of a tree. For this we can use a queue usually but the code below uses a simple Python List to mimic the same functionality. Here level indicates the height of the tree. We go from root to the leaves level by level.
Add root to a list/ queue called level.
Add all the nodes at the top most level to the nodes list.
Create a temp list and add the left and right child of each node in this level from left to right.
Set level to this temp list to process the next level.
Continue processing each level as long as there are nodes left.
Implementation:
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
level = [root]
result = []
while level:
result.append([node.val for node in level])
temp = []
for node in level:
if node.left:
temp.append(node.left)
if node.right:
temp.append(node.right)
level = [node for node in temp]
return result
Time Complexity: The processing time for different traversals is O(N) where N is the number of nodes in the tree and we have to process all N nodes.
Space Complexity: O(N) for the use of stack/ queue space where N is the number of nodes in the tree.
Hope you enjoyed learning the implementations for different types of tree traversals.
This is an interviewer who can put themselves in your shoes the minute they walk-in. They understand what an important day this is for you and the nervousness you carry. They know that you have done incredible amounts of hard work and won’t try to belittle you in any way. They are here because they want to solve the problem with you. As you go through your interview, whether you aced it or not, you will come out of it feeling like you had a good conversation where you learnt something. This is the kind of interviewer who is great to work with during and after the interview. Although you might think that you are the only one being evaluated, it is a great opportunity for you to evaluate whether you can see yourself working with this person in the future.
Now that we’ve gotten the best package, let’s look at some of the not-so-good scenarios that can happen.
The one who wouldn’t look at you
Sometimes interviewers have been told to type every little conversation that goes on in the room. Although there are some great note-takers who aren’t constantly distracted, most of them in this category don’t care to look at you much. The typing is distracting, there is no eye contact, mostly they aren’t listening nor trying to have an organic conversation with you.
If you had to interview with someone like that, don’t be afraid to take up space in the room. If you start feeling stressed or the interview feels too cold, politely let them know that the typing is a little distracting to your thought process. You can also pause a few times and wait to get their attention before proceeding so that they don’t miss out on the key points that you are mentioning during your interview. It is important for you to stay assured that you are not responsible for their distracted state no matter how boring the question is, so go about it confidently because this day is more important to you than it is for them.
The one who wants you to be a mind-reader
Some interviewers do not let you solve a problem using your own methods. This could be because they aren’t aware of more than one way of solving a problem or they aren’t able to understand how you’re trying to solve it.
Let us always assume the latter because if you are standing there judging the interviewer for not knowing multiple ways of solving a problem, it won’t benefit you in any way. This can create a communication barrier between the both of you. This is when you can take a step back and try to best explain your algorithm with a few examples. Place emphasis on why your approach might work. Pay attention when the interviewer counters it. In some cases, they might expect you to go for the most efficient solution right away. You have probably only come up with a brute force one and can’t really think of how it can be improved. When you feel stuck in this state, explain that you haven’t quite gotten there but you are hoping to get started with a basic solution and iteratively improve upon it once you see the caveats. Most interviewers will be fine with this approach.
The one with the unnecessary arrogance
An interviewer’s job is to make a case for someone who exhibits potential to be a good developer and fit for the company and its culture. Unfortunately, some of them try to check if you are as smart as them, or pick a super difficult problem. This might mostly be a junior developer whose idea of Software Development hasn’t grown beyond solving difficult Leetcode questions yet.
Such an interview scenario can be extremely stressful and the worst outcome is you experiencing a mental block. Try to pick a few easy example cases and manually solve the problem. See if you can turn that into a brute force algorithm that can work for the most common cases. You can then discuss edge cases and improve your algorithm. At any point, an interviewer should not try to trick you or turn it into a stress interview. If that starts to happen, take a few deep breaths and start over. Remember that it’s okay to sometimes not solve it at all. There are thousands of different problems out there and it’s completely okay to be clueless when an overly difficult problem gets presented to you. It was just one of those unlucky days.
The silence of the lambs
This type of interviewer can make you feel nervous throughout the interview by being silent. You may feel stuck at various points on whether your approach is right, waiting for cues to proceed or step back. A good interviewer will make sure to guide you and let you know when you are going in the wrong direction, but sometimes they might not. If this happens, calm yourselves and give it your best shot. Start explaining how you plan on solving the problem and once you are done, stop and explicitly ask whether you can go ahead and code it up. Get to this point as quickly as possible so that you have enough time to brainstorm an alternate approach if your first one doesn’t work out. Be aware of time and allocate a comfortable chunk of time to code the solution.
Hope this post helped you to mentally prepare yourselves to interview with any type of interviewer whom you might encounter. Good luck with your upcoming interviews 🙂
That Girl Coder 