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.
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
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:
Si % Sj = 0 or Sj % Si = 0
If there are multiple solutions, returning any subset is fine.
Example 1:
Input: [1,2,3] Output: [1,2] or [1,3]
Example 2:
Input: [1,2,4,8] Output: [1,2,4,8]
Solution #1:
Let’s say we have a list of numbers as shown below.
nums = [1, 2, 3, 4]
First thing to notice is that every integer is its own largest divisible subset if the given condition does not satisfy for any other element in the list. For example, given a list [5, 7] where neither of them are divisible by each other, the largest divisible subset can be [5] or [7], so both are correct.
Keeping that in mind, a straightforward approach is to check every integer with every other integer in the list to see if the condition Si % Sj = 0 or Sj % Si = 0 is satisfied. Before we begin, we sort the given list so that we can avoid having too many enumerations. Let’s understand this using another example as shown below.
[2, 4, 8]
Note that the list above is sorted in ascending order and all the elements form a divisible subset. If we choose to add one more element d to the divisible subset at front or an element D at the end of the list, all we have to check is whether D % 8 == 0 and 2 % d == 0.
At first we place each integer in its own subset. Then, we can iterate through the list using double for loops and whenever a pair satisfies the given condition, we extend the individual subsets. We start with the following subsets.
[{1}, {2}, {3}, {4}]
Use two pointers i and j where i is used to traverse the sorted list [1, 2, 3, 4]
Calculate the largest divisible subset that ends at the element at i. Use another pointer j to traverse the list until the index i.
If the values at i and j satisfy the divisibility condition ie. nums[i] % nums[j] == 0 and if the (size of the subset at i) < (size of subset at j + 1), then extend the subset at i. This is because we want to extend the subset only if we can get another larger subset, otherwise it’s already the largest subset possible ending with element at i.
To understand clearly, check the example walkthrough below.
Example walkthrough
Once we have all the subsets, we return the one with the max length.
Time Complexity: O(N2) since we use double for loops
Space Complexity: O(N2) for the use of subsets
Code:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums:
return []
nums.sort()
subsets = [{i} for i in nums]
for i in range(len(nums)):
for j in range(i):
if nums[i] % nums[j] == 0 and len(subsets[i]) < len(subsets[j]) + 1:
subsets[i] = subsets[j] | {nums[i]}
return max(subsets, key = len)
Hope you enjoyed learning how to solve the largest divisible subset problem. Have a great day!
Today, we will be discussing one of my favorite problems because it’s open ended and design oriented. We have to design a data structure that can perform insert, delete and get random operations with an average of O(1) time complexity.
insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Let’s take a look at our toolbox to see what data structures we can use in solving this problem. The table below lists the average time complexity for some of the operations.
Data structure
Access
Insert
Delete
Arrays
O(1)
O(N)
O(N)
Stacks
O(N)
O(1)
O(1)
Queues
O(N)
O(1)
O(1)
Hashmap
O(1)
O(1)
O(1)
Linked List
O(N)
O(1)
O(1)
Average time complexity
The above table shows that most of the data structures except arrays have an average time complexity of O(1) to perform insert and delete operations but remember that inserting and deleting from the end of an array is still O(1). The catch here is to get the getRandom function perform at O(1) time. We cannot get a random index from Hashmaps and accessing indexes takes O(N) time with other data structures except for arrays. In this case, we can leverage the benefits of hashmaps and arrays by doing the following.
Insertion O(1)
Insert an element at the end of an array
Store the insertion indexes of elements in a hashmap
Remove O(1)
Find the index of the element to be removed, from the hashmap
Copy the last element of the array into this index
Pop the last element of the array O(1)
Delete the entry for this element from the hashmap
Get Random O(1)
Use a random function to get an index between 0 and len(array) – 1
Return the element at that index from the array
Time Complexity: All operations happen in O(1)
Space Complexity: O(N) for the array and O(N) for the hashmap, so the overall space complexity is O(N)
Code:
class RandomizedSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.nums = []
self.mapping = {}
def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val not in self.mapping:
# Insert the element at the end of nums
self.nums.append(val)
index = len(self.nums) - 1
self.mapping[val] = index
return True
return False
def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val not in self.mapping:
return False
removeIndex = self.mapping[val]
lastValue = self.nums[-1]
# store the last element in the removed val index
self.nums[removeIndex] = lastValue
# Update the index value of last element
self.mapping[lastValue] = removeIndex
# clean up
self.nums.pop()
del self.mapping[val]
return True
def getRandom(self) -> int:
"""
Get a random element from the set.
"""
randIndex = random.randint(0, len(self.nums) - 1)
return self.nums[randIndex]
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
Hope you enjoyed learning how to design a data structure that can perform insert, delete and get random operations in O(1) time. Have a great day!
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
That Girl Coder 