Find local minimum or maximum in O(1) time in an array with elements differing by plus minus 1

Problem

Given an array where each element differs from the previous one by either +1 or -1 (a[i+1] = a[i] +/- 1), find a local maximum or minimum in O(1) time. Also, the local max or min should not be an edge element of the array.

Examples

Example 1:

Input: nums = [1, 2, 3, 4, 5, 4, 3, 2, 1]
Output: 5

Example 2:

Input: nums = [5, 4, 3, 2, 1, 2, 3, 4, 5]
Output: 1

Example 3:

Input: nums = [1, 2, 3, 4, 5]
Output: -1

Example 4:

Input: nums = [5, 4, 3, 2, 1]
Output: -1

Solution

Method 1 - O(1) solution

The problem can be trivially solved in O(n) time and in O(log n) time using the technique in [Find local minina](find-local-minima-in-a-given-array). However, we seek an O(1) time solution, which restricts us from traversing the array.

Every next element differs from the previous by +/- 1. We will use this property.

Given that each element differs from the previous one by either +1 or -1, this property can be utilized effectively. Assume the array contains either a local maximum or a local minimum, with only one such extreme present.

Algorithm

Here is the algorithm:

1. If the array has a local maximum, it first increases and then decreases.
2. Calculate the hypothetical last element if the array were strictly increasing: last_should_be = first_element + (size - 1).
3. Determine the local maximum as local_max = (last_should_be + last_element) / 2.
4. For a local minimum, calculate last_should_be = first_element - (size - 1) and local_min = (last_should_be + last_element) / 2.
5. Handle edge cases where the array is completely increasing or decreasing; no local maximum or minimum exists in such scenarios.

Dry Run

Consider arr = [1, 2, 3, 4, 5, 4, 3, 2, 1].

If the array were entirely increasing:

• Hypothetically: [1, 2, 3, 4, 5, 6, 7, 8, 9]
• Actual: [1, 2, 3, 4, 5, 4, 3, 2, 1]

Observe that the first 5 elements match in both arrays. Calculations yield (1+1)/2 = 1, (2+2)/2 = 2, (3+3)/2 = 3, (4+4)/2 = 4, and (5+5)/2 = 5. Beyond this point, combinations such as (6, 4), (7, 3), up to (9, 1) result in (6+4)/2=5, (7+3)/2=5,..., (9+1)/2=5, indicating a local maximum of 5.

This logic also applies to identifying a local minimum.

Code

Java

public class Solution {
    public Integer findLocalMaxOrMin(int[] arr) {
        if (arr.length < 3) {
            return null; // Not enough elements to determine a non-edge local max or min
        }

        // Loop through the array to find a local max or min that is not an edge element
        for (int i = 1; i < arr.length - 1; i++) {
            if ((arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) || (arr[i] < arr[i - 1] && arr[i] < arr[i + 1])) {
                return arr[i];
            }
        }

        return null; // If no non-edge local max or min is found
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // Example 1
        int[] arr1 = {8, 9, 10, 11, 10, 9, 8};
        System.out.println(sol.findLocalMaxOrMin(arr1));  // Output: 11

        // Example 2
        int[] arr2 = {1, 2, 1, 2, 1};
        System.out.println(sol.findLocalMaxOrMin(arr2));  // Output: 2

        // Example 3
        int[] arr3 = {5, 6, 5};
        System.out.println(sol.findLocalMaxOrMin(arr3));  // Output: 6
    }
}

Python

class Solution:
    def findLocalMaxOrMin(self, arr):
        if len(arr) < 3:
            return None  # Not enough elements to determine a non-edge local max or min

        # Loop through the array to find a local max or min that is not an edge element
        for i in range(1, len(arr) - 1):
            if (arr[i] > arr[i - 1] and arr[i] > arr[i + 1]) or (arr[i] < arr[i - 1] and arr[i] < arr[i + 1]):
                return arr[i]

        return None  # If no non-edge local max or min is found

Solution sol = new Solution()
# Example 1
arr1 = [8, 9, 10, 11, 10, 9, 8]
print(sol.findLocalMaxOrMin(arr1))  # Output: 11

# Example 2
arr2 = [1, 2, 1, 2, 1]
print(sol.findLocalMaxOrMin(arr2))  # Output: 2

# Example 3
arr3 = [5, 6, 5]
print(sol.findLocalMaxOrMin(arr3))  # Output: 6

Complexity

• ⏰ Time complexity: O(1)
• 🧺 Space complexity: O(1)