[Solution]Problem 42: Length of the longest subarray where all its elements are distinct (Microsoft)
Math, Permutations, Combinatorics, Heaps, Trees
Problem
This problem was asked by Microsoft.
Write a program to determine how many distinct ways there are to create a max heap from a list of N
given integers.
Examples:
Input : n = 3
Output : Assume the integers are 1, 2, 3.
Then the 2 possible max heaps are:
3
/ \
1 2
3
/ \
2 1
Input : n = 4
Output : Assume the integers are 1, 2, 3, 4.
Then the 3 possible max heaps are:
4
/ \
3 2
/
1
4
/ \
2 3
/
1
4
/ \
3 1
/
2
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below. Thanks to the guaranteed refund policy, there is no risk to you -
Step 1: Reading the Question
This might seem like a trivial step, but for such a question this step can be crucial. For problems that involve some degree of combinatorics, this is a phenomenal first step. Reading the question can help us generate the needed insights.
For such a question it is tempting to dive right in, generate valid heaps and count them. However, it is clear, that such an approach would be expensive. And generating heaps is hard work. Let’s see if we can conduct some kind of analysis to make our lives easier.
If you look at the examples, you will notice that all the heaps have the N number at the root. This is not too shocking. In a max heap- the value of the parent node>= value of children.
However, this makes the scope of our problem slightly easier. Instead of worrying about N different values, we know that we only have to worry about N-1 values being arranged in either the left or right child. This let’s us come up with the equation R+L=N-1.
Can we make infer any other information? I got a good one for you.
Heaps are by definition complete binary trees. This means, that for a given number N, the numbers R and L are constant, even if the nodes on the Left and Right change. This means that we can directly solve for L and R, and we will be able to come up with how to solve the problem at the end.
Step 2- Computing L, R, and the final combinations
We know that the heap is a recursive data structure. The number of combinations from the root will be a direct function of the number of nodes in the left and right sub-trees.
We know that our function for the number of heaps will have the form
f(N)= f(R) * f(L)* k
where k is some constant. Let’s figure out what that constant should be. We can choose any l of the remaining n-1 elements for the left sub-tree as they are all smaller than the root.
The total ways of constructing the heap are thus:
f(N) = choose(N, L) * f(L) * f(R)
The next step is to see if we can figure out an expression for L. Let’s do that.
Step 3: Calculating our L
This is the final piece that we need to figure out in our solution. Once we have an expression for L, we can calculate R (N-1-L) and thus have the functions for every value needed.
We can first calculate the height, h, of the tree. We know that 2^H will be N (for complete trees), assuming that the root is at level 0. What about incomplete trees?
The number of leftover nodes on the bottom row can be obtained by subtracting the number of nodes upto the row above from N
. Since our DS is a heap, we know that all the roles will be filled completely, with the last row being the only possible exception. In that case, all the leftover nodes will be contained in the left subtree.
We know that the number of nodes seen upto (not including) the last row will be
1+ 2 + 4 + … + 2^(H-1)= 2^H -1
Thus the number of nodes seen in the bottom rows will be
bottom= N- 2^H +1
Combining the left side nodes from the complete tree without the last level, and the bottom nodes that belong to the left tree, we come to the formula
Number of nodes in the left subtree, upto last row, not including root-2^(H - 1)- 1
Therefore L,
L = 2^(H - 1)- 1 + min(2^(H - 1), bottom).
This gives us all the relevant values that we can use to calculate the expressions. Notice how the coding tasks we have left have changed from generating heaps (a very hard coding task) to doing combinatorics (much easier). Let’s finish that up.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.