1) Delete mid of stack

06 November 2024 00:02

Given a stack, delete the middle element of the stack without using any additional data
structure.
Middle element:- floor((size_of_stack+1)/2) (1-based indexing) from the bottom of
the stack.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

void helper(stack<int>& s, int pos){

// Base case: If position is 1, pop the middle element
if(pos == 1){
[Link]();
return;
}

// Store top element and pop it to reach the middle

int temp = [Link]();
[Link]();

// Recursive call with decremented position

helper(s, pos - 1);

// Push the stored element back after recursive call

[Link](temp);
}

void deleteMid(stack<int>& s, int size) {

if([Link]()) return;

// Calculate the middle position correctly for both odd and even sizes
int pos= floor((size/2)+1); // Use 1-based indexing for middle
helper(s, pos);
}

New Section 1 Page 1

2) Insert an element at the bottom of stack
06 November 2024 00:32

You are given a stack st of n integers and an element x. You have to insert x at the bottom of the
given stack.

From <[Link]

void helper(stack<int> &st,int x){

if([Link]()){
[Link](x);
return;
}

//1 case solved

int temp = [Link]();
[Link]();

//recursion
helper(st, x);

//backtracking
[Link](temp);
}
stack<int> insertAtBottom(stack<int> st,int x){
int n = [Link]();
if(n == 0) return st;

helper(st, x);
return st;
}

New Section 1 Page 2

3) Reverse a stack using recursion
06 November 2024 00:56

You are given a stack St. You have to reverse the stack using recursion.

From <[Link]

void insertAtBottom(stack<int> &st, int n){

if([Link]()){
[Link](n);
return;
}

int temp = [Link]();

[Link]();

insertAtBottom(st, n);

[Link](temp);
}
void Reverse(stack<int> &st) {
if([Link]()) return;
int temp = [Link](); [Link]();

Reverse(st);

insertAtBottom(st, temp);
}

New Section 1 Page 3

4) Insert an element in an already sorted stack
06 November 2024 01:08

void insertInSortedStack(stack<int> &st, int x){

if([Link]() || x > [Link]()){
[Link](x);
return;
}
int temp = [Link]();
[Link]();
//recursion
insertInSortedStack(st, x);
//backtrack
[Link](temp);
}

New Section 1 Page 4

5) Sort a stack using recursion (based on prev problem)
06 November 2024 01:09

You’re given a stack consisting of 'N' integers. Your task is to sort this stack in descending order
using recursion.
We can only use the following functions on this stack S.

From <[Link]

void insertInSortedStack(stack<int> &st, int x){

if([Link]() || x > [Link]()){
[Link](x);
return;
}
int temp = [Link]();
[Link]();
//recursion
insertInSortedStack(st, x);
//backtrack
[Link](temp);
}
void sortStack(stack<int> &st)
{
if([Link]()) return ;
int temp = [Link]();
[Link]();
//recursion
sortStack(st);
//backtrack
insertInSortedStack(st, temp);
}

New Section 1 Page 5

6) Stack implementation using array
06 November 2024 01:15

class Stack {
public:
int* arr;
int size;
int top;

Stack(int size) {
arr = new int[size];
this->size = size;
this->top = -1;
}

void push(int data) {

if(top == size-1) {
cout << "Stack overflow" << endl;
return;
}
else {
top++;
arr[top] = data;
}
}

void pop() {
if(top == -1) {
cout << "Stack underflow" << endl;
return;
}
else {
top--;
}
}

bool isEmpty() {
if(top == -1) {
return true;
}
else {
return false;
}
}

int getTop() {
if(top == -1) {
cout << "Stack is empty" << endl;
return -1;
}
else {
return arr[top];
}
}

New Section 1 Page 6

 }

int getSize() {
return top+1;
}
};

New Section 1 Page 7

7) Implement two stacks using single array
06 November 2024 01:22

class Stack{
public:
int* arr;
int size;
int top1;
int top2;

Stack(int size){
arr = new int[size];
this->size = size;
top1 = -1;
top2 = size;
}

void push1(int data){

if(top2 - top1 == 1){
cout << "Stack overflow" << endl;
}
else{
top1 ++;
arr[top1] = data;
}
}

void push2(int data){

if(top2 - top1 == 1){
cout << "Stack overflow" << endl;
}
else{
top2 --;
arr[top2] = data;
}
}

void pop1(){
if(top1 == -1){
cout << "Stack underflow" << endl;
}
else{
arr[top1] = 0;
top1--;
}
}

void pop2(){
if(top2 == size){
cout << "Stack underflow" << endl;
}
else{
arr[top2] = 0;
top2++;

New Section 1 Page 8

 top2++;
}
}
};

