Jobs

Interviews

Discussions

Monotonic Array

Easy

Asked by:

More companies

50 views

Topics:

Arrays

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵

Try coding it in LeetCode

Monotonic Array

Easy

Asked by:

50 views

Topics:

Arrays

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 <= 10⁵
-10⁵ <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain negative numbers, zeros, or floating-point numbers?
What is the expected behavior for an empty array or an array with only one element?
If the array is both monotonically increasing and monotonically decreasing (e.g., all elements are the same), should I return true or false?
Are there any constraints on the size of the input array (e.g., maximum number of elements)?
Can I assume the input array will always be a valid array (i.e., not null or undefined)?

Brute Force Solution

Approach

The brute force approach determines if a list of numbers is monotonic by checking every possible scenario. It involves checking if the list is either entirely non-decreasing or entirely non-increasing. We can determine this by checking all possible pairs of numbers in the list.

Here's how the algorithm would work step-by-step:

First, assume the list is non-decreasing. This means each number should be greater than or equal to the number before it.
Check every consecutive pair of numbers in the list. If you find any pair where the first number is bigger than the second, the list can't be entirely non-decreasing.
If you get through the entire list without finding such a pair, then the list IS non-decreasing. You've successfully found one possibility.
Next, assume the list is non-increasing. This means each number should be less than or equal to the number before it.
Again, check every consecutive pair of numbers in the list. This time, if you find any pair where the first number is smaller than the second, the list can't be entirely non-increasing.
If you get through the entire list without finding such a pair, then the list IS non-increasing. You've successfully found another possibility.
If either the list is entirely non-decreasing or entirely non-increasing (or both!), then the original list is monotonic.

Code Implementation

def is_monotonic(numbers):
    is_non_decreasing = True
    # Check if the list is non-decreasing
    for index in range(1, len(numbers)):

        if numbers[index - 1] > numbers[index]:
            is_non_decreasing = False
            break

    is_non_increasing = True
    # Check if the list is non-increasing
    for index in range(1, len(numbers)):

        if numbers[index - 1] < numbers[index]:
            is_non_increasing = False
            break

    # The list is monotonic if either non-decreasing or non-increasing is true
    return is_non_decreasing or is_non_increasing

Big(O) Analysis

Time Complexity

O(n) – The proposed solution iterates through the input array twice, once to check for non-decreasing order and once to check for non-increasing order. Each iteration involves comparing consecutive pairs of elements. Since each element is visited a constant number of times (twice), the time complexity grows linearly with the input size n. Therefore, the overall time complexity is O(n).

Space Complexity

O(1) – The provided algorithm only uses a few boolean variables to track whether the array is non-decreasing or non-increasing. The number of these variables does not depend on the size of the input array, N. Therefore, the auxiliary space used is constant regardless of the input size. This results in a space complexity of O(1).

Optimal Solution

Approach

To check if a sequence is monotonic (either always increasing or always decreasing), we can avoid checking every single pair of numbers. The key is to determine the direction of the sequence early and then confirm that it stays consistent with that direction.

Here's how the algorithm would work step-by-step:

First, figure out if the sequence is generally increasing or decreasing by looking at the first few numbers. If it's hard to tell right away, skip over any equal numbers until you find a clear trend.
Once you think you know the direction, go through the rest of the numbers. Make sure each number follows the established trend. If you find any number that goes against the trend, you know the sequence isn't monotonic.
If you make it to the end without finding any numbers that break the trend, the sequence is monotonic.

Code Implementation

def is_monotonic(sequence):
    sequence_length = len(sequence)
    if sequence_length <= 2:
        return True

    index = 0
    while index < sequence_length - 1 and sequence[index] == sequence[index + 1]:
        index += 1

    if index == sequence_length - 1:
        return True

    is_increasing = sequence[index] < sequence[index + 1]

    # Determine overall trend (increasing or decreasing)
    
    for i in range(index + 1, sequence_length - 1):
        if is_increasing:
            if sequence[i] > sequence[i + 1]:
                return False
        else:
            if sequence[i] < sequence[i + 1]:
                return False

    # Ensure trend consistency.
    
    return True

