algoadvance

Leetcode 896. Monotonic Array

Problem Statement

Given an array A of integers, return true if and only if the array is monotonic.

An array is monotonic if it is either monotone increasing or monotone decreasing.

Clarifying Questions

  1. What should be the output when the array is empty?
    • Since an empty array can be considered trivially monotonic, the output should be true.
  2. Can the array contain duplicates?
    • Yes, the array can contain duplicates.
  3. What is the range of the array length and the element values?
    • The array length can range from 0 to (10^5).
    • The element values are integers within the standard integer range.

Strategy

We need to check if the given array is either monotone increasing or monotone decreasing. We can do this in one pass by maintaining two flags increasing and decreasing. We will iterate through the array:

  1. Initialize increasing and decreasing to true.
  2. Iterate through the array from the second element:
    • If we find an element where A[i] < A[i-1], set increasing to false.
    • If we find an element where A[i] > A[i-1], set decreasing to false.
  3. If at the end, either increasing or decreasing is still true, then the array is monotonic.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool isMonotonic(vector<int>& A) {
        if (A.empty()) return true;

        bool increasing = true;
        bool decreasing = true;

        for (int i = 1; i < A.size(); ++i) {
            if (A[i] > A[i - 1])
                decreasing = false;
            if (A[i] < A[i - 1])
                increasing = false;
        }

        return increasing || decreasing;
    }
};

Time Complexity

The time complexity of this solution is (O(n)), where (n) is the number of elements in the array. This is because we only need to make a single pass through the array to determine if it is monotonic.

The space complexity is (O(1)) because we are using only a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI