Problem

Sorted keys have search frequencies. Build a BST that minimises the total search cost Σ frequency × depth (the root is at depth 1). Return that cost.

Example 1

Input:  keys = [10, 12, 20], freq = [34, 8, 50]
Output: 142

Also asked as: Optimal Binary Search Tree

Test cases

Case 1

Input:    [34,8,50]
Expected: 142

Case 2

Input:    [34,50]
Expected: 118

Case 3

Input:    [1,1,1]
Expected: 5

Case 4

Input:    [5]
Expected: 5

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Interval DP with prefix frequency sums

Time O(n³)Space O(n²)

dp[i][j] = min expected search cost for keys i..j. Try each key r as the root: dp[i][r−1] + dp[r+1][j] + (sum of freq i..j). Every subtree drops one level, so the whole range’s frequency sum is added once per split.

function optimalBST(freq) {
const n = freq.length;
const prefix = [0];
for (const f of freq) prefix.push(prefix[prefix.length - 1] + f);
const rangeSum = (i, j) => prefix[j + 1] - prefix[i];
const dp = Array.from({ length: n }, () => new Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = freq[i];
for (let len = 2; len <= n; len++)
for (let i = 0; i + len - 1 < n; i++) {
const j = i + len - 1;
dp[i][j] = Infinity;
for (let r = i; r <= j; r++) {
const left = r > i ? dp[i][r - 1] : 0;
const right = r < j ? dp[r + 1][j] : 0;
dp[i][j] = Math.min(dp[i][j], left + right + rangeSum(i, j));
}
}
return dp[0][n - 1];
}