Given an integer array of size n, find any three numbers

Question

Return any three descending numbers that appear sequentially in the input such that A[i] > A[j] > A[k] and i < j < k. Since problem description contains 'any', I could not unit test using JUnit.

I'm looking for request code review, optimizations and best practices.

final class DescendingTriplets {

    private final int high;
    private final int mid;
    private final int low;

    DescendingTriplets(int high, int mid, int low) {
        this.high = high; 
        this.mid = mid; 
        this.low = low;
    }

    public int getHigh() {
        return high;
    }

    public int getMid() {
        return mid;
    }

    public int getLow() {
        return low;
    }

    @Override
    public String toString() {
        return "high: " + high + " mid: " + mid + " low: "  + low;
    }
}

public final class ThreeDescending {

    private ThreeDescending() {}

    /**
     * This class is used to save high and mid values.
     */
    private static class State {
        int mid;
        int high;

        State(int low, int high) {
            this.mid = low;
            this.high = high;
        }
    }

    /**
     * Returns any three descending numbers in an array such that they appear one after other in the original sequence.
     * If such numbers dont exist then null is returned
     * 
     * @param a         the input array 
     * @return          object with three descending numbers in squence
     */
    public static DescendingTriplets getDescendingTriplets(int[] a) {
        if (a.length < 3) {
            throw new IllegalArgumentException("The arrays size should atleast be three");
        }

        /*
         * The current state of 'high' and 'mid' values to be used to compare 'min' against.
         */
        State stateCurrent = null;
        /*
         * The state of new 'high' and new 'mid' which we obtain as we travel the array.
         * Once both values(high and mid) are populated, we replace the stateCurrent with the stateInProgress.
         */
        State stateInProgress = null;

        int k = 0;
        // fetch the completedstate,
        for (int i = 0; i < a.length - 1; i++) {
            if (a[i] > a[i + 1]) {
                stateCurrent = new State(a[i + 1], a[i]);
                k = i + 1;
                break;
            }
        }

        for (int j = k + 1; j < a.length; j++) {
            // if smallest
            if (a[j] <= stateCurrent.mid) {
                return new DescendingTriplets(stateCurrent.high, stateCurrent.mid, a[j]);
            }

            // if greater than mid but less than high
            if (a[j] <= stateCurrent.high) {
                if (stateInProgress != null) {
                    stateCurrent = stateInProgress;
                }
                stateCurrent.mid = a[j];
            } else {
                // if greater than high
                if (stateInProgress != null) {
                    if (j > stateInProgress.high) {
                        stateInProgress.high = a[j];
                    } else {
                        stateInProgress.mid = a[j];
                        stateCurrent = stateInProgress;
                    }
                } else {
                    stateInProgress = new State(Integer.MIN_VALUE, a[j]);
                }
            }
        }

        return null;
    }

    public static void main(String[] args) {
        int[] a1 = {5, 14, 3, 2, 1};
        System.out.println(getDescendingTriplets(a1));

        int[] a2 = {4,7,5,1,3,8,9,6,2};
        System.out.println(getDescendingTriplets(a2));
    }
}

Answer 1

Return any three descending numbers that appear sequentially in the input such that A[i] > A[j] > A[k] and i < j < k. Since problem description contains 'any', I could not unit test using junits.

I think you could create inputs for tests where

• there is only one of this sequence and check that,
• there are only a couple of possible sequences and check that the returned one whether exists in the possible return values list or not,
• there isn't any valid sequence.

Answer 2

The code for this one baffles me. I believe you are doing much, much more work than necessary.

The nature of the problem is such that an \$O(n)\$ solution is the best time-complexity one. Your solution is in fact \$O(n)\$, but it is much, much more complicated than necessary.... two loops over the data? Lots of state conditions, and class objects, and conditionals.

Have you considered the simple function (returns the index of the first of the triples, or -1 if there is not one:

public static final int getDescendingTriple(int[] data) {
    int index = 2;
    while (index < data.length
            && (data[index - 2] >= data[index - 1] || data[index - 1] >= data[index]) {
        index++;
    }
    if (index >= data.length) {
        return -1;
    }
    return index - 2;
}

If you want to return the fancy DescendingTriplets then you can construct that from index (if >= 0).