CF Step
Youtube Linkedin Discord Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Toggle Dark/Light/Auto mode Back to homepage


Let us solve the 1D version of this problem:

You are given an array of n elements. Choose 2 indices i and j such that the cost

A[i] + A[j] + C*|i - j|

is minimized.

Can you come up with an algorithm to find the answer in O(n)?

Define dp[i] to be the minimum cost when the last station is built at node i. The answer to the original problem would then be max(dp[i]). Can you populate this DP in O(n)?

Notice that since this is the last station built, we can freely open |.|.


dp[i] = min(A[i] + A[j] + C*(i - j))

Now, let’s separate out the i and j parts.

dp[i] = min(A[i] + C*i + A[j] - C*j)

Can you now notice a way to popualte this DP in O(n)?

dp[i] = min(A[i] + C*i + A[j] - C*j)

Define contrib[i] = A[i] - C*i, Then, it’s easy to see that

dp[i] = min(A[i] + C*i + contrib[j])
dp[i] = A[i] + C*i + min(contrib[j])

Hence, dp[i] only depends on minimum contribution of previous elements. And the contribution doesn’t change, so these contributions can be computed in advance. Then, you can iterate from left to right, keeping track of minimum contribution seen so far and updating DP values.

Once you’ve populated DP values, the answer is min(dp[i]). Hence, we solved it for 1D.

Now, what is stopping you from applying this trick to the 2D version?

  • There’s no concept of left and right in 2D matrix. Hence, you can’t open |.| like in the 1D version.
  • Even if you were to open |.|, for reach (i, j), as there is no concept of last node, so the the other cell could be anywhere.