Problem

Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

If two distances to larger numbers are the equal, then return any one of them. If the array at idoesn’t have a nearest larger integer, then return null.

Follow-up: If you can preprocess the array, can you do this in constant time?

Examples

Example 1

1
2
3

Input: nums = [4, 1, 3, 5, 6], index = 0
Output: 3
Explanation: The nearest larger number to 4 (at index 0) is 5 (at index 3).

Example 2

1
2
3

Input: nums = [1, 3, 4, 2, 5], index = 2
Output: 4
Explanation: The nearest larger number to 4 (at index 2) is 5 (at index 4).

Solution

To find the nearest larger number for the given index i, we need to check both directions (left and right) in the array for the nearest larger number. The idea is to explore both neighbors and keep track of the nearest larger number found.

Method 1 - Linear Search + Two Pointer Technique

Approach

  1. Linear Search:
    • Start from index i and explore both directions (left and right) to find the nearest index with a larger number.
    • Keep track of the nearest distance and index while exploring both directions simultaneously.
  2. Two Pointer Technique:
    • Use two pointers (left and right) initialized to index i.
    • Move both pointers outward (in left and right direction) and keep checking for larger numbers until the end of the array is reached.

For the follow-up, we can create an auxiliary array during preprocessing that stores the nearest larger indices for each element, allowing us to query in constant time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class Solution {
    public Integer nearestLargerIndex(int[] nums, int index) {
        int n = nums.length;
        int nearestIndex = -1;
        int nearestDistance = Integer.MAX_VALUE;

        for (int left = index - 1, right = index + 1; left >= 0 || right < n; left--, right++) {
            if (left >= 0 && nums[left] > nums[index]) {
                if (index - left < nearestDistance) {
                    nearestIndex = left;
                    nearestDistance = index - left;
                }
            }
            if (right < n && nums[right] > nums[index]) {
                if (right - index < nearestDistance) {
                    nearestIndex = right;
                    nearestDistance = right - index;
                }
            }
        }

        return (nearestIndex == -1) ? null : nearestIndex;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def nearestLargerIndex(self, nums: List[int], index: int) -> Optional[int]:
        n = len(nums)
        nearest_index = None
        nearest_distance = float('inf')
        
        left, right = index - 1, index + 1
        while left >= 0 or right < n:
            if left >= 0 and nums[left] > nums[index]:
                if index - left < nearest_distance:
                    nearest_index = left
                    nearest_distance = index - left
            if right < n and nums[right] > nums[index]:
                if right - index < nearest_distance:
                    nearest_index = right
                    nearest_distance = right - index
            left -= 1
            right += 1
        
        return nearest_index

Complexity

  • ⏰ Time complexity: O(n) where n is the number of elements in the array, as we may need to scan the entire array in the worst case.
  • 🧺 Space complexity: O(1) for the space used by the pointers and result index.