Approaches To Problem Solving #14(Divide and Conquer | DP | Array)
Problem: Given a list of integers, arr. Consider a tree where arr represents the values of its leaves in an inorder traversal. All internal nodes have 2 children each and their value is equal to the product of the largest leaf value of its left subtree and the largest leaf value of its right subtree. Find the tree with the minimum sum of its values and return the sum.
Let us consider the following example to get a clearer idea of this problem,
The answer tree for the above given input array can be created as follows,
It is given that the array provided to us as input depicts the leaves of the tree and that too in inorder manner. Hence, we can safely assume that we should not alter this array by say, sorting or reversing the array.
Since we are only considering the leaves to begin the construction of the tree, it seems intuitive to think about fixing the root node for the tree first and then build the tree subsequently. How? Let us use the concept of fixing the pivot for doing it. If we fix a pivot for a given array, we can divide the given array into two parts (Left and Right), where Left part indicates all the leaves that should belong to the left subtree for the root node and Right part indicates all the leaves that should belong to the right subtree for the root node.
Approach #1: Let us extend this idea to all the subtrees that we are going to explore. Whenever solving for some subtree, we will fix a pivot and try to create the left and right partitions and then lay it as the basis for finding the next answers for the other subarrays respectively.
Consider the following representation,
We can create a tree using the above division as,
We can approach the proposed solution in a recursive manner. We break our current subarray under consideration into two partitions, [L, i] and [i + 1, R], where ‘i’ denotes the pivot, ‘L’ denotes the left bound of the subarray and ‘R’ denotes the right bound of the subarray, and then progress further to find the answers for other subarrays and combining all the solutions to figure out the best solution.
Talking about the states, Left bound and Right bound for a given array are sufficient to define the current state of the recursion. Transitions can be defined as follows,
answer[L][R] = min(answer[L][R], maxElement(L, i) * maxElement(i + 1, R) + recursion(L, i) + recursion(i + 1, R))
where 1 ≤ i ≤ N, and N is the length of the array.
Basically, we keep fixing the pivot for a given [L, R] as i, and since we know that [L, i] depicts the left subtree for the current subarray and [i + 1, R] depicts the right subtree, we return the product of the maximum leaves of both the left and the right subtree and add them to the answer for the rest of the subarrays. The best solution from all the candidates can be found by checking if the found solution is the minimum of them all or not, and updating the minimum answer found accordingly.
We compute the answer for the given input array by calculating the value for answer[1][N].
We need to take care of the base case where L is equal to R, in that case we just return the Lth value of the input array.
We can use memoization for storing the answers for each state, so that we don’t end up visiting the same state more than once.
The time complexity for the given solution is O(N²), since there can be at most N² states.
We can find a solution for the given problem using concepts of heaps and monoqueues too.
In our next article, one of the problems that we are going to discuss is given below,
Problem: You are given N cities represented as integers and a list of one-way roads that connects one city to another. Return whether you can reach one city from any city.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Divide and Conquer, Dynamic Programming and Arrays further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 14th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
