896. Monotonic Array
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 57.9%
Problem Breakdown
The problem asks us to determine whether an array is monotonic, meaning it is either entirely non-increasing or non-decreasing. The input is a single integer array A, and the output should be a boolean value: true if the array is monotonic, and false otherwise.
Inputs:
- An array of integers
Awith length between 1 and 50,000. - Each element in the array can range from -100,000 to 100,000.
Outputs:
- A boolean value indicating whether the array is monotonic.
Implicit Constraints or Tricky Edge Cases:
- An empty array (length 0) is trivially monotonic.
- Arrays with a single element are also trivially monotonic.
- Arrays with all identical elements are monotonic.
- The presence of negative numbers does not affect monotonicity.
Intuition
A brute-force approach would involve checking each pair of consecutive elements to see if the array is either non-decreasing or non-increasing. This would require two passes through the array, resulting in a time complexity of O(n). However, we can optimize this by determining the direction (increasing or decreasing) during the first pass and then confirming that the entire array follows that direction.
The key insight is to determine the direction of monotonicity early on and validate it throughout the array. This approach ensures that we only make a single pass through the array, reducing the time complexity to O(n).
Approach
-
Determine Initial Direction:
- If the first element is less than or equal to the last element, assume the array is non-decreasing.
- Otherwise, assume the array is non-increasing.
-
Validate Monotonicity:
- Iterate through the array and check if each element adheres to the assumed direction:
- For a non-decreasing array, ensure that each element is less than or equal to the next.
- For a non-increasing array, ensure that each element is greater than or equal to the next.
- Iterate through the array and check if each element adheres to the assumed direction:
-
Return Result:
- If all elements adhere to the assumed direction, return
true. - Otherwise, return
false.
- If all elements adhere to the assumed direction, return
Complexity Analysis
- Time Complexity: O(n), where n is the length of the array. We make a single pass through the array.
- Space Complexity: O(1). We use only a constant amount of extra space.
Solution
def isMonotonic(A):
if len(A) <= 1:
return True
# Determine initial direction
increasing = A[0] <= A[-1]
for i in range(len(A) - 1):
if (increasing and A[i] > A[i + 1]) or (not increasing and A[i] < A[i + 1]):
return False
return True
Edge Cases Handled
- Empty Array: The function returns
truefor an empty array since it trivially satisfies the monotonic condition. - Single Element Array: The function returns
truefor a single-element array as it is trivially monotonic. - All Identical Elements: The function correctly identifies arrays with all identical elements as monotonic.
- Negative Numbers: The presence of negative numbers does not affect the logic, as the comparison operators work correctly with them.