Check if array is monotonic i.e either monotone increasing or monotone decreasing

Question

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

public class MonotonicArray {

    public boolean IsMonotonic(int[] numbers) {
        if (numbers == null  || numbers.length == 0) {
            return false;
        }

        if (numbers.length == 1) {
            return true;
        }

        boolean increasing = false;
        boolean decreasing = false;

        for (int index = 0; index < numbers.length - 1; index++) {

            if (numbers[index + 1] == numbers[index]){
                continue;
            }

            if (numbers[index + 1] > numbers[index]) {
                if (!decreasing) {
                    increasing = true;
                } else {
                    return false;
                }
            }

            else  {
                if (!increasing) {
                    decreasing = true;
                } else {
                    return false;
                }

            }

        }
        return increasing || decreasing;
    }
}

Test cases:

class MonotonicArrayTest extends MonotonicArray {

@org.junit.jupiter.api.Test
void isMonotonic1() {

    int[] array =  new int[]{1,2,3};
   assertEquals(true,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic2() {

    int[] array =  new int[]{-1,-2,-3};
    assertEquals(true,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic3() {

    int[] array =  new int[]{1,2,1};
    assertEquals(false,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic4() {
    int[] array =  new int[]{-1,2,-9};
    assertEquals(false,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic5() {

    int[] array =  new int[]{9,3,2};
    assertEquals(true,IsMonotonic(array));
}

@org.junit.jupiter.api.Test
void isMonotonic6() {
    int[] array =  new int[]{};
    assertEquals(false,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic7() {
    int[] array =  new int[]{1};
    assertEquals(true,IsMonotonic(array));
}


@org.junit.jupiter.api.Test
void isMonotonic8() {
    int[] array =  new int[]{9,7,5,4,8,10};
    assertEquals(false,IsMonotonic(array));
}

@org.junit.jupiter.api.Test
void isMonotonic9() {
    int[] array =  new int[]{1,1,2,3};
    assertEquals(true,IsMonotonic(array));
}

@org.junit.jupiter.api.Test
void isMonotonic10() {
    int[] array =  new int[]{1,1,0,-1};
    assertEquals(true,IsMonotonic(array));
}

}

Answer 1

static

IsMonotonic(...) does not need an instance of the MonotonicArray class to function, therefore it should be static.

Consistency

You special case an array of length 1 as monotonic. Is it really? It is neither increasing nor decreasing.

What about IsMonotonic(new int[]{1, 1, 1, 1})? Seems to me that should be true, but it will return false. Definitely should be added as a test case. And if it should return true, then ...

Optimization

... checking for length 1 is too restrictive. Any length 2 array will always be monotonic as well. Perhaps:

    if (numbers.length == 1) {
        return true;
    }

should be:

    if (numbers.length <= 2) {
        return true;
    }

Looping

This is ugly. Will Java optimize the numbers.length - 1 calculation as a constant?

    for (int index = 0; index < numbers.length - 1; index++) {

        if (numbers[index + 1] == numbers[index]){
            continue;
        }
        ...

It may be better to use Java's enhanced for loop to extract numbers, and rely on monotonic behaviour allowing equality to handle the first element:

    int current = numbers[0];
    for(int value : numbers) {
        if (value != current) {
           if (value < current) {
              ...
           } else {
              ...
           }
           current = value;
        }
    }

Answer 2

The loop is rather complicated. It is generally better to use simpler logic if possible, as that makes the loop simpler to reason about. For example, you can use Integer.compare to remove a lot of the logic from your loop.

public static boolean IsMonotonic(int[] numbers) {
    int lastCmp = 0;

    for (int i = 1; i < numbers.length; i++) {
        int cmp = Integer.compare(numbers[i], numbers[i - 1]);

        if (lastCmp == 0) {
            lastCmp = cmp;
        } else if (cmp != 0 && ((cmp > 0) != (lastCmp > 0))) {
            return false;
        }
    }

    return true;
}

In each iteration the cmp variable is zero if the two numbers are equal, and either positive or negative depending on whether there was an increase or decrease.

When lastCmp is zero, we have yet to see an increase or decrease, i.e. all integers have been equal. If lastCmp is nonzero, then we have seen either an increase or decrease. If the sequence is not monotonic, we will eventually reach a pair that moved in the opposite direction from the first change, which is what the second condition will detect.

If the list is shorter than two elements, then the loop doesn't run at all, and just returns true.

Answer 3

• You might get better performance and simplicity if you make up your mind right away: Comparing the first value with the last value immediately tells you which one of increasing/decreasing/constant you should check.

• What you should do for null depends on the contract. This problem is on LeetCode, where you're even guaranteed that the array will have at least one element, so there you wouldn't need to cover null or an empty array. You "chose"(?) to return false, but you could just as well argue for true, since "no array" seems rather similar to "no elements", for which the correct answer is btw true, not false.

Here's one that uses a first-vs-last check (although I included "constant" in "increasing") and which puts the burden on the caller to provide a reasonable input (i.e., not null). I think it's better to have the user get an error than to silently pretend nothing's wrong.

    public boolean isMonotonic(int[] numbers) {
        int last = numbers.length - 1;
        if (last >= 0 && numbers[0] <= numbers[last]) {
            for (int i = 0; i < last; i++) {
                if (numbers[i] > numbers[i+1]) {
                    return false;
                }
            }
        } else {
            for (int i = 0; i < last; i++) {
                if (numbers[i] < numbers[i+1]) {
                    return false;
                }
            }
        }
        return true;
    }

A BiPredicate version inspired by RoToRa's answer. This one distinguishes all three cases, as the BiPredicate avoids code duplication:

    public boolean isMonotonic(int[] numbers) {
        int n = numbers.length;
        if (n <= 2) {
            return true;
        }
        BiPredicate<Integer, Integer> fail =
            numbers[0] < numbers[n-1] ? (a, b) -> a > b :
            numbers[0] > numbers[n-1] ? (a, b) -> a < b :
                                        (a, b) -> a != b;
        for (int i = 1; i < n; i++)
            if (fail.test(numbers[i-1], numbers[i]))
                return false;
        return true;
    }

Python version, just for fun :-)

from operator import eq, le, ge

def isMonotonic(numbers):
    first, last = numbers[:1], numbers[-1:]
    check = eq if first == last else le if first < last else ge
    return all(map(check, numbers, numbers[1:]))

Answer 4

I'm not a big fan of having a single monolithic function that indiscriminately checks for both increasing and decreasing monotony. In most practical scenarios I would imagine you'd probably need to know if it's increasing or decreasing.

Based on that I'd specifically define:

public static boolean isMonotonic(int[] numbers) {
   return isMonotonicIncreasing(numbers) || isMonotonicDecreasing(numbers);
}

public static boolean isMonotonicIncreasing(int[] numbers) {
   return isXXX(numbers, (a, b) -> a <= b); // Not sure how to call this method
}

Sure, there will be a couple of duplicate checks, but in the end IMO the code will be better structured, better readable and more re-usable.

Answer 5

If you accept the consistency remark of @AJNeufeld (so that [1] being monotonic indicates that [1,1,1] may rather be monotonic too) and put the other remark about [x,y] being monotonic again, you may find it easier to have true-s by default and recognize when the array is not monotonic:

public static boolean IsMonotonic(int[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return false;
    }
    boolean inc_or_const = true;
    boolean dec_or_const = true;
    int prev = numbers[0];
    for (int curr : numbers) {
        if (curr < prev) {
            inc_or_const = false;
        } else if (curr > prev) {
            dec_or_const = false;
        }
        prev = curr;
    }
    return inc_or_const || dec_or_const;
}

Of course it looks that tidy only without short-circuiting, after that this will have a very similar structure to your original code again:

public static boolean IsMonotonic(int[] numbers) {
    if (numbers == null || numbers.length == 0) {
        return false;
    }
    boolean inc_or_const = true;
    boolean dec_or_const = true;
    int prev = numbers[0];
    for (int i = 1; i < numbers.length; i++) {
        int curr = numbers[i];
        if (curr < prev) {
            inc_or_const = false;
            if (!dec_or_const) {
                return false;
            }
        } else if (curr > prev) {
            dec_or_const = false;
            if (!inc_or_const) {
                return false;
            }
        }
        prev = curr;
    }
    return true;
}

Here I went back to indexed access on the basis of my dislike against comparing the first element to itself (what the for(:) variant does). Also note that here, because of the short-circuit returns, completion of the loop means that the array is monotonic for sure. Plus the remark about the hazard of having numbers.length-1 in the loop condition has been applied too.