In a row of dominoes, A[i]
and B[i]
represent the top and bottom halves of the i
-th domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.)
We may rotate the i
-th domino, so that A[i]
and B[i]
swap values.
Return the minimum number of rotations so that all the values in A
are the same, or all the values in B
are the same.
If it cannot be done, return -1
.
Example 1:
Input: A = [2,1,2,4,2,2], B = [5,2,6,2,3,2] Output: 2 Explanation: The first figure represents the dominoes as given by A and B: before we do any rotations. If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.
Example 2:
Input: A = [3,5,1,2,3], B = [3,6,3,3,4] Output: -1 Explanation: In this case, it is not possible to rotate the dominoes to make one row of values equal.
Note:
1 <= A[i], B[i] <= 6
2 <= A.length == B.length <= 20000
Intuition
Let's pick up an arbitrary i
th domino element in the configuration.
The element has two sides, A[i]
is an upper side
and B[i]
is a lower side.
There could be three possible situations here
1 . One could make all elements of A
row or B
row
to be the same and equal to A[i]
value.
For example, if one picks up the 0
th element,
it's possible to make all elements of A
row to be equal to 2
.
2 . One could make all elements of A
row or B
row
to be the same and equal to B[i]
value.
For example, if one picks up the 1
th element,
it's possible to make all elements of B
row to be equal to 2
.
3 . It's impossible to make all elements of A
row or B
row
to have the same A[i]
or B[i]
value.
The third situation means that it's impossible to make all elements in
A
row orB
row to be equal.
Yes, the only one domino element was checked here, and still it's enough because the rotation is the only allowed operation here.
Algorithm
Pick up the first element. It has two sides: A[0]
and B[0]
.
Check if one could make all elements in A
row or B
row
to be equal to A[0]
.
If yes, return the minimum number of rotations needed.
Check if one could make all elements in A
row or B
row
to be equal to B[0]
.
If yes, return the minimum number of rotations needed.
Otherwise return -1
.
Implementation
Complexity Analysis
Time complexity : since here one iterates over the arrays not more than two times.
Space complexity : since it's a constant space solution.
Given an input string (s
) and a pattern (p
), implement wildcard pattern matching with support for '?'
and '*'
.
'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Note:
s
could be empty and contains only lowercase letters a-z
.p
could be empty and contains only lowercase letters a-z
, and characters like ?
or *
.Example 1:
Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa".
Example 2:
Input: s = "aa" p = "*" Output: true Explanation: '*' matches any sequence.
Example 3:
Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.
Example 4:
Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Example 5:
Input: s = "acdcb" p = "a*c?b" Output: false
Intuition
The first idea here is a recursion. That's a straightforward approach but quite time consuming because of huge recursion depth for long input strings.
If the strings are equal p = s
, return True
.
If the pattern matches whatever string p = '*'
, return True
.
If p
is empty, or s
is empty, return False.
If the current characters match p[0] = s[0]
or p[0] = '?'
,
then compare the next ones and return isMatch(s[1:], p[1:])
.
If the current pattern character is a star p[0] = '*'
, then
there are two possible situations:
The star matches no characters, and hence the answer is
isMatch(s, p[1:])
.
The star matches one or more characters, and so the answer is
isMatch(s[1:], p)
.
If p[0] != s[0]
, return False
.
The problem of this algorithm is that it doesn't pass all test cases because of time limit issue, and hence has to be optimised. Here is what could be done:
Memorisation. That is a standard way to optimise the recursion.
Let's have a memorisation hashmap using pair (s, p)
as a key and
match/doesn't match as a boolean value.
One could keep all already checked pairs (s, p)
in this hashmap, so that
if there are any duplicate checks, the answer is right here,
and there is no need to proceed to the computations again.
Clean up of the input data. Whether the patterns with multiple stars
in a row a****bc**cc
are valid wildcards or not, they could be
simplified without any data loss a*bc*cc
. Such a cleanup helps to decrease
the recursion depth.
Algorithm
Here is the algorithm.
Clean up the input by replacing more than one star in a row by a single star:
p = remove_duplicate_stars(p)
.
Initiate the memorisation hashmap dp
.
Return the helper function with a cleaned input: helper(s, p)
.
helper(s, p)
:
If (s, p) is already known and stored in dp, return the value.
If the strings are equal p = s
, or the pattern matches whatever string p == '*'
,
add dp[(s, p)] = True
.
Else if p
is empty, or s
is empty, add dp[(s, p)] = False
.
Else if the current characters match p[0] = s[0]
or p[0] = '?'
,
then compare the next ones and add dp[(s, p)] = helper(s[1:], p[1:])
.
Else if the current pattern character is a star p[0] = '*'
, then
there are two possible situations: the star matches no characters,
and the star matches one or more characters.
dp[(s, p)] = helper(s, p[1:]) or helper(s, p[1:])
.
Else p[0] != s[0]
, add dp[(s, p)] = False
.
Now that the value is computed, return it dp[(s, p)]
.
Implementation
Complexity Analysis
helper(s, p[1:])
and helper(s[1:], p)
.
The maximum number of stars in the pattern after data cleanup is and hence
the time complexity is .Intuition
Recursion approach above shows how painful the large recursion depth could be, so let's try something more iterative.
Memorisation from the first approach gives an idea to try a dynamic programming. The problem is very similar with Edit Distance problem, so let's use exactly the same approach here.
The idea would be to reduce the problem to simple ones.
For example, there is a string adcebdk
and pattern *a*b?k
,
and we want to compute if there is a match for them: D = True/False
.
One could notice that it seems to be more simple for short strings and patterns
and so it would be logical to relate a match D[p_len][s_len]
with the lengths p_len
and s_len
of input pattern and string correspondingly.
Let's go further and introduce a match D[p_idx][s_idx]
which is a match between the first p_idx
characters of the pattern
and the first s_idx
characters of the string.
It turns out that one could compute D[p_idx][s_idx]
, knowing
a match without the last characters D[p_idx - 1][s_idx - 1]
.
If the last characters are the same or pattern character is '?', then
If the pattern character is '*' and there was a match on the previous step
D[p_idx - 1][s_idx - 1] = True
, then
The star at the end of pattern still results in a match.
The star could much as many characters as you wish.
So each step of the computation would be done based on the previous ones, as follows:
Algorithm
Start from the table initiated as False
everywhere but D[0][0] = True
.
Apply rules (1) and (2) in a loop and return D[p_len][s_len]
as an answer.
Implementation
Complexity Analysis
Intuition
Complexity is much better than , but still could be improved. There is no need to compute the entire matrix, and i.e. to check all the possibilities for each star :
...
Let's just pick up the first opportunity "matches zero characters" and proceed further. If this assumption would lead in "no match" situation, then backtrack : come back to the previous star, assume now that it matches one more character (one) and proceed again. Again "no match" situation? Backtrack again : come back to the previous star, and assume now that it matches one more character (two), etc.
Algorithm
Here is the algorithm.
Let's use two pointers here: s_idx
to iterate over the string, and p_idx
to
iterate over the pattern. While s_idx < s_len
:
If there are still characters in the pattern p_idx < p_len
and
the characters under the pointers match
p[p_idx] = s[s_idx]
or p[p_idx] = '?'
,
then move forward by increasing both pointers.
Else if there are still characters in the pattern p_idx < p_len
, and
p[p_idx] = '*'
, then first check "match zero characters" situation, i.e.
increase only pattern pointer p_idx++
.
Write down for a possible backtrack the star position in star_idx
variable,
and the current string pointer in s_tmp_idx
variable.
Else if there is "no match" situation:
the pattern is used up p_idx < p_len
or the characters under the pointers doesn't match.
If there was no stars in the pattern, i.e. no star_idx
, return False
.
If there was a star, then backtrack: set pattern pointer
just after the last star p_idx = star_idx + 1
, and string
pointer s_idx = s_tmp_idx + 1
, i.e. assume that this time the star
matches one more character. Save the current string pointer
for the possible backtrack s_tmp_idx = s_idx
.
Return True
if all remaining characters in the pattern are stars.
Implementation
Complexity Analysis
There are a lot of search-related questions around this problem which could pop up during the interview. To prepare, you could read about string searching algorithm and KMP algorithm.
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.
Example:
Input: [ [0,1,0], [0,0,1], [1,1,1], [0,0,0] ] Output: [ [0,0,0], [1,0,1], [0,1,1], [0,1,0] ]
Follow up:
Before moving on to the actual solution, let us visually look at the rules to be applied to the cells to get a greater clarity.
Intuition
The problem might look very easy at first, however, the most important catch in this problem is to realize that if you update the original array with the given rules, you won't be able to perform simultaneous updation as is required in the question. You might end up using the updated values for some cells to update the values of other cells. But the problem demands applying the given rules simultaneously to every cell.
Thus, you cannot update some cells first and then use their updated values to update other cells.
In the above diagram it's evident that an update to a cell can impact the other neighboring cells. If we use the updated value of a cell while updating its neighbors, then we are not applying rules to all cells simultaneously.
Here simultaneously
isn't about parallelism but using the original values of the neighbors instead of the updated values while applying rules to any cell. Hence the first approach could be as easy as having a copy of the board. The copy is never mutated. So, you never lose the original value for a cell.
Whenever a rule is applied to any of the cells, we look at its neighbors in the unmodified copy of the board and change the original board accordingly. Here we keep the copy unmodified since the problem asks us to make the changes to the original array in-place.
Algorithm
Board
one by one.Complexity Analysis
Time Complexity: , where is the number of rows and is the number of columns of the Board
.
Space Complexity: , where is the number of rows and is the number of columns of the Board
. This is the space occupied by the copy board we created initially.
Intuition
The problem could also be solved in-place. space complexity could be too expensive when the board is very large. We only have two states live(1)
or dead(0)
for a cell. We can use some dummy cell value to signify previous state of the cell along with the new changed value.
For e.g. If the value of the cell was 1
originally but it has now become 0
after applying the rule, then we can change the value to -1
. The negative sign
signifies the cell is now dead(0) but the magnitude
signifies the cell was a live(1) cell originally.
Also, if the value of the cell was 0
originally but it has now become 1
after applying the rule, then we can change the value to 2
. The positive sign
signifies the cell is now live(1) but the magnitude
of 2 signifies the cell was a dead(0) cell originally.
Algorithm
Board
one by one.The updated rules can be seen as this:
Rule 1: Any live cell with fewer than two live neighbors dies, as if caused by under-population. Hence, change the value of cell to -1
. This means the cell was live before but now dead.
Rule 2: Any live cell with two or three live neighbors lives on to the next generation. Hence, no change in the value.
Rule 3: Any live cell with more than three live neighbors dies, as if by over-population. Hence, change the value of cell to -1
. This means the cell was live before but now dead. Note that we don't need to differentiate between the rule 1 and 3. The start and end values are the same. Hence, we use the same dummy value.
Rule 4: Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Hence, change the value of cell to 2. This means the cell was dead before but now live.
Apply the new rules to the board.
Board
in terms of binary values i.e. live(1) and dead(0), we iterate the board again and change the value of a cell to a 1
if its value currently is greater than 0
and change the value to a 0
if its current value is lesser than or equal to 0
.Complexity Analysis
Time Complexity: , where is the number of rows and is the number of columns of the Board
.
Space Complexity:
So far we've only addressed one of the follow-up questions for this problem statement. We saw how to perform the simulation according to the four rules in-place i.e. without using any additional memory. The problem statement also mentions another follow-up statement which is a bit open ended. We will look at two possible solutions to address it. Essentially, the second follow-up asks us to address the scalability aspect of the problem. What would happen if the board is infinitely large? Can we still use the same solution that we saw earlier or is there something else we will have to do different? If the board becomes infinitely large, there are multiple problems our current solution would run into:
Such open ended problems are better suited to design discussions during programming interviews and it's a good habit to take into consideration the scalability aspect of the problem since your interviewer might be interested in talking about such problems. The discussion section already does a great job at addressing this specific portion of the problem. We will briefly go over two different solutions that have been provided in the discussion sections, as they broadly cover two main scenarios of this problem.
One aspect of the problem is addressed by a great solution provided by Stefan Pochmann. So as mentioned before, it's quite possible that we have a gigantic matrix with a very few live cells. In that case it would be stupidity to save the entire board as is.
If we have an extremely sparse matrix, it would make much more sense to actually save the location of only the live cells and then apply the 4 rules accordingly using only these live cells.
Let's look at the sample code provided by Stefan for handling this aspect of the problem.
Essentially, we obtain only the live cells from the entire board and then apply the different rules using only the live cells and finally we update the board in-place. The only problem with this solution would be when the entire board cannot fit into memory. If that is indeed the case, then we would have to approach this problem in a different way. For that scenario, we assume that the contents of the matrix are stored in a file, one row at a time.
In order for us to update a particular cell, we only have to look at its 8 neighbors which essentially lie in the row above and below it. So, for updating the cells of a row, we just need the row above and the row below. Thus, we read one row at a time from the file and at max we will have 3 rows in memory. We will keep discarding rows that are processed and then we will keep reading new rows from the file, one at a time.
@beagle's solution revolves around this idea and you can refer to the code in the discussion section for the same. It's important to note that there is no single solution for solving this problem. Everybody might have a different viewpoint for addressing the scalability aspect of the problem and these two solutions just address the most basic problems with handling matrix based problems at scale.
Analysis written by: @godayaldivya.
Given an array nums
of n integers where n > 1, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Example:
Input:[1,2,3,4]
Output:[24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
From the looks of it, this seems like a simple enough problem to solve in linear time and space. We can simply take the product of all the elements in the given array and then, for each of the elements of the array, we can simply find product of array except self
value by dividing the product by .
Doing this for each of the elements would solve the problem. However, there's a note in the problem which says that we are not allowed to use division operation. That makes solving this problem a bit harder.
It's much easier to build an intuition for solving this problem without division once you visualize how the different products except self
look like for each of the elements. So, let's take a look at an example array and the different products.
Looking at the figure about we can figure another way of computing those different product values.
Instead of dividing the product of all the numbers in the array by the number at a given index to get the corresponding product, we can make use of the product of all the numbers to the left and all the numbers to the right of the index. Multiplying these two individual products would give us the desired result as well.
For every given index, , we will make use of the product of all the numbers to the left of it and multiply it by the product of all the numbers to the right. This will give us the product of all the numbers except the one at the given index . Let's look at a formal algorithm describing this idea more concretely.
Algorithm
L
and R
where for a given index i
, L[i]
would contain the product of all the numbers to the left of i
and R[i]
would contain the product of all the numbers to the right of i
. L
, would be 1
since there are no elements to the left of the first element. For the rest of the elements, we simply use . Remember that L[i]
represents product of all the elements to the left of element at index i.1
in where is the number of elements in the array, and keep updating R[i]
in reverse. Essentially, . Remember that R[i]
represents product of all the elements to the right of element at index i.i
, we find the product except self
as . Let's go over a simple run of the algorithm that clearly depicts the construction of the two intermediate arrays and finally the answer array.
!?!../Documents/238_anim1.json:770,460!?!
For the given array , the L
and R
arrays would finally be:
Complexity analysis
Although the above solution is good enough to solve the problem since we are not using division anymore, there's a follow-up component as well which asks us to solve this using constant space. Understandably so, the output array does not count towards the space complexity. This approach is essentially an extension of the approach above. Basically, we will be using the output array as one of L
or R
and we will be constructing the other one on the fly. Let's look at the algorithm based on this idea.
Algorithm
answer
array where for a given index i
, answer[i]
would contain the product of all the numbers to the left of i
. answer
array the same way we constructed the L
array in the previous approach. These two algorithms are exactly the same except that we are trying to save up on space.R
array from before. Instead, we simply use a variable to keep track of the running product of elements to the right and we keep updating the answer
array by doing . For a given index i
, answer[i]
contains the product of all the elements to the left and R
would contain product of all the elements to the right. We then update R
as
Complexity analysis
Analysis written by: @sachinmalhotra1993.
Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1:
Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
There are two general strategies to traverse a tree:
Depth First Search (DFS
)
In this strategy, we adopt the depth
as the priority, so that one
would start from a root and reach all the way down to certain leaf,
and then back to root to reach another branch.
The DFS strategy can further be distinguished as
preorder
, inorder
, and postorder
depending on the relative order
among the root node, left node and right node.
Breadth First Search (BFS
)
We scan through the tree level by level, following the order of height, from top to bottom. The nodes on higher level would be visited before the ones with lower levels.
On the following figure the nodes are numerated in the order you visit them,
please follow 1-2-3-4-5
to compare different strategies.
To solve the problem, one could use the property of BST : inorder traversal of BST is an array sorted in the ascending order.
It's a very straightforward approach with
time complexity.
The idea is to build an inorder traversal of BST which is
an array sorted in the ascending order.
Now the answer is the k - 1
th element of this array.
Complexity Analysis
The above recursion could be converted into iteration, with the help of stack. This way one could speed up the solution because there is no need to build the entire inorder traversal, and one could stop after the kth element.
Complexity Analysis
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Insert and delete in a BST were discussed last week, the time complexity of these operations is , where is a height of binary tree, and for the balanced tree.
Hence without any optimisation insert/delete + search of kth element has complexity. How to optimise that?
That's a design question, basically we're asked to implement a structure which contains a BST inside and optimises the following operations :
Insert
Delete
Find kth smallest
Seems like a database description, isn't it? Let's use here the same logic as for LRU cache design, and combine an indexing structure (we could keep BST here) with a double linked list.
Such a structure would provide:
time for the insert and delete.
for the search of kth smallest.
The overall time complexity for insert/delete + search of kth smallest is instead of .
Complexity Analysis
Time complexity for insert/delete + search of kth smallest: , where is a tree height. in the average case, in the worst case.
Space complexity : to keep the linked list.