def is_monotonic_two(nums):
    increasing = True
    decreasing = True

    # Check both increasing and decreasing
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            increasing = False
        if nums[i] < nums[i+1]:
            decreasing = False

    # Return if it is either increasing or decreasing
    return increasing or decreasing

def is_monotonic_one_pass(array):
    direction = 0
    # Need to check the direction for increase or decrease.
    for i in range(1, len(array)): 
        if array[i] - array[i - 1] > 0:
            current_direction = 1
        elif array[i] - array[i - 1] < 0:
            current_direction = -1
        else:
            current_direction = 0

        if direction == 0:
            direction = current_direction
        elif direction != current_direction and current_direction != 0:
            # Ensure same direction
            return False
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n at most twice. The first iteration identifies the trend (increasing or decreasing), potentially skipping equal elements. The second iteration confirms the trend's consistency by comparing adjacent elements. Therefore, the number of operations is proportional to the size of the array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm determines the direction (increasing or decreasing) and then iterates through the input array. It does not create any auxiliary data structures such as new arrays, lists, or hash maps to store intermediate results or visited elements. The only memory used is for a few variables like the index and the direction flag, which take up constant space regardless of the input array's size (N). Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty or null input array	Return true because an empty array can be considered both monotonically increasing and monotonically decreasing.
Array with a single element	Return true, as a single element is always monotonic.
Array with all identical elements	The algorithm should correctly identify this as monotonic (both increasing and decreasing).
Array with strictly increasing values	Algorithm must correctly identify it as monotonically increasing.
Array with strictly decreasing values	Algorithm must correctly identify it as monotonically decreasing.
Array with mixed increasing and decreasing segments	The algorithm should correctly identify this as non-monotonic.
Array with duplicate consecutive elements in increasing or decreasing order	Algorithm should handle these gracefully, maintaining the monotonic property if the increasing/decreasing order is consistent.
Large array sizes to test performance	The algorithm should ideally have O(n) time complexity, performing a single pass through the array efficiently.

Empty or null input array

How to Handle:

Return true because an empty array can be considered both monotonically increasing and monotonically decreasing.

Array with a single element

How to Handle:

Return true, as a single element is always monotonic.

Array with all identical elements

How to Handle:

The algorithm should correctly identify this as monotonic (both increasing and decreasing).

Array with strictly increasing values

How to Handle:

Algorithm must correctly identify it as monotonically increasing.

Array with strictly decreasing values

How to Handle:

Algorithm must correctly identify it as monotonically decreasing.

Array with mixed increasing and decreasing segments

How to Handle:

The algorithm should correctly identify this as non-monotonic.

Array with duplicate consecutive elements in increasing or decreasing order

How to Handle:

Algorithm should handle these gracefully, maintaining the monotonic property if the increasing/decreasing order is consistent.

Large array sizes to test performance

How to Handle:

The algorithm should ideally have O(n) time complexity, performing a single pass through the array efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input array contain negative numbers, zeros, or floating-point numbers?
What is the expected behavior for an empty array or an array with only one element?
If the array is both monotonically increasing and monotonically decreasing (e.g., all elements are the same), should I return true or false?
Are there any constraints on the size of the input array (e.g., maximum number of elements)?
Can I assume the input array will always be a valid array (i.e., not null or undefined)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, assume the list is non-decreasing. This means each number should be greater than or equal to the number before it.
Check every consecutive pair of numbers in the list. If you find any pair where the first number is bigger than the second, the list can't be entirely non-decreasing.
If you get through the entire list without finding such a pair, then the list IS non-decreasing. You've successfully found one possibility.
Next, assume the list is non-increasing. This means each number should be less than or equal to the number before it.
Again, check every consecutive pair of numbers in the list. This time, if you find any pair where the first number is smaller than the second, the list can't be entirely non-increasing.
If you get through the entire list without finding such a pair, then the list IS non-increasing. You've successfully found another possibility.
If either the list is entirely non-decreasing or entirely non-increasing (or both!), then the original list is monotonic.

Code Implementation

