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.
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.