Push DP vs Pull DP

$\mathcal{O}(n)$ : Problem Link

$\mathcal{O}(n^2)$ : Problem Link

Target Audience : If you are not able to come up with the $O(n^2)$ algorithm in 5 minutes, and the $O(n)$ algorithm in additional 5 minutes, this tutorial is for you. If you are a beginner to Dynamic Programming on Prefix, this 1D DP problem is a good starting point for you to learn the technique. This tutorial assumes that you already have some experience with 1D DP.

For an $O(n^2)$ solution, we can define

$dp[i]$ is true if the prefix $[0 \dots i]$ can be sent over a network.

How do we perform the transitions? For a fixed $i$, suppose the last segment is $[j \dots i]$. Then, if $[j \dots i]$ is a valid segment, we are interested in knowing whether the prefix $[0 \dots j - 1]$ can be sent over a network. This is nothing but $dp[j - 1]$. Hence, we can iterate over all possible $j$ backwards and take contribution from valid segments.

for (int i = 0; i < n; i++) {
    // The last segment is [j, i] (inclusive of length).
    for (int j = i - 1; j >= 0; j--) {
        int len = i - j;
        if ((a[i] == len) || (a[j] == len)) {
            dp[i] = dp[i] || (j ? dp[j - 1] : true);
        }
    }
}

Full code

The time complexity of this solution is $O(n^2)$, and it will TLE on Test 12. How do we optimize this?

Notice that there can be 2 types of valid segments, one where the length is written to the right and one where the length is written to the left.

Let’s consider the first type of segment, with length to the right. Since the length is fixed to $a[i]$, we will only take contribution from $j - 1$ where $j = i - a[i]$. So, this is not responsible for bumping up the time complexity to $O(n^2)$.

Then, let’s consider the second type of segment, where the length is present to the left. However, in this case, we are not sure where the segment starts, so we end up scanning everything towards the left. Also, there can be multiple possible candidates for $j$ such that $a[j]$ denotes the length.

In the current DP, we are pulling contributions from various indices. This is known as Pull DP.

So far we’ve been focusing on $i$. Let’s change our perspective and focus on $j$ instead. We know that $i$ can take contributions from several such $j$s but how many indices will $j$ provide contribution to? In fact, each such $j$ will only provide contribution to a single fixed $i$. Hence, it’s clear that we are scanning redundant $j$ for each $i$.

So, instead of going backwards and pulling contribution from each $j$ when populating $dp[i]$, let’s be a bit more proactive and keep updating the $dp[i]$ values as soon as we see $j$ in our journey for the first time. This technique of providing contribution to future DP values even before encountering them is known as Push DP. That is, you anticipate that a future $i$ would come back looking for this $j$. So, to reduce the time complexity, you push the contribution immediately so that $i$ won’t have to travel back.

for (int i = 0; i < n; i++) {
    // Suppose last segment is [j,i].
    // Then, i - j = a[i] ==> j = i - a[i]
    // Therefore, we need to pull contribution from j - 1.
    int j = i - a[i];
    if (j == 0) {
        dp[i] = true;
    } else if (j > 0) {
        dp[i] = dp[i] || dp[j - 1];
    }

    // Push the contribution forward.
    // Suppose last segment is [i,j].
    // Then, j - i = a[i] ==> j = i + a[i].
    // Therefore, we need to push contribution to j.
    j = i + a[i];
    if (j < n) {
        if (i == 0) {
            dp[j] = true;
        } else if (i > 0) {
            dp[j] = dp[j] || dp[i - 1];
        }
    }
}

Full code

The above code is a combination of Pull DP (for rightmost length) and Push DP (for leftmost length). Since there’s just a single loop, the time complexity is $O(n)$.

Note : For push DP, always make sure to avoid partial updates, i.e, if $j$ provides contribution to $i$, you need to ensure that DP values of $j$ is never updated after it has provided the contribution. This is true in the code above, since each element provides contribution to the rightmost elements only. However, the same code would become incorrect if you swapped the position of pull dp and push dp in the for-loop. Hence, you should always propagate the values of $dp[j]$ forward once you are absolutely sure that there will be no more future updates to this DP value.