New Section 1 Page 9

8)Valid parenthesis
06 November 2024 01:36

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

From <[Link]

void helper(stack<char>& st, string& s){

for(int i = 0; i < [Link](); i++){
if(![Link]() && [Link]() == '(' && s[i] == ')'){
[Link](); continue;
}
if(![Link]() && [Link]() == '[' && s[i] == ']'){
[Link](); continue;
}
if(![Link]() && [Link]() == '{' && s[i] == '}'){
[Link](); continue;
}
[Link](s[i]);
}
}
bool isValid(string s) {
stack<char> st;
if([Link]() == 0) return true;
if([Link]() == 1) return false;
helper(st, s);
if([Link]()) return true;
return false;
}

From <[Link]

New Section 1 Page 10

9) Redundant brackets
06 November 2024 01:47

Given valid mathematical expressions in the form of a string. You are supposed to return true if the
given expression contains a pair of redundant brackets, else return false. The given string only
contains ‘(‘, ’)’, ‘+’, ‘-’, ‘*’, ‘/’ and lowercase English letters.

From <[Link]

bool findRedundantBrackets(string &s){

bool flag = false;
stack<char>st;
for (int i = 0; i < [Link](); i++){
if(s[i] == '+' || s[i] == '*' ||s[i] == '-' ||s[i] == '/' || s[i] == '('){
[Link](s[i]);
}
if(s[i] == ')'){
if(![Link]() && [Link]() == '(') flag = true;
while([Link]() == '+' || [Link]() == '*' ||[Link]() == '-' ||[Link]() == '/') [Link]();
[Link]();
}
}
return flag;
}

New Section 1 Page 11

11) Infix to postfix
06 November 2024 23:37

Given an infix expression in the form of string str. Convert this infix expression to postfix expression.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

int priority(char ch){

if(ch == '^') return 3;
if(ch == '+' || ch == '-') return 1;
if(ch == '*' || ch == '/') return 2;
return -1;
}
string infixToPostfix(string& s) {
int n = [Link]();
int i = 0;
stack<char>st;
string ans = "";

while(i < n){

if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z') ||(s[i] >= '0' && s[i] <= '9')){
ans += s[i];
}
else if(s[i] == '(') [Link](s[i]);
else if(s[i] == ')'){
while(![Link]() && [Link]() != '('){
ans += [Link]();
[Link]();
}
[Link]();
}

else{
while(![Link]() && priority(s[i]) <= priority([Link]())){
ans += [Link]();
[Link]();
}
[Link](s[i]);
}
i++;
}
while(![Link]()){
ans += [Link]();
[Link]();
}
return ans;
}

New Section 1 Page 12

12) Infix to prefix
06 November 2024 23:38

int priority(char ch){

if(ch == '^') return 3;
if(ch == '*' || ch == '/') return 2;
if(ch == '+' || ch == '-') return 1;
return -1;
}

std::string infixToPrefix(std::string& s) {
int n = [Link]();
std::string reversed = "", ans = "";
std::stack<char> st;

for(int i = n - 1; i >= 0; i--) {

if(s[i] == '(') reversed += ')';
else if(s[i] == ')') reversed += '(';
else reversed += s[i];
}

for(int i = 0; i < n; i++) {

char ch = reversed[i];
if(isalnum(ch)) {
ans += ch;
}
else if(ch == '(') {
[Link](ch);
}
else if(ch == ')') {
while(![Link]() && [Link]() != '(') {
ans += [Link]();
[Link]();
}
if(![Link]()) [Link]();
}
else {
while(![Link]() && priority(ch) <= priority([Link]())) {
if (ch == '^' && [Link]() == '^') {
break;
}
ans += [Link]();
[Link]();
}
[Link](ch);
}
}

while(![Link]()) {
ans += [Link]();
[Link]();
}

std::reverse([Link](), [Link]());
return ans;
}

New Section 1 Page 13

