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));
 }
}

• Vogel612: sequentially meaning that k = j-1, j = i-1?
• rolfl: It appears that the statement Return any three descending numbers that appear sequentially in the input is ambiguous, and can be interpreted multiple ways. The answer I gave does one interpretation of that, but your code does a different interpretation... Down-vote applied.
• JavaDeveloper: sequentially - wrt my question - does not mean consecutive. Hope that solves doubts.
• Red Alert: your algorithm is incorrect. Consider the array {5, 4, 6, 7, 6, 5}. Your program returns 6, 7, 6, which is not descending.

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.

• amon: Even simpler than enumerating all possible sequences per input, an unit test could assert 0 <= i < j < k < A.length and A[i] > A[j] > A[k] in the case of one or more possible sequences.
• palacsint: @amon: It should also check the returned values exist in the input array.

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

• Joffrey: I don't think your solution answers the problem. I agree the OP is unclear on this aspect, but what I understood is that the indices don't have to follow each other. I believe the OP just wants i < j < k.
• rolfl: @Joffrey - I think you may be right. The question is ambiguous (the description and implementation do different things in the asker's question).
• Joffrey: agreed that it is ambiguous, let's wait for the OP to answer the comments.