LeetCode - Stack - Valid Parentheses/ Next Greater Element/ Next Smaller Element to the Left

---

1. Valid Parentheses

Problem: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:

• Open brackets are closed by the same type of brackets.

• Open brackets are closed in the correct order.

---

Input:

string s = "({[]})";

Output:

true

---

Brute Force (Less common, but for demonstration: repeated string reduction):

Repeatedly remove pairs "()", "{}", "[]" until no changes:

bool isValidBruteForce(string s) {
    string prev;
    while (s != prev) {
        prev = s;
        s = regex_replace(s, regex("\\(\\)"), "");
        s = regex_replace(s, regex("\\{\\}"), "");
        s = regex_replace(s, regex("\\[\\]"), "");
    }
    return s.empty();
}

Note: This is inefficient, regex not typical in LeetCode C++ solutions.

---

Optimized Stack Approach:

bool isValidOptimized(string s) {
    stack<char> stk;
    for (char c : s) {
        if (c == '(') stk.push(')');
        else if (c == '{') stk.push('}');
        else if (c == '[') stk.push(']');
        else {
            if (stk.empty() || stk.top() != c)
                return false;
            stk.pop();
        }
    }
    return stk.empty();
}

---

Iteration Table:

Iteration	Char	Stack Top after push/pop	Stack content
1	'('	')'	[')']
2	'{'	'}'	[')', '}']
3	'['	']'	[')', '}', ']']
4	']'	(pop ']')	[')', '}']
5	'}'	(pop '}')	[')']
6	')'	(pop ')')	[]

Stack empty → valid.

---

2. Next Greater Element (NGE)

Problem: For each element in array, find the next element greater than it to the right; if none, output -1.

---

Input:

vector<int> nums = {4, 5, 2, 25};

Output:

5 25 25 -1

---

Brute Force: O(n²)

vector<int> nextGreaterBruteForce(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (nums[j] > nums[i]) {
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}

---

Optimized Stack Approach: O(n)

vector<int> nextGreaterOptimized(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk;  // stores indices
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && nums[i] > nums[stk.top()]) {
            result[stk.top()] = nums[i];
            stk.pop();
        }
        stk.push(i);
    }
    return result;
}

---

Iteration Table:

i	nums[i]	Stack content (indices)	Result updates	Result array
0	4	[0]	-	[-1, -1, -1, -1]
1	5	[] (pop 0)	result[0] = 5	[5, -1, -1, -1]
	push 1
2	2	[1, 2]	-	[5, -1, -1, -1]
3	25	[] (pop 2, pop 1)	result[2] = 25, result[1] = 25	[5, 25, 25, -1]
	push 3

---

3. Monotonic Stack (Next Smaller Element to the Left)

Problem: For each element, find the closest smaller element to the left; if none, output -1.

---

Input:

vector<int> nums = {2, 1, 5, 6, 2, 3};

Output:

-1 -1 1 5 1 2

---

Brute Force: O(n²)

vector<int> nextSmallerLeftBruteForce(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    for (int i = 0; i < n; i++) {
        for (int j = i-1; j >= 0; j--) {
            if (nums[j] < nums[i]) {
                result[i] = nums[j];
                break;
            }
        }
    }
    return result;
}

---

Optimized Stack Approach: O(n)

vector<int> nextSmallerLeftOptimized(vector<int>& nums) {
    int n = nums.size();
    vector<int> result(n, -1);
    stack<int> stk; // stores elements
    
    for (int i = 0; i < n; i++) {
        while (!stk.empty() && stk.top() >= nums[i]) {
            stk.pop();
        }
        result[i] = stk.empty() ? -1 : stk.top();
        stk.push(nums[i]);
    }
    return result;
}

---

Iteration Table:

i	nums[i]	Stack content (elements)	Result[i]	Action
0	2	[] → push 2	-1	empty stack
1	1	[2] → pop 2, push 1	-1	2 ≥ 1, pop
2	5	[1] → push 5	1	top=1 < 5
3	6	[1,5] → push 6	5	top=5 < 6
4	2	[1,5,6] → pop 6, pop 5, push 2	1	pop until top < 2
5	3	[1,2] → push 3	2	top=2 < 3

---

Summary Table:

Problem	Brute Force Time	Optimized Time	Stack Use
Valid Parentheses	O(n²) (inefficient)	O(n)	Push expected closing
Next Greater Element	O(n²)	O(n)	Monotonic decreasing stack
Next Smaller to Left	O(n²)	O(n)	Monotonic increasing stack

---