Minimum Cost BST

Hard
0/120
profile
Contributed by
16 upvotes
Asked in companies
UberCodenation

Problem statement

You are given two arrays ‘arr’ and ‘freq’, where ‘freq[i]’ represent the number of times we are querying the element ‘arr[i]’. Your task is to construct a binary search tree from the elements of ‘arr’ such that the cost of querying the elements of ‘arr’ is minimum.

The cost of a BST node is the level of the node multiplied by it’s frequency.

Note: 
The array ‘arr’ is sorted.
For example: 
You are given ‘arr’ = [1, 2, 3] and ‘freq’ = [10, 30, 20], we can construct binary search trees such that

TestCase1

We can clearly see that the minimum cost of the tree is 90.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers representing the element of the array, ‘arr’.

The third line of each test case contains ‘N’ space-separated integers representing the element of the array, ‘freq’.
Output Format: 
For each test case print a single integer representing the minimum cost of the BST.

Print a separate line for each test case.
Constraints: 
1 <= T <= 10
1 <= |arr| = |freq| <= 100
0 <= freq[i] <= 10^8

Time Limit = 1 sec
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Sample Input 1:
2
3
1 2 3
10 30 20
2
1 3
50 10
Sample Output 1:
90
70
Explanation:
 For the first test case, ‘arr’ = [1, 2, 3] and ‘freq’ = [10, 30, 20], we can construct binary search trees such that

TestCase1

We can clearly see that the minimum cost of the tree is 90.

For the second test case, ‘arr’ = [1, 2] and ‘freq’ = [50, 10] we can construct binary search trees such that

TestCase2

Sample Input 2:
2
4
1 3 4 6
5 2 1 4
1
1
50
Sample Output 2
23
50
Hint

 Try to find the optimal substructure to the solution.

Approaches (3)
Recursive Solution

In this approach, we will try to see that the minimum cost to form a BST from the subarray ‘arr[i: j]’ is equal to 

minCost(i, j, level) = min(minCost(i, r - 1, level + 1) + minCost(r + 1, jm level + 1) + freq[r] * level) , where r ranges from i to j.

Here r is considered as the root for the nodes ranging from i to r- 1 in left child and r + 1 to j in the right child of r.
 

We will create a recursive solution minCostSubarray( freq, i, j, level), ‘freq’ is the frequency array, i and j are the starting and ending indices of the subarray given and level is the depth of current subtree in the tree. This function returns the minimum cost of BST in subarray arr[i : j].

 

Algorithm:

  • In the minCostSubarray(arr, freq, i, j) function
    • If j is less than i return 0
    • Set minSol as infinity
    • Iterate k from i to j
      • Set leftMinSol as minCostSubarray(freq, i, k - 1, level + 1)
      • Set rightMinSol as minCostSubarrray(freq, k + 1, j, level + 1)
      • Set minSol as minimum of itself and leftMinSol + rightMinSol + freq[k]*level
    • Return minSol 
  • In the given function
    • Return minCostSubarray(freq, 0, length of freq - 1, 1)
Time Complexity

O(N*(2^N)), Where N is the size of the array.

 

We are iterating over the whole subarray in each function call and at each iteration, we are calling the recursive function twice. Hence the overall time complexity is O(N*(2^N)).

Space Complexity

O(N), Where N is the size of the array
 

The space complexity of the recursion stack is O(N).

Code Solution
(100% EXP penalty)
Minimum Cost BST
Full screen
Console