13) Postfix to prefix
06 November 2024 23:39

You are given a string that represents the postfix form of a valid mathematical expression. Convert it
to its prefix form.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

string postToPre(string s) {
stack<string> st;
for (int i = 0; i < [Link](); i++) {
if (isalpha(s[i]) || isdigit(s[i])) {
// Convert char to string and push to stack
[Link](string(1, s[i]));
} else {
// Pop two operands from the stack for the operator
string op2 = [Link]();
[Link]();
string op1 = [Link]();
[Link]();
// Form the prefix expression and push back to stack
string con = s[i] + op1 + op2;
[Link](con);
}
}
return [Link]();
}

New Section 1 Page 14

14) Prefix to postfix
06 November 2024 23:40

New Section 1 Page 15

15) Postfix to Infix
06 November 2024 23:41

You are given a string that represents the postfix form of a valid mathematical expression. Convert it
to its infix form.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

string postToInfix(string s) {
stack<string> st;
int n = [Link]();
for(int i = 0; i < n; i++) {
if(isalnum(s[i])) {
[Link](string(1, s[i]));
}
else {
string op1 = [Link](); [Link]();
string op2 = [Link](); [Link]();
string temp = "(" + op2 + s[i] + op1 + ")";
[Link](temp);
}
}
return [Link]();
}

New Section 1 Page 16

16) Prefix to infix
06 November 2024 23:41

You are given a string S of size N that represents the prefix form of a valid mathematical expression.
The string S contains only lowercase and uppercase alphabets as operands and the operators are
+, -, *, /, %, and ^.Convert it to its infix form.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

string preToInfix(string s) {
stack<string> st;
int n = [Link]();
for(int i = n-1; i >= 0; i--) {
if(isalnum(s[i])) {
[Link](string(1, s[i]));
}
else {
string op1 = [Link](); [Link]();
string op2 = [Link](); [Link]();
string temp = "(" + op1 + s[i] + op2 + ")";
[Link](temp);
}
}
return [Link]();
}

New Section 1 Page 17

17) Implement min stack
06 November 2024 23:52

Design a stack that supports push, pop, top, and retrieving the minimum element in constant
time.
Implement the MinStack class:
• MinStack() initializes the stack object.
• void push(int val) pushes the element val onto the stack.
• void pop() removes the element on the top of the stack.
• int top() gets the top element of the stack.
• int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.

From <[Link]

vector<pair<int, int>>st;
MinStack() {

void push(int val) {

if([Link]()){
pair<int, int> p;
[Link] = val; [Link] = val;
st.push_back(p);
}
else{
pair<int, int> p;
[Link] = val;
[Link] = min([Link]().second, val);
st.push_back(p);
}

void pop() {
st.pop_back();
}

int top() {
return [Link]().first;
}

int getMin() {
return [Link]().second;
}

From <[Link]

New Section 1 Page 18

18) Problem Based on (next smaller element)
07 November 2024 00:21

You are given an integer array prices where prices[i] is the price of the ith item in a shop.
There is a special discount for items in the shop. If you buy the ith item, then you will receive a
discount equivalent to prices[j] where j is the minimum index such that j > i and prices[j] <=
prices[i]. Otherwise, you will not receive any discount at all.
Return an integer array answer where answer[i] is the final price you will pay for the ith item of the
shop, considering the special discount.

From <[Link]

vector<int> finalPrices(vector<int>& prices) {

stack<int> st;
int n = [Link]();
vector<int> result(n);
for (int i = n - 1; i >= 0; i--) {
while (![Link]() && [Link]() > prices[i]) [Link]();

if (![Link]()) result[i] = prices[i] - [Link]();

else result[i] = prices[i];

[Link](prices[i]);
}
return result;
}

there is just one diff bw next smaller or prev smaller,

1) for next smaller, yoy start the iteration from the end, (n-1)th index
2) for prev smaller, you start the iteration from the start, 0th index

New Section 1 Page 19

19) Smaller on left (same as next smaller element)
07 November 2024 00:35

Given an array a of integers of length n, find the nearest smaller number for every element such
that the smaller element is on left [Link] no small element present on the left print -1.

From <[Link]
itm_source=geeksforgeeks&itm_medium=article&itm_campaign=practice_card>

