Find the Smallest Number Greater Than Each Element

Title: Find the Smallest Number Greater Than Each Element

Given an array of integers, how do you find, for every element, the smallest value anywhere else in the array that is strictly greater than it? This comes up often in interviews as a warm-up for binary search, and it is a great way to practice turning a repeated linear scan into a single sort plus a binary search per element. In this guide, we will explore an efficient Java solution, walk through a dry run trace, and work through several examples, common mistakes, and interview-style follow-up questions.

Understanding the Problem

Given an array numbers, we want to produce a result array of the same length where result[i] is the smallest value in numbers that is strictly greater than numbers[i]. If no such value exists, usually because numbers[i] is the maximum (or tied for the maximum), result[i] should be -1.

For example, for numbers = {8, 1, 2, 2, 3}, the smallest value greater than 8 does not exist in the array, so result[0] = -1. The smallest value greater than 1 is 2, so result[1] = 2, and so on.

A brute-force approach compares every element against every other element, which costs O(n²) time. By sorting a copy of the array once and using binary search for each element, we can answer every query in O(log n), bringing the total time down to O(n log n).

Approach: Sort and Binary Search

The key insight is that once the array is sorted, the smallest value strictly greater than a target is found at the first position where the sorted value exceeds the target. That position is exactly what an upperBound binary search returns.

Here are the steps:

1. Create a sorted copy of the input array using Arrays.copyOf and Arrays.sort, leaving the original array untouched.
2. For every index i in the original array, run a binary search for the first position in the sorted copy whose value is strictly greater than numbers[i].
3. This binary search, called upperBound, narrows a low/high range: whenever the middle value is less than or equal to the target, move low past it; otherwise shrink high to the middle.
4. If the returned index is within bounds, the value at that index in the sorted array is the answer for numbers[i].
5. If the returned index equals the array length, no element is greater than numbers[i], so the answer is -1.
6. Store each answer in a result array at the same index i and return it once every element has been processed.

Java Program to Find the Smallest Greater Element

Let us put the approach into a complete, compilable Java program:

import java.util.Arrays;

public class SmallestGreaterElement {

    public static int[] findSmallestGreater(int[] numbers) {
        int n = numbers.length;
        int[] sorted = Arrays.copyOf(numbers, n);
        Arrays.sort(sorted);

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            int index = upperBound(sorted, numbers[i]);
            result[i] = (index < n) ? sorted[index] : -1;
        }
        return result;
    }

    private static int upperBound(int[] sorted, int target) {
        int low = 0;
        int high = sorted.length;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (sorted[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 1, 2, 2, 3};
        int[] result = findSmallestGreater(numbers);

        System.out.println("Input array: " + Arrays.toString(numbers));
        System.out.println("Smallest greater element for each index: " + Arrays.toString(result));
    }
}

Explanation of the Program

• The method findSmallestGreater takes an int[] and returns a new array where each slot holds the smallest value in the input that is strictly greater than the element at that slot, or -1 when none exists.
• Arrays.copyOf followed by Arrays.sort builds a sorted sorted array without mutating the caller’s numbers array.
• For each i, we call upperBound(sorted, numbers[i]), which performs a binary search and returns the index of the first value in sorted that is strictly greater than numbers[i].
• Inside upperBound, the loop keeps halving the [low, high) range. When sorted[mid] is less than or equal to the target, the answer must lie to the right, so low moves past mid. Otherwise, mid is a candidate answer, so high shrinks down to it.
• When low and high meet, that shared index is either a valid position in sorted or equal to sorted.length, which signals no greater element exists.
• The main method runs the function on the sample array {8, 1, 2, 2, 3} and prints both the input and the computed result so you can see the algorithm in action immediately.

Step-by-Step Trace

Let us trace the algorithm on numbers = {5, 3, 9, 3, 7}, which includes a duplicate pair and the array maximum so we can see both a normal lookup and the no-match case. First, sorting a copy gives sorted = {3, 3, 5, 7, 9}. Then we run upperBound independently for every index.

At the end of each iteration, result[i] holds the smallest value in sorted that is strictly greater than numbers[i], or -1 when numbers[i] is the maximum value in the array, as seen for i = 3 where numbers[i] = 9 has nothing larger to find.

Examples

Let us look at a few runs that stress different parts of the algorithm.

Example 1: Distinct Values

int[] numbers = {10, 2, 14, 7};
int[] result = findSmallestGreater(numbers);
System.out.println(Arrays.toString(result));
// Output: [14, 7, -1, 10]

