8
\$\begingroup\$

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

}

\$\endgroup\$
5
  • 6
    \$\begingroup\$ It has bugs. Result for an empty array should be true. Result for an array of all-equal values should also be true. \$\endgroup\$ Aug 19, 2020 at 21:40
  • 1
    \$\begingroup\$ @superbrain Can you justify why it should return true for the empty array? I am inclined to say that it should be UB or exception but I can't really make a solid argument about why that and not some other way... \$\endgroup\$
    – slepic
    Aug 20, 2020 at 4:22
  • 3
    \$\begingroup\$ @superbrain Do you base it on the fact that "for all (i,j) in an empty set" is always satisified? \$\endgroup\$
    – slepic
    Aug 20, 2020 at 4:26
  • 2
    \$\begingroup\$ @slepic Yes, that's why. \$\endgroup\$ Aug 20, 2020 at 11:04
  • 2
    \$\begingroup\$ The real property is forall i. A[i] <= A[i+1] (or >= for decreasing). For an empty or singleton array, the domain of i is empty, so it property is vacuously satisfied. \$\endgroup\$
    – chepner
    Aug 20, 2020 at 15:33

5 Answers 5

7
\$\begingroup\$

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;
        }
    }
\$\endgroup\$
4
  • \$\begingroup\$ To avoid nesting if statements, another minor improvement would be if (value == current) continue; \$\endgroup\$
    – DarkDust
    Aug 20, 2020 at 8:14
  • 4
    \$\begingroup\$ What? You don't think a length-1 array should be considered monotonic? To me, it sounds like it should definitely be considered monotonic. \$\endgroup\$
    – Alice Ryhl
    Aug 20, 2020 at 12:13
  • 5
    \$\begingroup\$ “[An array of length 1] is neither increasing nor decreasing.” It is both. \$\endgroup\$
    – Carsten S
    Aug 20, 2020 at 12:28
  • 2
    \$\begingroup\$ The monotonicity property vacuously holds for a single-element array, because there is no second element to invalidate it. \$\endgroup\$
    – chepner
    Aug 20, 2020 at 15:30
5
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Due to integer overflow, { 0, Integer.MAX_VALUE, Integer.MIN_VALUE } would erroneously test as monotonic. \$\endgroup\$
    – AJNeufeld
    Aug 20, 2020 at 13:25
  • 1
    \$\begingroup\$ I fixed the integer overflow. \$\endgroup\$
    – Alice Ryhl
    Aug 20, 2020 at 17:02
  • 2
    \$\begingroup\$ This new version might not work, as compare can return any positive or negative result. So your -sign == lastSign check isn't safe. \$\endgroup\$ Aug 20, 2020 at 17:06
  • 2
    \$\begingroup\$ Interesting. I initially wrote out the three-way case, but my IDE said it could be replaced with Integer.compare. It's annoying that they don't guarantee this behaviour for integer comparison. \$\endgroup\$
    – Alice Ryhl
    Aug 20, 2020 at 17:09
  • 2
    \$\begingroup\$ Yeah, I agree it's annoying. I think they really only return 0, 1 or -1, just don't guarantee it. I think your newest version is correct, but it was a little prettier before. I'm almost sorry I pointed this issue out :-) \$\endgroup\$ Aug 20, 2020 at 17:24
4
\$\begingroup\$
  • 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:]))
\$\endgroup\$
4
  • \$\begingroup\$ Your idea of looking at the last element to determine direction is interesting, but might touch a cache line that didn't need to be touched if the early part of the array is enough to prove it non-monotonic. But is simplifies startup so either strategy could be better depending on the inputs. (Assuming you're optimizing for speed, as discussed in another comment thread.) But yes, 2 separate loops in if/else is efficient and readable. \$\endgroup\$ Aug 21, 2020 at 0:40
  • \$\begingroup\$ @PeterCordes Well, but it's only one cache-line. And the early-part argument is for best-case scenarios. I'm more interested in worst-case, i.e., where times matter more. Like very long arrays that are monotonic. I don't care much about super-duper-fast vs "just" super-fast in best-case scenarios :-) \$\endgroup\$ Aug 21, 2020 at 1:15
  • \$\begingroup\$ It's only one cache line, but if it's cold in cache that could stall the pipeline for long enough that it could have already finished looking at the first few cache lines of the array. I'm picturing a case where the first few cache lines of the array are hot in cache, but the end isn't. (Although if it was just written first to last, that's opposite). The separate loops only have a control dependency, not a data dependency, on that last line, so if the branch predicted correctly all that work can be already done under the latency of that cache miss. But if it mispredicts, it has to restart. \$\endgroup\$ Aug 21, 2020 at 1:55
  • \$\begingroup\$ Agreed for most cases it's fine, and doesn't impact the worst-case large monotonic array time by more than a couple hundred clock cycles in the worst case, negligible compared to the difference between SIMD and scalar code for this, especially on x86 where branching on SIMD compare results can be done efficiently. (Unlike on some ARM) \$\endgroup\$ Aug 21, 2020 at 1:58
3
\$\begingroup\$

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.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ Regarding the function name: as the second parameter is a BiPredicate and predicates use the standard method name test(), I'd go for pairwiseTest(int[] numbers. BiPredicate<Integer, Integer> predicate) or - moving away from the primitives <T> pairwiseTest(List<T> objects, BiPredicate<T, T> predicate). \$\endgroup\$
    – mtj
    Aug 20, 2020 at 10:52
  • 1
    \$\begingroup\$ Re "a couple of duplicate checks": on most inputs one or the other will indeed bail out quickly, but in the worst case it's twice the number of checks, for example 111111111111110. \$\endgroup\$
    – Thomas
    Aug 20, 2020 at 12:51
  • \$\begingroup\$ @Thomas Well the OP's solution has up to three checks at every element, while this has at worst two. (But yes, it's worse than the optimal solution, which only needs one check at every element.) \$\endgroup\$ Aug 20, 2020 at 15:17
  • \$\begingroup\$ I combined our answers to this. Do you see a way to make that nicer? (I'm not much of a Java guy.) \$\endgroup\$ Aug 20, 2020 at 18:15
  • 1
    \$\begingroup\$ @superbrain: If you were serious about optimizing this for speed without a lot of care for keeping the source compact, you'd probably start by scanning for an element not equal to the first element (can be done very efficiently with SIMD), then depending on that one compare, enter one of two loops that only check for a single ordering. (Hard to vectorize with SIMD, but cheap with scalar so should compile to a loop with just a couple asm instructions that hopefully checks 1 element per clock cycle.) So one loop to start, possible early return, then if/else with a loop in each branch. \$\endgroup\$ Aug 21, 2020 at 0:34
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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