vector<int> leftSmaller(int n, int a[]){

stack<int> st;
vector<int> ans(n);

for (int i = 0; i < n; i++) {

while (![Link]() && [Link]() >= a[i]) [Link]();

if (![Link]()) ans[i] = [Link]();

else ans[i] = -1;

[Link](a[i]);
}
return ans;
}

New Section 1 Page 20

20) Largest rectangle in histogram
07 November 2024 01:00

Given an array of integers heights representing the histogram's bar height where the width of
each bar is 1, return the area of the largest rectangle in the histogram.

From <[Link]

vector<int> nextSmaller(vector<int>& heights) {

int n = [Link]();
vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
while (![Link]() && heights[[Link]()] >= heights[i])
[Link]();
ans[i] = [Link]() ? n : [Link]();
[Link](i);
}
return ans;
}
vector<int> prevSmaller(vector<int>& heights) {
int n = [Link]();
vector<int> ans(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (![Link]() && heights[[Link]()] >= heights[i])
[Link]();
ans[i] = [Link]() ? -1 : [Link]();
[Link](i);
}
return ans;
}
int largestRectangleArea(vector<int>& heights) {
int n = [Link]();
vector<int> next = nextSmaller(heights);
vector<int> prev = prevSmaller(heights);
int maxi = 0;
for (int i = 0; i < n; i++) {
maxi = max(maxi, heights[i] * (next[i] - prev[i] - 1)) ;
}
return maxi;
}

New Section 1 Page 21

22) Next greater Element I (based on prev problem)
07 November 2024 01:56

The next greater element of some element x in an array is the first greater element that is to
the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a
subset of nums2.
For each 0 <= i < [Link], find the index j such that nums1[i] == nums2[j] and determine
the next greater element of nums2[j] in nums2. If there is no next greater element, then the
answer for this query is -1.

From <[Link]

vector<int> nextGreaterElement(vector<int>& arr) {

int n = [Link]();
vector<int> ans(n);
stack<int> st;
for(int i = n - 1; i >= 0; i--) {
while(![Link]() && [Link]() <= arr[i]) {
[Link]();
}

ans[i] = [Link]() ? -1 : [Link]();

[Link](arr[i]);
}
return ans;
}
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int n1 = [Link]();
int n2 = [Link]();
vector<int> temp = nextGreaterElement(nums2);
vector<int> ans(n1);
for(int i = 0; i < [Link](); i++){
for(int j = 0; j < [Link](); j++){
if(nums1[i] == nums2[j]){
ans[i] = temp[j];
}
}
}
return ans;
}

New Section 1 Page 22

23) Next greater element II
07 November 2024 02:10

Given a circular integer array nums (i.e., the next element of nums[[Link] - 1] is nums[0]),
return the next greater number for every element in nums.
The next greater number of a number x is the first greater number to its traversing-order next in
the array, which means you could search circularly to find its next greater number. If it doesn't
exist, return -1 for this number.

From <[Link]

vector<int> nextGreaterElements(vector<int>& nums) {

int n = [Link]();
stack<int> st;
vector<int> ans(n);
for(int i = 2*n-1; i >= 0; i--){
while(![Link]() && [Link]() <= nums[i%n]){
[Link]();
}
if(i < n){
ans[i] = [Link]()? -1:[Link]();
}
[Link](nums[i%n]);
}
return ans;
}

Or its very blunt

||

vector<int> nextGreaterElements(vector<int>& nums) {

vector<int> ans;
int n = [Link]();
for(int i = 0; i < [Link](); i++){
ans.push_back(nums[i]);
}
for(int i = 0; i < [Link](); i++){
ans.push_back(nums[i]);
}
stack<int> st;
vector<int> v(2*n);
for(int i = [Link]()-1; i>= 0; i--){
while(![Link]() && [Link]() <= ans[i]){
[Link]();
}
v[i] = [Link]()? -1 : [Link]();
[Link](ans[i]);
}
vector<int>v2(n);
for(int i = 0; i < n; i++){
v2[i] = v[i];
}
return v2;
}

New Section 1 Page 23

24) Asteroid Collision
07 November 2024 02:49

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction
(positive meaning right, negative meaning left). Each asteroid moves at the same speed.
Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will
explode. If both are the same size, both will explode. Two asteroids moving in the same direction
will never meet.

From <[Link]

