← Back to DSA Course | Chapter 5: Stacks | Lesson 4 of 5

Next Greater Element ढूँढना

Next greater element लोगों की एक line को नीचे देखने जैसा है और, हर व्यक्ति के लिए, उनके दाईं ओर खड़े पहले taller person को ढूंढने जैसा है।

In this page:

  1. NGE Idea
  2. Using a Stack
  3. NGE Examples
  4. Circular Array
  5. NGE Practice
Syntax
markup 
result = [-1] * len(arr)
stack = []    # indexes still waiting
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)

NGE Idea

किसी array में हर element के लिए, 'next greater element' इसकी दाईं ओर का पहला value है जो इससे बड़ा हो, या अगर ऐसा कोई value मौजूद नहीं तो none, और हर element के लिए इसे efficiently compute करना एक classic stack problem है।

उदाहरण: NGE Idea

#include <iostream>
using namespace std;
int main() {
    int arr[] = {4, 5, 2, 10};
    cout << "for 4, next greater is 5. for 10, no next greater exists" << endl;
    return 0;
}
public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10};
        System.out.println("for 4, next greater is 5. for 10, no next greater exists");
    }
}
arr = [4, 5, 2, 10]
print("for 4, next greater is 5. for 10, no next greater exists")
#include <stdio.h>
int main() {
    int arr[] = {4, 5, 2, 10};
    printf("for 4, next greater is 5. for 10, no next greater exists\n");
    return 0;
}

Using a Stack

एक stack उन elements के indexes रखता है जो अब भी अपना next greater element ढूंढने का 'इंतज़ार' कर रहे हैं, इसलिए जैसे आप left से right scan करते हैं, आप stack पर candidates रखते हैं जब तक top से कुछ बड़ा न आए।

उदाहरण: Using a Stack

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {4, 5, 2, 10};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) { result[s.top()] = arr[i]; s.pop(); }
        s.push(i);
    }
    for (int r : result) cout << r << " ";
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {4, 5, 2, 10};
        int[] result = new int[arr.length];
        java.util.Arrays.fill(result, -1);
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) result[s.pop()] = arr[i];
            s.push(i);
        }
        for (int r : result) System.out.print(r + " ");
    }
}
arr = [4, 5, 2, 10]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)
print(result)
#include <stdio.h>
int main() {
    int arr[] = {4, 5, 2, 10};
    int n = 4;
    int result[4] = {-1, -1, -1, -1};
    int s[4], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) { result[s[top]] = arr[i]; top--; }
        s[++top] = i;
    }
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    return 0;
}

NGE Examples

यह O(n) में चलता है भले ही ऐसा लगे कि nested loops की ज़रूरत पड़ सकती है, क्योंकि एक monotonic stack सुनिश्चित करता है कि हर element पूरे scan में ज़्यादा से ज़्यादा एक बार push और pop हो, हर दूसरे element के लिए एक बार नहीं।

उदाहरण: NGE Examples

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {1, 3, 2, 4};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < (int)arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) { result[s.top()] = arr[i]; s.pop(); }
        s.push(i);
    }
    cout << "each index pushed/popped at most once, O(n) despite the nested loop shape" << endl;
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 4};
        int[] result = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) result[s.pop()] = arr[i];
            s.push(i);
        }
        System.out.println("each index pushed/popped at most once, O(n)");
    }
}
arr = [1, 3, 2, 4]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        result[stack.pop()] = arr[i]
    stack.append(i)
print("each index pushed/popped at most once, O(n)")
#include <stdio.h>
int main() {
    int arr[] = {1, 3, 2, 4};
    int n = 4;
    int result[4] = {-1, -1, -1, -1};
    int s[4], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) { result[s[top]] = arr[i]; top--; }
        s[++top] = i;
    }
    printf("each index pushed/popped at most once, O(n)\n");
    return 0;
}

Circular Array

एक circular array के लिए, जहां search शुरुआत से जारी रहती है, आप index को इसकी length modulo उपयोग करके conceptually array में दो बार scan करके wraparound simulate कर सकते हैं।

