Leetcode : Monotonic Array

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] <= 105

Introduction

Hi CyberKnights, we will explore how to use the two-pointer technique to check if a given array is monotonic. We’ll discuss why we chose the two-pointer approach, the steps involved to solve the problem, visualize it with an example test case using an ASCII table, and finally, analyze the time complexity (TC) and space complexity (SC) of the code.

Why Two-Pointer Approach?

The two-pointer technique is a powerful tool for solving problems that involve iterating over arrays or lists. It can help simplify the code and make it more efficient. In this problem, the two-pointer approach allows us to compare elements from both ends of the array towards the center, ensuring that we can check for monotonicity efficiently.

Steps to Solve the Problem :

1. Initial Check: If the array has 0 or 1 element, it is considered monotonic.
2. Set Pointers: Initialize two pointers, left at the start and right at the end of the array.
3. Traverse Towards the Middle: Move the left and right pointers towards the center while comparing the elements to check for increasing or decreasing order.
4. Update Flags: Maintain two flags, increasing and decreasing, to keep track of whether the array is non-decreasing or non-increasing.
5. Midpoint Check: Once the pointers meet in the middle, ensure the middle element follows the series by comparing it with adjacent elements.
6. Return Result: If either the increasing or decreasing flag is True, the array is monotonic.

Let’s visualize the process with an example test case using an ASCII table.

Test Case: nums = [1, 2, 2, 3]

| Iteration | left | right | nums[left] | nums[right] | Compare nums[left] with nums[left + 1] | Compare nums[right] with nums[right - 1] | increasing | decreasing |
|-----------|------|-------|------------|-------------|----------------------------------------|------------------------------------------|------------|------------|
| Initial   | 0    | 3     | 1          | 3           | -                                      | -                                        | True       | True       |
| 1         | 0    | 3     | 1          | 3           | 1 <= 2                                 | 2 <= 3                                   | True       | False      |
| 2         | 1    | 2     | 2          | 2           | 2 <= 2                                 | 2 <= 3                                   | True       | False      |
| Midpoint  | 2    | 1     | 2          | 2           | (Left meets Right)                     | (Left meets Right)                       | True       | False      |

Time Complexity (TC)

• Initial Check: The check if len(nums) <= 1 is a constant time operation, O(1)O(1).
• Two-Pointer Traversal: The main part of the code is the while loop that runs while left < right. Each pointer (left and right) moves towards the middle. In each iteration, we perform a constant number of operations (comparisons and increments/decrements).

Since each pointer will traverse approximately half of the list, the overall traversal covers all elements in the list exactly once. Thus, the time complexity is O(n)O(n), where nn is the length of the list.

Space Complexity (SC)

• Constant Space: The space complexity is determined by the additional space used by the algorithm.
• Flags and Pointers: We use a constant number of variables: two boolean flags (increasing and decreasing), and two integer pointers (left and right). These variables do not scale with the size of the input list.

Therefore, the space complexity is O(1)O(1), which means we use constant space.

Final Code:

Quote : “Efficiency lies in simplicity — let the two-pointer technique guide your way to swift solutions”