3
\$\begingroup\$

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[0];
        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[0];
        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 :)

\$\endgroup\$
3
\$\begingroup\$

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;
    
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Another good name might be isMonotonicSequence(). \$\endgroup\$ – 200_success Jun 25 '16 at 14:34
  • \$\begingroup\$ @JS1 Bug fixed. \$\endgroup\$ – mdfst13 Jun 25 '16 at 21:41
2
\$\begingroup\$

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[0];
    //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;
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.