उदाहरण: Circular Array

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {3, 8, 4};
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> s;
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (!s.empty() && arr[s.top()] < arr[idx]) { result[s.top()] = arr[idx]; s.pop(); }
        if (i < n) s.push(idx);
    }
    for (int r : result) cout << r << " ";
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 8, 4};
        int n = arr.length;
        int[] result = new int[n];
        java.util.Arrays.fill(result, -1);
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!s.isEmpty() && arr[s.peek()] < arr[idx]) result[s.pop()] = arr[idx];
            if (i < n) s.push(idx);
        }
        for (int r : result) System.out.print(r + " ");
    }
}
arr = [3, 8, 4]
n = len(arr)
result = [-1] * n
stack = []
for i in range(2 * n):
    idx = i % n
    while stack and arr[stack[-1]] < arr[idx]:
        result[stack.pop()] = arr[idx]
    if i < n:
        stack.append(idx)
print(result)
#include <stdio.h>
int main() {
    int arr[] = {3, 8, 4};
    int n = 3;
    int result[3] = {-1, -1, -1};
    int s[3], top = -1;
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n;
        while (top >= 0 && arr[s[top]] < arr[idx]) { result[s[top]] = arr[idx]; top--; }
        if (i < n) s[++top] = idx;
    }
    for (int i = 0; i < n; i++) printf("%d ", result[i]);
    return 0;
}

NGE Practice

Internalize करने के लिए key insight यह है कि जब भी एक नई value stack के top से बड़ी हो, वह top element ने बस अपना next greater element पाया है और pop हो जाता है, तब तक दोहराते हुए जब तक stack का top बड़ा न हो या stack खाली न हो।

उदाहरण: NGE Practice

#include <iostream>
#include <stack>
#include <vector>
using namespace std;
int main() {
    vector<int> arr = {2, 1, 2, 4, 3};
    vector<int> result(arr.size(), -1);
    stack<int> s;
    for (int i = 0; i < (int)arr.size(); i++) {
        while (!s.empty() && arr[s.top()] < arr[i]) {
            cout << "index " << s.top() << " (" << arr[s.top()] << ") found NGE " << arr[i] << endl;
            result[s.top()] = arr[i];
            s.pop();
        }
        s.push(i);
    }
    return 0;
}
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        int[] arr = {2, 1, 2, 4, 3};
        int[] result = new int[arr.length];
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i]) {
                System.out.println("index " + s.peek() + " (" + arr[s.peek()] + ") found NGE " + arr[i]);
                result[s.pop()] = arr[i];
            }
            s.push(i);
        }
    }
}
arr = [2, 1, 2, 4, 3]
result = [-1] * len(arr)
stack = []
for i in range(len(arr)):
    while stack and arr[stack[-1]] < arr[i]:
        top = stack.pop()
        print("index", top, "(", arr[top], ") found NGE", arr[i])
        result[top] = arr[i]
    stack.append(i)
#include <stdio.h>
int main() {
    int arr[] = {2, 1, 2, 4, 3};
    int n = 5;
    int result[5] = {-1, -1, -1, -1, -1};
    int s[5], top = -1;
    for (int i = 0; i < n; i++) {
        while (top >= 0 && arr[s[top]] < arr[i]) {
            printf("index %d (%d) found NGE %d\n", s[top], arr[s[top]], arr[i]);
            result[s[top]] = arr[i];
            top--;
        }
        s[++top] = i;
    }
    return 0;
}
Related Topics

Balanced Parentheses चेक करना · Monotonic Stack क्या है · Stack का Implementation · Stack परिचय

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. दो nested loops उपयोग करना, जो O(n^2) है, जब एक monotonic stack इसे O(n) में करता है।
  2. Indexes के बजाय values push करना, इसलिए answer array को सही position पर update नहीं किया जा सकता।
  3. यह भूल जाना कि आखिर में stack पर छोड़े गए elements का कोई greater element नहीं है और उन्हें -1 सेट किया जाना चाहिए।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Balanced Parentheses Next Lesson → Monotonic Stack

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.