The longest subsequence with specified difference between min and max

Question

As an input you have non-empty zero-indexed array of integers. The goal is to find the longest subsequence (any sequence obtained by removing some elements from A), where difference between min value and max value does not exceed 1.

For example, given array: 6,10,7,7,9,8 function should return 3, because 6,7,7 (or 7,7,8) is the longest qualifying subsequence.

Is this solution efficient?

    public int solution(int[] A) {
    Arrays.sort(A);
    int counter = 0;
    int res = 0;
    int val = -1;
    for (int i = 0; i < A.length - 1; i++) {
        if (val == -1 && A[i + 1] - A[i] < 2) {
            counter = 2;
            val = A[i + 1] - A[i];
        } else if (val == 0 && A[i + 1] - A[i] <= 1) {
            counter++;
            val = A[i + 1] - A[i];
        } else if (val == 1 && A[i + 1] - A[i] == 0) {
            counter++;
        } else {
            val = -1;
            res = Math.max(res, counter);
            counter = 0;
        }
    }
    return res;
}

Time complexity is linearithmic.

Answer 1

Bugs

The function doesn't handle the last series of numbers. For example:

Input: 5 5 5       Output: 0
Input: 5 5 9 9 9   Output: 2

This can be fixed by modifying the end of the function:

    return Math.max(res, counter); // <-- Accounts for last series

Also, the function fails to consider a number as the lower of two numbers once it has used it as the upper of two numbers. For example:

Input: 5 5 6 6 6 7 7 7 10    Output: 5 (should be 6)

Here, it groups 5 and 6 together but never considers that 6 and 7 can be grouped together.

Answer 2

public int solution(int[] A) {

Not a big deal, but methods are normally given verb names rather than noun names.

public static int mapSolve(int[] A, int maximumDifference) {

I added the static keyword because the method wasn't using any class variables. This allows us to call the method without declaring an instance of the class first.

I added the maximumDifference variable to allow for alternate values other than 1.

A linear time solution

It's possible to solve this in linear time for a given value for maximumDifference. Note that if you allow that to vary as well, it would be \$O(m*n)\$ where \$m\$ is the maximumDifference and \$n\$ is the number of items in the array.

    Map<Integer, Integer> countsOf = new HashMap<Integer, Integer>();
    int maxCount = 0;

    for ( int number : A ) {
        Integer count = countsOf.get(number);
        if (null == count) {
            countsOf.put(number, 1);
        } else {
            countsOf.put(number, count + 1);
        }
    }

    for ( Map.Entry<Integer, Integer> countOf : countsOf.entrySet()) {
        int count = countOf.getValue();
        int number = countOf.getKey();

        for (int i = 1; i <= maximumDifference; i++) {
            Integer c = countsOf.get(number + i);
            if ( null != c ) {
                count += c;
            }
        }

        if ( count > maxCount ) {
            maxCount = count;
        }
    }

    return maxCount;

This code counts the members of all the groups of adjacent numbers that are possible from a given input. First, it counts the number of appearances of each number. Second, it calculates the counts of the adjacent groups, saving the largest each time it calculates it.

An advantage of this solution is that it leaves the original input unchanged.

A disadvantage is that this uses more memory than the original.

Bug

The original code only works if the solution has two separate numbers in it. Try {6, 10, 7, 7, 10, 8, 10, 10} for example. The correct answer is 4 for {10, 10, 10, 10} but the original code will still answer 3.