Determine whether an int slice is monotonic in O(n)
Implement isMonotonic(in) returning true if the slice is monotonic — either non-decreasing everywhere or non-increasing everywhere. Requirement: a single pass, O(n) time, O(1) extra space. Examples: {1,7} → true; {1,1} → true; {3,3,1} → true; {9,5,1} → true; {23,5,23} → false.
func isMonotonic(in []int) bool {
// your code here
return false
}Write the implementation.
Track two booleans, isUp and isDown, both true at the start. Walk adjacent pairs once: keep isUp true only while in[i-1] <= in[i], and isDown true only while in[i-1] >= in[i]. Return isUp || isDown. A flat run keeps both true, and any direction change clears one. It is O(n) time, O(1) space, single pass.
- ✗Locking in a direction from the first pair instead of tracking both flags
- ✗Treating equal adjacent elements as breaking monotonicity
- ✗Deciding from only the endpoints, missing a dip in the middle
- →How would you change it to require strict monotonicity (no equal neighbours)?
- →Can you early-return as soon as both flags become false?
Solution
Two flags track both allowed trends at once. No reallocation, no sort.
func isMonotonic(in []int) bool {
isUp, isDown := true, true
for i := 1; i < len(in); i++ {
isDown = isDown && in[i-1] >= in[i]
isUp = isUp && in[i-1] <= in[i]
}
return isUp || isDown
}
// {3,3,1} -> true {23,5,23} -> falseisUp stays true while the sequence never decreases; isDown stays true while it never increases. Equal neighbours (the >= and <= are non-strict) keep both flags, so {1,1} and {3,3,1} are monotonic. If there is both a rise and a fall, both flags clear and the result is false.
⚠️ Deciding from only in[0] and in[len-1] is wrong: {1,5,1} has equal ends but is not monotonic.
