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. 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)