vector<int> asteroidCollision(vector<int>& asteroids) {

stack<int> st;
for(auto ast: asteroids){
bool destroy = false;//initially nothing is destroyed
if(ast > 0){
[Link](ast);
}
else{
if([Link]() || [Link]() <0){
[Link](ast);
}
else{
//collision happens only when [Link]() > 0 && ast < 0
while(![Link]() && [Link]() > 0){
if(abs(ast) == [Link]()){
destroy = true;
[Link]();
break;
}
else if(abs(ast) > [Link]()){
[Link]();
}
else{
destroy = true;
break;
}
}
if(!destroy){
[Link](ast);
}
}
}
}
vector<int>ans([Link]());
for (int i = [Link]() - 1; i >= 0; i--){
ans[i] = [Link]();
[Link]();
}
return ans;
}

From <[Link]

New Section 1 Page 24

25) Remove K digits
07 November 2024 02:58

Given string num representing a non-negative integer num, and an integer k, return the smallest
possible integer after removing k digits from num.

From <[Link]

string removeKdigits(string num, int k) {

string ans;
stack <char> st;
for (auto digit : num){
if(k>0){
while(![Link]() && [Link]() > digit){
[Link]();
k--;
if(k == 0) break;
}
}
[Link](digit);
}
if(k > 0){
while(![Link]() && k){
[Link]();
k--;
}
}
while(![Link]()){
ans.push_back([Link]());
[Link]();
}
//removing leading zeroes
while([Link]() > 0 && [Link]() == '0'){
ans.pop_back();
}
//get real ans
reverse ([Link](), [Link]());
return ans == "" ? "0" : ans;
}

From <[Link]

New Section 1 Page 25

26) Sum of subarray minimum
09 November 2024 02:44

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous)
subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

From <[Link]

vector<int> nextSmallerElement(vector<int> &arr, int n) {

vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
if([Link]()){
ans[i] = n;
}
while (![Link]() && arr[[Link]()] >= arr[i]) {
[Link]();
}
ans[i] = [Link]() ? n : [Link]();
[Link](i);
}
return ans;
}
vector<int> leftSmaller(vector<int> &arr, int n) {
vector<int> ans(n);
stack<int> st;
for (int i = 0; i < n; i++) {
if([Link]()){
ans[i] = -1;
}
while (![Link]() && arr[[Link]()] > arr[i]) {
[Link]();
}
ans[i] = [Link]() ? -1 : [Link]();
[Link](i);
}
return ans;
}
int sumSubarrayMins(vector<int>& arr) {
int n = [Link]();
vector<int> nse = nextSmallerElement(arr, n);
vector<int> pse = leftSmaller(arr, n);
long long sum = 0;
int mod = 1e9 + 7;
for (int i = 0; i < n; i++) {
long long left = i - pse[i];
long long right = nse[i] - i;
long long totalWays = left*right;
long long totalSum = arr[i]*totalWays;
sum = (sum + totalSum) % mod;
}
return sum;
}

New Section 1 Page 26

27) Maximal Rectangle
09 November 2024 02:56

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing
only 1's and return its area.

From <[Link]

vector<int> nextSmaller(vector<int>& heights) {

int n = [Link]();
vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
while (![Link]() && heights[[Link]()] >= heights[i])
[Link]();
ans[i] = [Link]() ? n : [Link]();
[Link](i);
}
return ans;
}
vector<int> prevSmaller(vector<int>& heights) {
int n = [Link]();
vector<int> ans(n);
stack<int> st;
for (int i = 0; i < n; i++) {
while (![Link]() && heights[[Link]()] >= heights[i])
[Link]();
ans[i] = [Link]() ? -1 : [Link]();
[Link](i);
}
return ans;
}
int largestRectangleArea(vector<int>& heights) {
int n = [Link]();
vector<int> next = nextSmaller(heights);
vector<int> prev = prevSmaller(heights);
int maxi = 0;
for (int i = 0; i < n; i++) {
maxi = max(maxi, heights[i] * (next[i] - prev[i] - 1)) ;
}
return maxi;
}
int maximalRectangle(vector<vector<char>>& matrix) {
int n = [Link]();
int m = matrix[0].size();
vector<vector<int>>v(n, vector<int>(m));
for(int j = 0; j < m; j++){
int sum = 0;
for(int i = 0; i < n; i++){
sum += matrix[i][j] - '0';
if(matrix[i][j] == '0') sum = 0;
v[i][j] = sum;
}
}
int maxi = 0;
for(int i = 0; i <n ;i++){
maxi = max(maxi, largestRectangleArea(v[i]));
}
return maxi;
}

