# Checking if numbers in array are sorted or reverse sorted

I would like to determine is an array of numbers, is always increasing (for all x, x+1 >= x) or always decreasing (for all x, x+1 =< x). If so return true. Another way to state the problem is, return true if the array is sorted or reverse sorted. Here is the code:

public static boolean isAlwaysIncreasingOrDecreasing(int[] arr) {
//check if decreasing
int previous = arr;
boolean decreasing = true;
for(int i = 1; i < arr.length; i++) {
if(previous < arr[i]) {
decreasing = false;
break;
}
previous = arr[i];
}

//check if increasing
int previous = arr;
boolean increasing = true;
for(int i = 1; i < arr.length; i++) {
if(previous > arr[i]) {
increasing = false;
break;
}
previous = arr[i];
}

//return true if always increasing or decreasing
if(decreasing || increasing) {
return false;
}

return true;
}


Any tips? Obviously duplicate values are allowed, so inputs such as 1,2,3,3,3,3....3,4,2,5,6 would be tricky.

I ask mainly out of curiosity, as the above solution would take at most 2 iterations through the array and I don't think it is possible to take less than 1, so it's not too bad :)

I'd write the following, seems cleaner to me. I wrote it in groovyConsole in Groovy, and adapted to Java, but I might have forgotten a semicolon or something, sorry if it doesn't compile.

public boolean isIncreasingOrDecreasing(int[] arr) {
boolean increasing = true, decreasing = true;
if (arr.length <= 2) {
return true;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i-1]) {
increasing = false;
}
if (arr[i] > arr[i-1]) {
decreasing = false;
}
if (!increasing && !decreasing) {
return false;
}
}
return true;
}

• First, you need to define rules for empty array and array of one element (I consider them "sorted").
• Second, array of 2 elements is always "sorted".
• Third, I like the possibility to return in the middle of function/method. If you don't like it (many people do not), you may do

if (!increasing || !decreasing) {
break;
}


and then

return increasing || decreasing;


Your version is slightly misnamed. It's actually isNonincreasingOrNondecreasing. It returns true for arrays where all the entries are the same value, which is neither increasing nor decreasing.

If you don't want to duplicate the checks, you can add a bit more logic.

public static boolean isNonincreasingOrNondecreasing(int[] sequence) {
// clear out equal entries from the beginning
int i = 1;
while (i < sequence.length && sequence[i - 1] == sequence[i]) {
i++;
}

// if there are no entries left, then it is nonincreasing and nondecreasing
if (i >= sequence.length) {
return true;
}

int previous = sequence[i - 1];
if (i < sequence.length && previous > sequence[i]) {
for (; i < sequence.length; i++) {
if (previous < sequence[i]) {
return false;
}

previous = sequence[i];
}

return true;
}

for (; i < sequence.length; i++) {
if (previous > sequence[i]) {
return false;
}

previous = sequence[i];
}

return true;
}


This version only loops once, although it has three loops coded. It only runs one loop over any section of the array.

It also gets rid of the Boolean variables. It can return immediately since it only gets to the loops once it already knows which one to test.

• Another good name might be isMonotonicSequence(). Jun 25 '16 at 14:34
• @JS1 Bug fixed. Jun 25 '16 at 21:41

You are traversing the array twice, it can be done in one. Since, the boolean variable once set false will remain false.

public static boolean isAlwaysIncreasingOrDecreasing(int[] sequence) {

int previous = arr;
//check if increasing
boolean increasing = true;
//check if decreasing
boolean decreasing = true;
for(int i = 1; i < arr.length; i++) {
if(previous < arr[i]) {
decreasing = false;
if( !increasing ){
break;
}
} else if(previous > arr[i]) {
increasing = false;
if( !decreasing ){
break;
}
}
previous = arr[i];
}
//return true if always increasing or decreasing
if( decreasing || increasing ) {
return false;
}
return true;
}