Leetcode – Monotonic Array Solution in Python

Spread the love

The Monotonic Array problem is one of the popular coding challenges available on Leetcode. It checks a coder’s understanding of array manipulation, logical reasoning, and the ability to write clean and efficient code. In this article, we will delve deep into understanding the problem, formulating a strategy, and implementing solutions in Python.

Overview:

  1. Understanding the Problem Statement
  2. Intuitive Approach
  3. Optimal Approach
  4. Implementation in Python
  5. Analyzing Time and Space Complexity
  6. Conclusion

1. Understanding the Problem Statement

Problem:

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

Given an array A consisting of n integers, write a function to return True if and only if the given array is Monotonic.

Example:

Input: [1,2,2,3]
Output: True

Input: [6,5,4,4]
Output: True

Input: [1,3,2]
Output: False

2. Intuitive Approach

The simplest way to approach this problem is to check two conditions:

  1. Whether the array is strictly increasing or non-decreasing.
  2. Whether the array is strictly decreasing or non-increasing.

If either of these conditions is True, then the array is monotonic.

3. Optimal Approach

Instead of running two separate loops to check for increasing and decreasing arrays, you can determine the nature of the array in a single pass.

  1. Iterate through the array.
  2. Use two flags: is_increasing and is_decreasing.
  3. Update the flags based on the comparison of adjacent elements.
  4. If both flags are True at any point, return False.
  5. Else, return True.

4. Implementation in Python

def isMonotonic(A):
    is_increasing = is_decreasing = True
    
    for i in range(1, len(A)):
        if A[i] > A[i-1]:
            is_decreasing = False
        elif A[i] < A[i-1]:
            is_increasing = False
            
    return is_increasing or is_decreasing

You can test the function with the examples provided:

print(isMonotonic([1,2,2,3]))  # True
print(isMonotonic([6,5,4,4]))  # True
print(isMonotonic([1,3,2]))    # False

5. Analyzing Time and Space Complexity

Time Complexity: Since we are traversing the array once, the time complexity is O(n), where n is the number of elements in the array.

Space Complexity: We are using a constant amount of space irrespective of the input array size. Therefore, the space complexity is O(1).

6. Conclusion

The Monotonic Array problem on Leetcode tests a coder’s ability to think logically and optimize solutions. The key to solving it efficiently is understanding the nature of monotonic sequences and applying that knowledge to traverse the array optimally. By practicing such problems, one can enhance problem-solving skills and become adept at handling array-related challenges.

Leave a Reply