New Section 1 Page 27

From <[Link]

New Section 1 Page 28

28) Online stock span
09 November 2024 14:47

Design an algorithm that collects daily price quotes for some stock and returns the span of that
stock's price for the current day.
The span of the stock's price in one day is the maximum number of consecutive days (starting
from that day and going backward) for which the stock price was less than or equal to the price of
that day.

From <[Link]

stack<pair<int, int>>st;
StockSpanner() {

int next(int price) {

int span = 1;
while(![Link]() && [Link]().first <= price){
span += [Link]().second;
[Link]();
}
[Link]({price, span});
return span;
}

From <[Link]

New Section 1 Page 29

29) Sum of subarray ranges
09 November 2024 15:28

You are given an integer array nums. The range of a subarray of nums is the difference between
the largest and smallest element in the subarray.
Return the sum of all subarray ranges of nums.
A subarray is a contiguous non-empty sequence of elements within an array.

From <[Link]

vector<int> nextSmallerElement(vector<int> &arr, int n) {

vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
if([Link]()){
ans[i] = n;
}
while (![Link]() && arr[[Link]()] >= arr[i]) {
[Link]();
}
ans[i] = [Link]() ? n : [Link]();
[Link](i);
}
return ans;
}
vector<int> leftSmaller(vector<int> &arr, int n) {
vector<int> ans(n);
stack<int> st;
for (int i = 0; i < n; i++) {
if([Link]()){
ans[i] = -1;
}
while (![Link]() && arr[[Link]()] > arr[i]) {
[Link]();
}
ans[i] = [Link]() ? -1 : [Link]();
[Link](i);
}
return ans;
}
long long sumSubarrayMins(vector<int>& arr) {
int n = [Link]();
vector<int> nse = nextSmallerElement(arr, n);
vector<int> pse = leftSmaller(arr, n);
long long sum = 0;
for (int i = 0; i < n; i++) {
long long left = i - pse[i];
long long right = nse[i] - i;
long long totalWays = left*right;
long long totalSum = arr[i]*totalWays;
sum = (sum + totalSum);
}
return sum;
}
vector<int> nextLargerElement(vector<int> &arr, int n) {
vector<int> ans(n);
stack<int> st;
for (int i = n - 1; i >= 0; i--) {
if([Link]()){
ans[i] = n;
}
while (![Link]() && arr[[Link]()] <= arr[i]) {
[Link]();
}
ans[i] = [Link]() ? n : [Link]();
[Link](i);

New Section 1 Page 30

 [Link](i);
}
return ans;
}
vector<int> leftLarger(vector<int> &arr, int n) {
vector<int> ans(n);
stack<int> st;
for (int i = 0; i < n; i++) {
if([Link]()){
ans[i] = -1;
}
while (![Link]() && arr[[Link]()] < arr[i]) {
[Link]();
}
ans[i] = [Link]() ? -1 : [Link]();
[Link](i);
}
return ans;
}
long long sumSubarrayMaxs(vector<int>& arr) {
int n = [Link]();
vector<int> nse = nextLargerElement(arr, n);
vector<int> pse = leftLarger(arr, n);
long long sum = 0;
for (int i = 0; i < n; i++) {
long long left = i - pse[i];
long long right = nse[i] - i;
long long totalWays = left*right;
long long totalSum = arr[i]*totalWays;
sum = (sum + totalSum);
}
return sum;
}
long long subArrayRanges(vector<int>& nums) {
return sumSubarrayMaxs(nums) - sumSubarrayMins(nums);
}

From <[Link]

New Section 1 Page 31

30) Celebrity Problem
09 November 2024 15:56

A celebrity is a person who is known to all but does not know anyone at a party. A party is being
organized by some people. A square matrix mat (n*n) is used to represent people at the party such
that if an element of row i and column j is set to 1 it means ith person knows jth person. You need to
return the index of the celebrity in the party, if the celebrity does not exist, return -1.

From <[Link]

