Longest subsequence such that difference between adjacent is one

The problem, simply

You get a row of numbers. Choose some of them, keeping their order, so that every two neighbors in your choice differ by exactly 1 (up one or down one). Give back the length of the longest such choice.

The choice is a subsequence: you may skip numbers, but you may not reorder them.

A story to remember it

Picture it

Examples

Way 1: the simple way

Trying every choice is O(2^n). Instead, remember an answer per position: dp[i] is the longest good chain that ends exactly at arr[i].

1. Every number alone is a chain, so dp[i] = 1.
2. For each i, look back at every j < i. If |arr[i] - arr[j]| == 1, try dp[j] + 1.
3. The answer is the biggest dp[i].

class Solution {
    public int longestSubseq(int[] arr) {
        int n = arr.length, best = 0;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;                                     // the number alone
            for (int j = 0; j < i; j++) {
                if (Math.abs(arr[i] - arr[j]) == 1) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);    // step on from arr[j]
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }
}

How long it takes: each number looks back at all earlier ones, O(n^2). Extra room: the dp array, O(n).

Way 2: the clever way

Way 1 looks at every earlier number, but only two values can ever help: x - 1 and x + 1. And among earlier numbers with the same value, only the best chain matters. So keep a notebook, a hash map, from a value to the longest chain seen so far that ends with that value.

1. For each number x from left to right:
2. Look up x - 1 and x + 1 in the map (missing means 0).
3. The chain ending at this x is the bigger of the two, plus 1.
4. Store it for x if it beats what x already had. Update the best.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestSubseq(int[] arr) {
        Map<Integer, Integer> bestEnd = new HashMap<>();   // value -> longest chain ending with it
        int best = 0;
        for (int x : arr) {
            int down = bestEnd.getOrDefault(x - 1, 0);     // come up from x - 1
            int up = bestEnd.getOrDefault(x + 1, 0);       // come down from x + 1
            int len = Math.max(down, up) + 1;
            bestEnd.merge(x, len, Math::max);              // keep the longer one for x
            best = Math.max(best, len);
        }
        return best;
    }
}

How long it takes: two map lookups per number, O(n) on average. Extra room: the map holds at most one entry per different value, O(n).

Watch out for

• Differ by exactly 1 means x - 1 and x + 1. Do not include x itself.
• Values can be negative or huge, so use a map. An array indexed by value only works if values are small and not negative.
• When a value repeats, keep the longer chain for it. Overwriting with a shorter one loses answers.

What interviewers ask next

• Difference of exactly d instead of 1: look up x - d and x + d. Same O(n).
• Only going up by 1 (consecutive increasing chain, like 3, 4, 5): look up only x - 1.
• Longest arithmetic subsequence with a given difference: same map trick, bestEnd[x] = bestEnd[x - d] + 1.
• Print the chain: also store the index where each value's best chain ends and a parent index for each position.
• Difference at most 1 (0 or 1): also look up x itself.

Remember this

Grown-up words: the stair walk is a subsequence with adjacent difference one, the notebook is a hash map used as the DP table, and Way 1 is the classic "ends at i" O(n^2) DP.