Next Greater Element In Sorted Array Editorial

Practice Problem Link: Next Greater Element In Sorted Array

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a sorted array and a number key, find the smallest array element which is greater than the key. If the key is greater than or equal to the largest element then return the key itself.

Naive Approach

The simple solution is to traverse the array and return the first element greater than key.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int getNextGreaterElement(vector<int> &arr, int key) {
    int n = arr.size();
	if (arr[n - 1] <= key) {
		return key;
	}
	for (int i = 0; i < n; i++) {
		if (arr[i] > key) {
			return arr[i];
		}
	}
}

Java

class Solution {
	int getNextGreaterElement (int[] arr, int key) {
		int n = arr.length;
		if (arr[n - 1] <= key) {
			return key;
		}
		for (int i = 0; i < n; i++) {
			if (arr[i] > key) {
				return arr[i];
			}
		}
		return 0;
	}
}

Optimal Approach

The problem can be solved efficiently using binary search to find the element just greater than the key.

Analysis

• Time Complexity: O(log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

int binarySearch (vector<int> &arr, int low, int high, int key) {
	if(low < high) {
		int mid = (high + low) / 2;
		if (arr[mid] <= key) {
			return binarySearch (arr, mid + 1, high, key);
		} else {
			return binarySearch (arr, low, mid, key);
		}
	}
	else {
		return arr[low];
	}
}
int getNextGreaterElement(vector<int> &arr, int key) {
    int n = arr.size();
	if (arr[n - 1] <= key) {
			return key;
	}
	return binarySearch (arr, 0, n - 1, key);
}

Java

class Solution {
	int binarySearch (int[] arr, int low, int high, int key) {
		if(low < high) {
			int mid = (high + low) / 2;
			if (arr[mid] <= key) {
				return binarySearch (arr, mid + 1, high, key);
			} else {
				return binarySearch (arr, low, mid, key);
			}
		}
		else {
			return arr[low];
		}
	}
	int getNextGreaterElement (int[] arr, int key) {
		int n = arr.length;
		if (arr[n - 1] <= key) {
			return key;
		}
		return binarySearch (arr, 0, n - 1, key);
	}
}