1. Balanced Parentheses

Problem Statement:

Ek string di gayi hai jo sirf (), {}, [] brackets ka use karti hai. Aapko batana hai ki string balanced hai ya nahi.

Balanced ka matlab: Har opening bracket ka sahi closing bracket ho proper order me.

Example:

• ({[]}) → Valid
• ([)] → Invalid
• ((() → Invalid

Intuition:

Stack ka use karenge. Jab bhi opening bracket mile toh stack me push karo. Jab closing bracket mile toh check karo stack ke top se match karta hai ya nahi.

Steps:

1. Stack banao.
2. Har character par loop chalao:
3. Agar openning bracket ho, stack me daalo.
4. Agar closing ho:
5. Stack empty ho to false return.
6. Top bracket check karo matching hai ya nhi.
7. Nhi match kare to false return.
8. Match kare to pop karo.
9. Last mein agar stack empty hai toh true, warna false.

Code

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

bool isBalanced(string str) {
  stack<char> st;
  for (char ch : str) {
    if (ch == '(' || ch == '{' || ch == '[')
      st.push(ch);
    else {
      if (st.empty()) return false;
      char top = st.top();
      if ((ch == ')' && top != '(') ||
        (ch == '}' && top != '{') ||
        (ch == ']' && top != '['))
        return false;
      st.pop();
    }
  }
  return st.empty();
}

int main() {
  string s = "{[()]}";
  cout << (isBalanced(s) ? "Balanced" : "Not Balanced");
  return 0;
}

Output: 

Balanced

Explanation: 

1. Ek empty stack st banaya hai jo brackets ko track karega.

2. Loop chalaate hain har character ch par.

3. Agar ch opening bracket ho ((, {, [), toh stack me daal dete hain.

4. Agar ch closing bracket ho:

a. Stack empty ho toh invalid hai → return false.

b. Stack ke top ko nikaal ke top me store karte hain.

c. Check karte hain ch aur top ka pair valid hai ya nahi.

d. Agar valid nahi hai, return false.

e. Agar match ho gaya, toh top ko stack se hata hain.

5. Loop ke baad, agar stack empty hai toh brackets properly balanced hain → return true, warna false.

2. Min Stack

Problem Statement:

Ek special Stack implement karo jisme aap:

• push(x)
• pop()
• top()
• getMin()

sab kuch O(1) time me kar sake.

Intuition:

Ek extra stack use karenge jo minimum values ko track karega.

Steps:

• Normal stack me value push karo.
• Min stack me sirf tab push karo jab ya toh empty ho ya naye element se chhota ho.
• Jab pop karo toh min stack ka top bhi pop karo agar dono same ho.

Code

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

class MinStack {
    stack<int> st;
    stack<int> minSt;

public:
    void push(int x) {
        st.push(x);
        if (minSt.empty() || x <= minSt.top())
            minSt.push(x);
    }

    void pop() {
        if (st.top() == minSt.top())
            minSt.pop();
        st.pop();
    }

    int top() {
        return st.top();
    }

    int getMin() {
        return minSt.top();
    }
};

int main() {
    MinStack ms;
    ms.push(5);
    ms.push(3);
    ms.push(7);
    cout << "Minimum: " << ms.getMin() << endl; // 3
    ms.pop();
    cout << "Top: " << ms.top() << endl;       // 3
    cout << "Minimum: " << ms.getMin() << endl; // 3
    ms.pop();
    cout << "Minimum: " << ms.getMin() << endl; // 5
    return 0;
}

Explanation:

1. st ek normal stack hai jisme actual values store hoti hain.

2. minSt ek extra stack hai jo minimum value track karta hai.

3. push() function me:

i. Value x ko normal stack me daalte hain.

ii. Agar minSt empty hai ya x chhota ya barabar hai top se, toh minSt me bhi x daal dete hain.

4. pop() function me:

i. Agar st ka top minSt ke top ke barabar ho, toh minSt se bhi pop karte hain.

ii. Phir st se bhi pop karte hain.top() se current top element milta hai.

5. top() se current top element milta hai.

6. getMin() se current minimum value milti hai constant time me.

3. Next Greater Element (NGE)

Problem Statement:

Ek array diya gaya hai. Har element ke liye next greater element nikaalo — matlab uske right me sabse pehla bada element.

Example:

[4, 5, 2, 25] → [5, 25, 25, -1]

Intuition:

Hum Stack ka use karenge to track elements. Back se iterate karenge aur stack me sirf useful elements rakhte jayenge.

Steps:

1. Stack banao.
2. Array ko reverse me traverse karo:
3. Jab tak stack top <= current element, pop karo.
4. Agar stack empty ho, NGE = -1.
5. Else, NGE = stack top.
6. Current element ko stack me push karo.

Code

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

vector<int> nextGreaterElement(vector<int>& nums) {
    int n = nums.size();
    stack<int> st;
    vector<int> res(n);

    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= nums[i])
            st.pop();
        res[i] = st.empty() ? -1 : st.top();
        st.push(nums[i]);
    }
    return res;
}

int main() {
    vector<int> arr = {4, 5, 2, 25};
    vector<int> nge = nextGreaterElement(arr);
    for (int x : nge)
        cout << x << " ";
    return 0;
}

Output:

5 25 25 -1

Explanation:

1. nums array ka size n store karta hai.
2. Ek empty stack st banate hain future ke greater elements ke liye.
3. Ek result vector res banate hain same size ka.
4. Loop ko right-to-left (n-1 se 0) chalaate hain.
5. Jab tak stack ka top, current element se chhota ya barabar ho, use pop karte hain.
6. Agar stack empty ho gaya toh -1 assign karte hain (res[i] = -1), warna res[i] = st.top().
7. Current element ko stack me push kar dete hain.
8. Loop ke baad result array res return karte hain.

Important Stack Questions

• Largest Rectangle in Histogram
• Stock Span Problem
• Sliding Window Maximum

Solve above practice questions and share your solutions in Comment Box...