Table of contents

Find the Next Larger Element for each element

Given an array of integers, find the Next Larger Element (NLE) for each element. The next larger element for an element x is the first element on the right side of x in the array which is larger than x. If there is no larger element, return -1 for that element.

Input/Output Examples

plaintext
Example 1:
Input: arr = [4, 5, 2, 10, 8]
Output: [5, 10, 10, -1, -1]
Explanation: For 4, the next larger element is 5. For 5, it's 10. For 2, it's 10. There is no next larger element for 10 and 8, so they both get -1.

Example 2:
Input: arr = [3, 7, 1, 7, 8]
Output: [7, 8, 7, 8, -1]
Explanation: For 3, the next larger element is 7. For 7, it's 8. For 1, it's 7. For 7 (fourth element), it's 8. For 8, there is no larger element, so it gets -1.

Approach to find the Next Larger Element

  1. Stack-Based Approach:
    • Use a stack to keep track of elements for which we haven't yet found the next larger element.
    • Traverse the array from right to left.
    • For each element, pop elements from the stack that are smaller than or equal to the current element.
    • If the stack becomes empty, there is no next larger element for the current element, so append -1. Otherwise, the top of the stack is the next larger element.
  2. Algorithm to find the Next Larger Element:
    • Initialize an empty stack and a result array with the same length as the input, filled with -1.
    • Traverse the array from right to left:
      • For each element, pop elements from the stack that are smaller than or equal to the current element.
      • If the stack is not empty, the top of the stack is the next larger element.
      • Push the current element onto the stack.
  3. Edge Cases:
    • If the array has only one element, the next larger element is -1.
    • If all elements are in descending order, every element will have -1 as the next larger element.

C++ Program to find the Next Larger Element

cpp
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

// Function to find the next larger element for each element in the array
vector<int> nextLargerElement(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1); // Initialize result with -1
    stack<int> s;
    
    // Traverse the array from right to left
    for (int i = n - 1; i >= 0; i--) {
        // Pop elements from the stack that are smaller than or equal to the current element
        while (!s.empty() && s.top() <= arr[i]) {
            s.pop();
        }
        // If the stack is not empty, the top of the stack is the next larger element
        if (!s.empty()) {
            result[i] = s.top();
        }
        // Push the current element onto the stack
        s.push(arr[i]);
    }
    
    return result;
}

int main() {
    vector<int> arr = {4, 5, 2, 10, 8};
    vector<int> result = nextLargerElement(arr);
    
    cout << "Next larger elements: ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Java Program to find the Next Larger Element

java
import java.util.Stack;

public class NextLargerElement {

    // Function to find the next larger element for each element in the array
    public static int[] nextLargerElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n]; // Initialize result array with -1
        Stack<Integer> stack = new Stack<>();
        
        // Traverse the array from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Pop elements from the stack that are smaller than or equal to the current element
            while (!stack.isEmpty() && stack.peek() <= arr[i]) {
                stack.pop();
            }
            // If the stack is not empty, the top of the stack is the next larger element
            if (!stack.isEmpty()) {
                result[i] = stack.peek();
            } else {
                result[i] = -1;
            }
            // Push the current element onto the stack
            stack.push(arr[i]);
        }
        
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10, 8};
        int[] result = nextLargerElement(arr);
        
        System.out.println("Next larger elements: ");
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}

Python Program to find the Next Larger Element

python
# Function to find the next larger element for each element in the array
def next_larger_element(arr):
    n = len(arr)
    result = [-1] * n  # Initialize result array with -1
    stack = []
    
    # Traverse the array from right to left
    for i in range(n - 1, -1, -1):
        # Pop elements from the stack that are smaller than or equal to the current element
        while stack and stack[-1] <= arr[i]:
            stack.pop()
        # If the stack is not empty, the top of the stack is the next larger element
        if stack:
            result[i] = stack[-1]
        # Push the current element onto the stack
        stack.append(arr[i])
    
    return result

# Example usage
if __name__ == "__main__":
    arr = [4, 5, 2, 10, 8]
    result = next_larger_element(arr)
    print("Next larger elements:", result)

Time Complexity:

  • O(n): Each element is pushed and popped from the stack at most once, so the time complexity is linear.

Space Complexity:

  • O(n): The space complexity is proportional to the size of the stack, which can store up to n elements in the worst case.

DSA

Related Articles