Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1. Examples:
Input : 11, 13, 21, 3, 9, 12 Output : 11 --> 21 13 --> 21 21 --> -1 3 --> 12 9 --> 12 12 --> -1 Input : 10, 9, 8, 7, 6, 5, 4, 3, 2 Output : 10 --> -1 9 --> -1 8 --> -1 7 --> -1 6 --> -1 5 --> -1 4 --> -1 3 --> -1 2 --> -1
Below is a simple implementation in Python.
Python3
# Function for implementation of NGEdef NGE(arr): # Iterate through array to check for greatest element for i in range(0, len(arr)): # Find the maximum from i to end lead = max(arr[i:]) # If max is same as the i'th number then # print -1 else print the maximum if (arr[i] == lead): print("% d --> % d" % (arr[i], -1)) else: print("% d --> % d" % (arr[i], lead))# Driver programdef main(): arr = [11, 13, 21, 3, 9, 12] NGE(arr) arr = [10, 9, 8, 7, 6, 5, 4, 3, 2] NGE(arr)if __name__ == '__main__': main() |
Note that the time complexity of above solution is O(n*n). We can optimize it in O(n) time using stack.
The space complexity of the given code is O(1) because the memory used by the program is constant, irrespective of the input size. The memory used by the program is mainly for storing the input array and a few variables used in the loop, which do not depend on the size of the input. Therefore, the space complexity is constant or O(1).