def is_monotonic(numbers):
    is_non_decreasing = True
    # Check if the list is non-decreasing
    for index in range(1, len(numbers)):

        if numbers[index - 1] > numbers[index]:
            is_non_decreasing = False
            break

    is_non_increasing = True
    # Check if the list is non-increasing
    for index in range(1, len(numbers)):

        if numbers[index - 1] < numbers[index]:
            is_non_increasing = False
            break

    # The list is monotonic if either non-decreasing or non-increasing is true
    return is_non_decreasing or is_non_increasing

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out if the sequence is generally increasing or decreasing by looking at the first few numbers. If it's hard to tell right away, skip over any equal numbers until you find a clear trend.
Once you think you know the direction, go through the rest of the numbers. Make sure each number follows the established trend. If you find any number that goes against the trend, you know the sequence isn't monotonic.
If you make it to the end without finding any numbers that break the trend, the sequence is monotonic.

Code Implementation

def is_monotonic(sequence):
    sequence_length = len(sequence)
    if sequence_length <= 2:
        return True

    index = 0
    while index < sequence_length - 1 and sequence[index] == sequence[index + 1]:
        index += 1

    if index == sequence_length - 1:
        return True

    is_increasing = sequence[index] < sequence[index + 1]

    # Determine overall trend (increasing or decreasing)
    
    for i in range(index + 1, sequence_length - 1):
        if is_increasing:
            if sequence[i] > sequence[i + 1]:
                return False
        else:
            if sequence[i] < sequence[i + 1]:
                return False

    # Ensure trend consistency.
    
    return True

def is_monotonic_two(nums):
    increasing = True
    decreasing = True

    # Check both increasing and decreasing
    for i in range(len(nums) - 1):
        if nums[i] > nums[i+1]:
            increasing = False
        if nums[i] < nums[i+1]:
            decreasing = False

    # Return if it is either increasing or decreasing
    return increasing or decreasing

def is_monotonic_one_pass(array):
    direction = 0
    # Need to check the direction for increase or decrease.
    for i in range(1, len(array)): 
        if array[i] - array[i - 1] > 0:
            current_direction = 1
        elif array[i] - array[i - 1] < 0:
            current_direction = -1
        else:
            current_direction = 0

        if direction == 0:
            direction = current_direction
        elif direction != current_direction and current_direction != 0:
            # Ensure same direction
            return False
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return true because an empty array can be considered both monotonically increasing and monotonically decreasing.
Array with a single element	Return true, as a single element is always monotonic.
Array with all identical elements	The algorithm should correctly identify this as monotonic (both increasing and decreasing).
Array with strictly increasing values	Algorithm must correctly identify it as monotonically increasing.
Array with strictly decreasing values	Algorithm must correctly identify it as monotonically decreasing.
Array with mixed increasing and decreasing segments	The algorithm should correctly identify this as non-monotonic.
Array with duplicate consecutive elements in increasing or decreasing order	Algorithm should handle these gracefully, maintaining the monotonic property if the increasing/decreasing order is consistent.
Large array sizes to test performance	The algorithm should ideally have O(n) time complexity, performing a single pass through the array efficiently.

Empty or null input array

How to Handle:

Return true because an empty array can be considered both monotonically increasing and monotonically decreasing.

Array with a single element

How to Handle:

Return true, as a single element is always monotonic.

Array with all identical elements

How to Handle:

The algorithm should correctly identify this as monotonic (both increasing and decreasing).

Array with strictly increasing values

How to Handle:

Algorithm must correctly identify it as monotonically increasing.

Array with strictly decreasing values

How to Handle:

Algorithm must correctly identify it as monotonically decreasing.

Array with mixed increasing and decreasing segments

How to Handle:

The algorithm should correctly identify this as non-monotonic.

Array with duplicate consecutive elements in increasing or decreasing order

How to Handle:

Algorithm should handle these gracefully, maintaining the monotonic property if the increasing/decreasing order is consistent.

Large array sizes to test performance

How to Handle:

The algorithm should ideally have O(n) time complexity, performing a single pass through the array efficiently.