int celebrity(vector<vector<int> >& M, int n)

{
stack <int> st;

//step 1: push all persons into stack

for (int i = 0; i < n; i++){
[Link](i);
}

//step 2: run discard method to get a might be celebrity

while([Link]() != 1){
int a = [Link]();
[Link]();
int b = [Link]();
[Link]();

//if a knows b?
if(M[a][b]){
//a isn't celebrity, b might be
[Link](b);
}
else{
[Link](a);
}
}

//check that single person is actually a celebrity

int mightBeCelebrity = [Link]();
[Link]();

//celebrity should not know anyone

for (int i = 0; i < n; i++){
if(M[mightBeCelebrity][i] != 0)
return -1;
}
//everyone should know celebrity
for (int i = 0; i < n; i++){
if(M[i][mightBeCelebrity] == 0 && i != mightBeCelebrity)
return -1;
}
//mightBeCelebrity is the cell
return mightBeCelebrity;
}

From <[Link]

New Section 1 Page 32

31) 132 pattern
09 November 2024 16:39

Given an array of n integers nums, a 132 pattern is a subsequence of three

integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.

From <[Link]

bool find132pattern(vector<int>& nums) {

int n = [Link]();
stack<int> st;
int nums3 = INT_MIN;
for(int i = n-1; i >= 0; i--){
if(nums3 > nums[i]) return true;
while(![Link]() && [Link]() < nums[i]){
nums3 = [Link]();[Link]();
}
[Link](nums[i]);
}
return false;
}

New Section 1 Page 33

32) Basic calculator
09 November 2024 20:37

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and
return the result of the evaluation.

From <[Link]

int calculate(string s) {
int n = [Link]();
int number = 0;
int result = 0;
int sign = 1;
stack<int> st;
for(int i = 0; i < n; i++){
if(isdigit(s[i])){
number = number*10 + (s[i] - '0');
}
else if(s[i] == '+'){
result += number*sign;
number = 0;
sign = 1;
}

else if(s[i] == '-'){

result += number*sign;
number = 0;
sign = -1;
}
else if(s[i] == '('){
[Link](result);
[Link](sign);
number = 0;
result = 0;
sign = 1;
}

else if(s[i] == ')'){

result += number*sign;
number = 0;
int stack_sign = [Link]() ;[Link]();
int last_result = [Link]() ;[Link]();
result *= stack_sign;
result += last_result;
}
}
result += number*sign;
return result;
}

New Section 1 Page 34

33) Basic calculator II
09 November 2024 20:37

Given a string s which represents an expression, evaluate this expression and return its
value.
The integer division should truncate toward zero.

From <[Link]

int calculate(string s) {
stack<int> st;
int num = 0;
char prevOperator = '+';
for (int i = 0; i <= [Link](); i++) {
char ch = (i < [Link]()) ? s[i] : '\0';
if (isdigit(ch)) {
num = num * 10 + (ch - '0');
}
if ((!isdigit(ch) && ch != ' ') || i == [Link]()) {
if (prevOperator == '+') [Link](num);
if (prevOperator == '-') [Link](-num);
if (prevOperator == '*') {
int temp = [Link]() * num;
[Link]();
[Link](temp);
}
if (prevOperator == '/') {
int temp = [Link]() / num;
[Link]();
[Link](temp);
}
prevOperator = ch;
num = 0;
}
}
int result = 0;
while (![Link]()) {
result += [Link]();
[Link]();
}
return result;
}

New Section 1 Page 35

34) Help classmate (based on problem 18)
19 March 2025 19:24

Professor X wants his students to help each other in the chemistry lab. He suggests that every
student should help out a classmate who scored less marks than him in chemistry and whose roll
number appears after him. But the students are lazy and they don't want to search too far. They
each pick the first roll number after them that fits the criteria. Find the marks of the classmate that
each student picks.
Note: one student may be selected by multiple classmates.

From <[Link]

vector<int> help_classmate(vector<int> prices, int n) {

stack<int> st;
vector<int> result(n);

for (int i = n - 1; i >= 0; i--) {

while (![Link]() && [Link]() >= prices[i]) {
[Link]();
}

result[i] = (![Link]()) ? [Link]() : -1; // Store the next smaller element or -1 if none exists

[Link](prices[i]);
}
return result;
}

New Section 1 Page 36