Longest subsequence such that difference between adjacent is one

Problem Statement

Given an array of integers, find the length of the longest subsequence such that the absolute difference between every two adjacent elements in the subsequence is exactly one.

Example:

• Input: arr = [1, 2, 3, 4, 5, 3, 2]
• Output: 6 (The subsequence is [1, 2, 3, 4, 3, 2])

Noob-Friendly Explanation

Imagine you're climbing stairs, but you can only go one step up or one step down at a time. You're given a list of floor numbers, and you need to pick the longest path where each next floor you visit is exactly one above or one below the previous floor. You can skip floors in the list, but the ones you pick must follow the "differ by one" rule.

Approach 1: Brute Force

Intuition

Generate all possible subsequences of the array, then check each one to see if every pair of adjacent elements differs by exactly one. Track the longest valid subsequence.

Algorithm

1. Use recursion to generate all subsequences.
2. For each subsequence, check if the absolute difference between every adjacent pair is 1.
3. Keep track of the maximum length found.

class Solution {
    static int maxLen;

    public static int longestSubseqBrute(int[] arr) {
        maxLen = 0;
        generateSubseq(arr, 0, new java.util.ArrayList<>());
        return maxLen;
    }

    private static void generateSubseq(int[] arr, int index, java.util.List<Integer> current) {
        if (index == arr.length) {
            if (isValid(current)) {
                maxLen = Math.max(maxLen, current.size());
            }
            return;
        }
        // Include current element
        current.add(arr[index]);
        generateSubseq(arr, index + 1, current);
        current.remove(current.size() - 1);

        // Exclude current element
        generateSubseq(arr, index + 1, current);
    }

    private static boolean isValid(java.util.List<Integer> list) {
        if (list.size() <= 1) return true;
        for (int i = 1; i < list.size(); i++) {
            if (Math.abs(list.get(i) - list.get(i - 1)) != 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 3, 2};
        System.out.println(longestSubseqBrute(arr)); // Output: 6
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - we generate all possible subsequences
• Space Complexity: O(n) - recursion stack depth and temporary list

Approach 2: Optimal

Intuition

Use dynamic programming. For each element, the longest valid subsequence ending at that element can be built by looking at all previous elements that differ by exactly one. We store the best answer for each index and take the maximum.

Algorithm

1. Create a dp array where dp[i] = length of the longest valid subsequence ending at index i.
2. Initialize all dp[i] = 1 (each element alone is a valid subsequence of length 1).
3. For each element i, look at all previous elements j. If |arr[i] - arr[j]| == 1, then dp[i] = max(dp[i], dp[j] + 1).
4. The answer is the maximum value in the dp array.

class Solution {
    public static int longestSubseq(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);

        int result = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (Math.abs(arr[i] - arr[j]) == 1) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            result = Math.max(result, dp[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 3, 2};
        System.out.println(longestSubseq(arr)); // Output: 6
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - two nested loops over the array
• Space Complexity: O(n) - the dp array of size n