Last Updated: 13 Dec, 2021
Minimum Cost BST
Hard
Asked in companies
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
We can clearly see that the minimum cost of the tree is 90.
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.
Approaches
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)
In this approach, we can see there are many overlapping subproblems, thus it can be solved by creating a cache and storing the solution for each subarray in the cache.
We will create a recursive solution minCostSubarray( freq, i, j, level, cache), ‘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. ‘cache’ is the cache that stores the solution. This function returns the minimum cost of BST in subarray arr[i : j].
Algorithm:
- In the minCostSubarray(arr, freq, i, j, cache) function
- If j is less than i return 0
- Set key as (i, j, level)
- If key is not in cache
- Set cache[key] 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 cache[key] as minimum of itself and leftMinSol + rightMinSol + freq[k]*level
- Return cache[key]
- In the given function
- Create a empty hashmap cache
- Return minCostSubarray(arr, freq, 0, length of freq - 1, cache)
In this approach, we can see there are many overlapping subproblems, thus it can be solved by dynamic programming.
We use an auxiliary array cost[n][n] to store the solutions of subproblems. Here
cost[i][j] = min(cost[i][r - 1] + cost[r + 1][j] + sum(freq[i: j])) , where r ranges from i to j.
Here to find the ‘sum(freq[i: j])’ We can make an optimization to store the prefix sum of ‘freq’ array. ‘freqSum’ and sum(freq[i: j]) = freqSum[j + 1] - freqSum[i]
Algorithm:
- Set N as the length of arr
- Create a prefix sum array of freq array, ‘freqSum’
- Initialise an empty 2D array cost of NxN size
- Iterate i from 0 to N - 1 and set cost[i][i] as freq[i]
- Iterate gap from 1 to N
- Iterate i from 0 to N - gap + 1
- Set j as minimum of i + gap - 1 and N - 1
- Set cost[i][j] as infinity
- Iterate r from i to j
- Set minSol as 0
- If r is not equal to i, add cost[i][r - 1] to minSol
- If r is not equal j, add cost[r + 1][j] to minSol
- Add freq[j + 1] - freq[i] to minSol
- Set cost[i][j] as the minimum of itself and minSol
- Iterate i from 0 to N - gap + 1
- Return cost[0][n - 1]
Similar problems