Every value is unique, so each lookup lands on a clean neighbor in the sorted order. 14 has nothing greater, which is why result[2] = -1.

Example 2: Negative Numbers and Duplicates

int[] numbers = {-3, -3, 0, -3, 5};
int[] result = findSmallestGreater(numbers);
System.out.println(Arrays.toString(result));
// Output: [0, 0, 5, 0, -1]

The three copies of -3 all map to the same answer, 0, because upperBound skips past every value equal to the target before stopping. 5 is the array maximum, so its answer is -1.

Example 3: All Elements Equal

int[] numbers = {4, 4, 4, 4};
int[] result = findSmallestGreater(numbers);
System.out.println(Arrays.toString(result));
// Output: [-1, -1, -1, -1]

When every element has the same value, no element is strictly greater than any other, so every position in the result is -1. This is a useful sanity check for the boundary behavior of upperBound.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing this sort-and-search approach:

• Using a lower bound instead of an upper bound – searching for the first value greater than or equal to the target, instead of strictly greater, wrongly returns the target itself when duplicates are present. Make sure the comparison in upperBound is sorted[mid] <= target, not <.
• Binary searching the unsorted array – running upperBound directly on numbers instead of the sorted copy produces meaningless results because binary search assumes sorted input. Always sort a copy first.
• Sorting the original array in place – calling Arrays.sort directly on numbers destroys the original ordering, so result[i] no longer lines up with the caller’s input. Always sort a copy made with Arrays.copyOf.
• Returning the sorted index instead of the value – forgetting to read sorted[index] and instead storing the index itself produces numbers that look plausible but are completely wrong. The result must be the value at that position, not the position.
• Forgetting the out-of-range check – when the binary search returns sorted.length, indexing into sorted[index] throws an ArrayIndexOutOfBoundsException. Always check index < n before reading from sorted.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Empty array
• Single-element array
• All identical elements
• Array already sorted in ascending order
• Array sorted in descending order
• Maximum value appearing more than once
• Negative numbers mixed with positive numbers
• Integer.MIN_VALUE or Integer.MAX_VALUE present

Additional Considerations

A few points worth remembering about this approach:

1. Time complexity: Sorting the copy costs O(n log n), and each of the n binary searches costs O(log n), for a total of O(n log n), far better than the O(n²) brute-force comparison of every pair.
2. Space complexity: The algorithm allocates one sorted copy and one result array, both of size n, so the extra space is O(n).
3. Why upperBound and not a standard binary search: Arrays.binarySearch only tells you whether an exact match exists; it gives no guarantee about which index it lands on when duplicates are present. A hand-written upperBound deterministically returns the first index past every occurrence of the target.
4. Handling duplicates: Because upperBound advances past values that are less than or equal to the target, every duplicate of a given value maps to the same answer, which is the correct behavior for this problem.
5. Alternative with TreeSet: A TreeSet<Integer> with its higher() method answers the same question in O(log n) per query without writing a manual binary search, at the cost of extra memory for the tree nodes and boxed integers.

Interview Follow-up Questions

Once the base version is working, an interviewer will usually probe deeper with questions like these:

• What if the array is already sorted? – skip the sorting step entirely and run upperBound directly on the input, dropping the time complexity to O(n log n) with no extra sort cost, or O(n) if you walk both pointers together instead of binary searching.
• What if you need the smallest value greater than each element, but only among elements to its right? – this becomes the classic Next Greater Element problem, best solved with a decreasing monotonic stack in a single O(n) pass instead of sorting.
• What if you need the largest value smaller than each element instead? – mirror the approach with a lowerBound-style search that finds the last sorted value strictly less than the target.
• What if the array is too large to fit in memory? – sort the data externally in chunks, then stream each original element against the sorted chunks using merge-style scanning instead of random-access binary search.
• Can you answer these queries online, with elements inserted one at a time? – maintain the running values in a balanced structure like a TreeSet so that higher() answers each new query in O(log n) as the data grows.

Conclusion

In this guide, we solved the problem of finding the smallest number greater than each element by sorting a copy of the array and running a binary search for every element. The upperBound helper is the reusable piece here: once you understand how it narrows a range to the first value exceeding a target, it applies directly to many other search problems.

Try adapting the code to find the largest value smaller than each element, or restrict the search to elements that appear only to the right of the current index. Both variations build directly on the upperBound pattern you just implemented. Happy coding!

You can learn more about array techniques here: Arrays.