Leetcode 896: Monotonic Array
An array is said to be monotonic if it is either monotonically increasing or monotonically decreasing. A monotonically increasing array is one where each element is greater than or equal to the previous one, and a monotonically decreasing array is one where each element is less than or equal to the previous one. Given an integer array, return true if the array is monotonic, and false otherwise.
Problem
Approach
Steps
Complexity
Input: You are given an array of integers, nums, and you need to determine if the array is monotonic.
Example: Input: nums = [3, 3, 4, 5]
Constraints:
• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
Output: Return a boolean value, true if the array is monotonic, and false otherwise.
Example: Output: true
Constraints:
• The output is either true or false based on whether the array is monotonic.
Goal: The goal is to check whether the given array is either monotonically increasing or decreasing.
Steps:
• 1. Initialize two boolean variables, inc and dec, to true. These will track whether the array is monotonically increasing or decreasing.
• 2. Traverse the array and check if each pair of adjacent elements follows the increasing or decreasing pattern.
• 3. If any element fails to maintain the increasing pattern, set inc to false; if it fails to maintain the decreasing pattern, set dec to false.
• 4. After traversing the array, if either inc or dec remains true, return true. Otherwise, return false.
Goal: The problem involves checking if the array is monotonic within the given constraints of the array size and element range.
Steps:
• The length of nums will be between 1 and 100,000.
• The values in nums will range from -100,000 to 100,000.
Assumptions:
• The input array will contain at least one element.
• The array may contain negative, zero, or positive values.
• Input: Input: nums = [3, 3, 4, 5]
• Explanation: This array is monotonically increasing because each element is greater than or equal to the one before it.
• Input: Input: nums = [5, 4, 4, 3]
• Explanation: This array is monotonically decreasing because each element is less than or equal to the one before it.
• Input: Input: nums = [1, 3, 2]
• Explanation: This array is neither increasing nor decreasing, so the output is false.
Approach: To determine if the array is monotonic, we check if it is either monotonically increasing or decreasing by comparing adjacent elements. This can be done efficiently in a single pass through the array.
Observations:
• We need to ensure that we only traverse the array once to keep the solution efficient.
• The problem can be solved by maintaining two boolean variables to track if the array is increasing or decreasing.
• Using a single pass and two boolean flags allows us to solve this problem in linear time.
Steps:
• 1. Initialize two boolean flags, inc and dec, both set to true.
• 2. Loop through the array starting from the second element.
• 3. For each pair of consecutive elements, check if the array is increasing or decreasing and update the flags accordingly.
• 4. At the end of the loop, return true if either inc or dec is true, otherwise return false.
Empty Inputs:
• If the array contains only one element, it is trivially monotonic.
Large Inputs:
• For large arrays, the solution should still work efficiently within the time constraints.
Special Values:
• Arrays with all identical elements are considered monotonic.
Constraints:
• The solution must handle large inputs up to the constraint limits efficiently.
bool isMonotonic(vector<int> A) {
bool inc = true, dec = true;
for (int i = 1; i < A.size(); ++i)
inc &= A[i - 1] <= A[i], dec &= A[i - 1] >= A[i];
return inc || dec;
}
1 : Function Declaration
bool isMonotonic(vector<int> A) {
This line declares a function `isMonotonic` that takes a vector of integers `A` as input and returns a boolean value.
2 : Variable Initialization
bool inc = true, dec = true;
Two boolean variables `inc` and `dec` are initialized to `true`. These will be used to track whether the array is non-decreasing (`inc`) or non-increasing (`dec`).
3 : Loop Initialization
for (int i = 1; i < A.size(); ++i)
A `for` loop is started, iterating through the vector `A` starting from index 1. This loop checks the relationship between consecutive elements.
4 : Condition Update
inc &= A[i - 1] <= A[i], dec &= A[i - 1] >= A[i];
The boolean variables `inc` and `dec` are updated. The `&=` operator ensures that `inc` remains true if each pair of consecutive elements is non-decreasing, and `dec` remains true if the elements are non-increasing.
5 : Return Statement
return inc || dec;
The function returns `true` if either `inc` or `dec` is true, meaning the array is monotonic (non-decreasing or non-increasing).
6 : Function End
}
The function ends here.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we traverse the array once, where n is the number of elements in the array.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) because we only use a constant amount of extra space to store the two boolean flags.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus