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));
}
}
k = j-1, j = i-1
? \$\endgroup\${5, 4, 6, 7, 6, 5}
. Your program returns6, 7, 6
, which is not descending. \$\endgroup\$