An array is monotonic if it is either monotone increasing or monotone decreasing.
An array nums is monotone increasing if for all i <= j, nums[i] <= nums[j]. An array nums is monotone decreasing if for all i <= j, nums[i] >= nums[j].
Given an integer array nums, return true if the given array is monotonic, or false otherwise.
Example 1:
Input: nums = [1,2,2,3] Output: true
Example 2:
Input: nums = [6,5,4,4] Output: true
Example 3:
Input: nums = [1,3,2] Output: false
Constraints:
1 <= nums.length <= 105-105 <= nums[i] <= 105The goal of #896 Monotonic Array is to determine whether a given array is entirely non-increasing or non-decreasing. A monotonic array maintains a consistent order across all adjacent elements. Instead of sorting or using extra data structures, the key insight is to simply track the direction of comparisons while scanning the array once.
A common approach is to iterate through the array and compare each element with the next one. Maintain two logical indicators: one to check if the array can still be non-decreasing and another for non-increasing. If at any point a comparison violates one direction, you update the corresponding indicator. By the end of the traversal, if at least one direction remains valid, the array is monotonic.
This strategy works efficiently because it only requires a single pass through the array and uses constant extra space. The method avoids unnecessary sorting and keeps the solution optimal for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single Pass Direction Check | O(n) | O(1) |
Ashish Pratap Singh
This approach involves traversing the array and maintaining two flags: one for checking if the array elements are in increasing order and another for checking if they are in decreasing order. As we iterate through the array, we update these flags accordingly. If the array violates both conditions at any point, it is not monotonic.
Time Complexity: O(n), where n is the length of the array, since we perform a single traversal of the array.
Space Complexity: O(1), as no extra space is utilized apart from the flags.
1#include <stdbool.h>
2
3bool isMonotonic(int* nums, int numsSize) {
4 bool increasing = true, decreasing = true;
5 for (We loop through the array, starting from the second element. We check if the current element is greater than or less than the previous element and update the respective flags (decreasing and increasing). If both conditions are violated for any element pair, the function returns false. At the end of the loop, if either flag remains true, it implies the array is monotonic.
In this approach, we perform two separate passes to test for monotonic increase and monotonic decrease independently. The first pass checks for strictly increasing nature, and the second checks for strictly decreasing nature.
Time Complexity: O(n), two passes over the array which are separate checks.
Space Complexity: O(1), with no additional space used beyond flags.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, monotonic array concepts appear in coding interviews because they test basic array traversal and logical reasoning. While the exact problem may vary, similar patterns involving order checks and comparisons are common in technical interviews.
The optimal approach is to traverse the array once while checking whether it remains non-decreasing or non-increasing. By maintaining two direction flags during the scan, you can determine monotonicity efficiently without sorting. This results in O(n) time and O(1) space complexity.
No special data structure is required for this problem. A simple array traversal with a few boolean indicators is enough to track whether the order remains increasing or decreasing throughout the iteration.
You can compare each pair of adjacent elements while iterating through the array. Track whether the array still satisfies non-decreasing or non-increasing conditions. If at least one condition holds after the traversal, the array is monotonic.
The C solution uses two helper functions, isIncreasing and isDecreasing, which independently check if the array is monotone increasing or decreasing. The main function returns true if either condition holds true.