find maximum length of subsequence with adjancent diff less than 2

Question

Problem Statement:

You are given an array of integers arr of size n.

Select a subsequence of integers and rearrange them to form a circular sequence such that the absolute difference between any two adjacent integers (including the last and first) is at most 1.

Find the maximum number of integers that can be selected.

Notes:

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements.

The selected integers can be rearranged in any order.

The sequence is circular — the last and first integers are considered adjacent.

Constraints:

1 <= n <= 2 × 10^5

0 <= arr[i] <= 10^9

Examples:

Input: arr = [4, 3, 5, 1, 2, 2, 1]
Output: 5
Explanation: maximum length subsequence is : [3, 1, 2, 2, 1], it can be rearranged to seq : [2, 1, 1, 2, 3] of length 5, note that the condition must be satisfied in circular also, means abs(seq[0] - seq[seq.length-1]) means abs(2-3) <= 0 

Input: arr = [3, 7, 5, 1, 5]
Output: 2
Explanation: maximum length subsequence is : [5,5] of length 2

Input: arr = [2, 2, 3, 2, 1, 2, 2]
Output: 7
Explanation: maximum length subsequence is : [2,2,3,2,1,2,2] of length 7

Input: arr = [1,2,3,4,5]
Output = 2
Explanation: maximum length subsequence is : [1,2] or [2,3] or [3,4] or [4,5], so length is 2. 

Note, that the subsequence should satisfy the circular condition also Here is my code:

import java.util.*;

class Main {
    public static int solve(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        int max = 0;
        for (int num : freq.keySet()) {
            int count = freq.get(num);
            int countWithNext = freq.getOrDefault(num + 1, 0);
            int countWithPrev = freq.getOrDefault(num - 1, 0);
            max = Math.max(max, countWithPrev + count + countWithNext);
        }

        return max;
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[]{4,3,5,1,2,2,1})); // Expected: 5
        System.out.println(solve(new int[]{3,7,5,1,5})); // Expected: 2
        System.out.println(solve(new int[]{2,2,3,2,1,2,2})); // Expected: 7
        System.out.println(solve(new int[]{1,2,3,4,5})); // Expected: 2
    }
}

I am able to find the maximum length subsequences, but not to find how to meet the circular condition, so for the test case [1,2,3,4,5], my code is returning 5 instead of 2.

Also, the approach itself is failing for input [1,2,3,4,3,2] as commented by John Bollinger

What is the correct approach to solve this with less time complexity.

Answer 1

What is the correct approach to solve this with less time complexity.

Note well the hint from @btilly in comments:

Your subsequence has a min, has a max, and every value between those must appear 2+ times.

That's very nearly a fingerprint that you can match, but before we extend it into such a fingerprint, let's first consider why it is so.

Consider a member s_n of a contiguous circular sequence that is neither its minimum value nor its maximum value. Now suppose we traverse the cycle starting at s_n. Before we return to s_n, we will traverse both the sequence minimum and the sequence maximum, and because the sequence is arranged contiguously, between those we must traverse another element whose value is the same as s_n. Therefore, every member that is neither minimum nor maximum in the sequence must occur at least twice.

The same is not true of minimum or maximum, however. There may be multiple appearances of one or both of those, but we can still form a cycle with only one of each. In the most trivial case, a single appearance of a single number satisfies the criteria, but we can have a single appearance each of the minimum and maximum with any overall number of elements other than exactly 3.

Now suppose that we have a collection of contiguous numbers, in any order, such that there are at least two appearances of each, except possibly for the minimum and maximum among them. We can form from them a circular sequence by first sorting them in ascending order, then taking one of each number that is neither minimum nor maximum, and shifting them to the end, in descending order. For example,

• starting with 2, 4, 3, 2, 3, 1, 3, 5, 5, 4,
• we sort to get 1, 2, 2, 3, 3, 3, 4, 4, 5, 5
• then we move one 4, one 3, and one 2 to the end to get 1, 2, 3, 3, 4, 5, 5, 4, 3, 2, which satisfies the requirements

It follows that for a collection of numbers to be suitable for forming the kind of circular sequence you require, it is both necessary and sufficient that (i) they are contiguous, and (ii) every number that is neither the minimum nor the maximum appears at least twice.

NOW you have your fingerprint. It is possible to find the maximal sequence with that fingerprint in O(n log n) steps (worst case), but I leave it to you to work out the details.

Answer 2

Your code only looks at the frequencies of the immediate "neighbors" (in sorted order) to determine a count. This will give wrong results when the correct answer will involve more than 3 distinct numbers.

Counting frequencies is a good approach, but then scan further than only to the direct neighbors of the value at hand. It will also be helpful to only look for neighbors when you are sure you are at a low end of a potential range -- that way you only have to scan values in ascending order. A value is a "low" when either its frequency is 1 or there is no occurrence of that value minus one.

Here is how the loop (after you got the frequencies) can be made to work:

        int max = 0;
        for (int num : freq.keySet()) {
            int count = freq.get(num);
            if (count != 1 && freq.containsKey(num-1)) continue;
            // We're at a low end of a range
            int groupCount = count;
            do {
                num++;
                count = freq.getOrDefault(num, 0);
                groupCount += count;
            } while (count > 1);
            max = Math.max(max, groupCount);
        }
        return max;

Assuming that get and put operations on a hash map have a amortised time complexity of O(1), this algorithm has a O(𝑛) time complexity, where 𝑛 is the size of the input array.