Balanced Parenthesis

//You are given a string of brackets i.e. '{', '}' , '(' , ')', '[' , ']' . You have to check whether the sequence of parenthesis is balanced or not.
//For example, "(())", "(())()" are balanced and "())(", "(()))" are not.
//
//Input Format
//A string of '(' , ')' , '{' , '}' and '[' , ']' .
//
//Constraints
//1<=|S|<=10^5
//
//Output Format
//Print "Yes" if the brackets are balanced and "No" if not balanced.
//
//Sample Input
//(())
//Sample Output
//Yes
//Explanation
//(()) is a balanced string.

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

bool isBal(string s){
    stack<char> stk;
    for(char c : s){
        if(c == '{' || c == '(' || c == '[') stk.push(c);
        else{
            if(stk.empty()) return false;
            else if(stk.top() == '(' && c == ')') stk.pop();
            else if(stk.top() == '{' && c == '}') stk.pop();
            else if(stk.top() == '[' && c == ']') stk.pop();
            else{
                return false;
            }
        }
    }
    return stk.empty();
}
int main() {
    string str; cin >> str;
    if(isBal(str)) cout << "Yes";
    else cout << "No";
    return 0;
}

Largest Area in Histogram

//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.
//
//
//
//Input Format
//First Line contains size of input array
//Second Line contains Array
//
//Constraints
//1 <= heights.length <= 105
//0 <= heights[i] <= 104
//
//Output Format
//Print Largest Area
//
//Sample Input
//6
//2 1 5 6 2 3
//Sample Output
//10
//Explanation
//The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int largestArea(vector<int>& arr){
    stack<int> s; int m = 0, i = 0;
    while(i <= arr.size()){
        int val = i < arr.size() ? arr[i] : 0;
        if(s.empty() || val >= arr[s.top()]) s.push(i), i++;
        else{
            int h = arr[s.top()]; s.pop();
            int w = s.empty() ? i : i-s.top()-1;
            m = max(m , h*w);
        }
    }
    return m;
}

int main(){
    int n; cin >> n; vector<int> arr;
    while(n--){
        int val; cin >> val;
        arr.push_back(val);
    }
    cout << largestArea(arr);
    return 0;
}

Next Greater Element 2

//You are given a circular integer array nums
//
//The next element of nums[nums.length - 1] is nums[0]), print 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, print -1 for this number.
//
//Input Format
//First line contains an integer n ( size of the array).
//
//Second line contains an integer array of size n.
//
//Constraints
//1 <= n <= 105
//-104 nums[i] <= 104
//
//Output Format
//print the next greater number for every element in nums.
//
//Sample Input
//5
//1 2 3 4 3
//Sample Output
//2 3 4 -1 4
//Explanation
//2 3 4 -1 4 are the next greater elements of the corresponding array elements .

#include <bits/stdc++.h>
using namespace std;

vector<int> nge(vector<int>&nums){
    int n = nums.size();
    vector<int> res(n,-1);
    stack<int>st;
    for(int i=0;i<n*2;i++){
        while(!st.empty() && nums[i%n] > nums[st.top()]){
            res[st.top()] = nums[i%n];
            st.pop();
        }
        st.push(i%n);
    }
    return res;
}

int main() {
    int n; cin >> n; vector<int> arr; for(int i=0;i<n;i++){
        int val; cin >> val; arr.push_back(val);
    }
    vector<int> res = nge(arr);
    for(int i : res){
        cout << i << " ";
    }
}

Playing with Cards

//You are at a casino. There are N stacked cards on pile A0. Each card has a number written on it. Then there will be Q iterations. In ith iteration, you start picking up the cards in Ai-1th pile from the top one by one and check whether the number written on the card is divisible by the ith prime number. If the number is divisible, you stack that card on pile Bi. Otherwise, you stack that card on pile Ai. After Q iterations, cards can only be on pile B1, B2, B3, . . . BQ, AQ . Output numbers on these cards from top to bottom of each piles in order of B1, B2, B3, . . . BQ, AQ .
//
//Input Format
//First line contains N and Q. The next line contains N space separated integers representing the initial pile of cards i.e., A0. The leftmost value represents the bottom plate of the pile.
//
//Constraints
//N < 10^5
//Q < 10^5
//|Ai| < 10^9
//
//Output Format
//Output N lines, each line containing the number written on the card.
//
//Sample Input
//5 1
//3 4 7 6 5
//Sample Output
//4
//6
//3
//7
//5
//Explanation
//Initially:
//
//A0 = [3, 4, 7, 6, 5]<-TOP
//
//After 1st iteration:
//
//A0 = []<-TOP
//
//A1 = [5, 7, 3]<-TOP
//
//B1 = [6, 4]<-TOP
//
//Now first print B1 from top to bottom then A1 from top to bottom.

#include<bits/stdc++.h>
using namespace std;

void primes(vector<int>& res){
    vector<bool> prime(100001);
    prime[0] = true;
    prime[1] = true;
    for(int i=2;i*i<100000;i++){
        if(prime[i] == false){
            res.push_back(i);
            for(int a=2;a*i<=100000;a++){
                prime[a*i] = true;
            }
        }
    }
    for(int i=2;i<=100000;i++){
        if(!prime[i]) res.push_back(i);
    }
}

void helper(stack<int>&cards, int q){
    stack<int> a , b;
    vector<int> res;
    primes(res);
    for(int i=1;i<=q;i++){
        int prime = res[i-1];
        while(!cards.empty()){
            int temp = cards.top(); cards.pop();
            if(temp%prime==0) b.push(temp);
            else a.push(temp);
        }
        while(!b.empty()){
            cout << b.top() << endl;
            b.pop();
        }
        cards = a;
        while(!a.empty()) a.pop();
    }
    while(!cards.empty()){
        cout << cards.top() << endl;
        cards.pop();
    }
}

int main(){
    int n, q; cin >> n >> q; stack<int> cards;
    for(int i=0;i<n;i++){
        int val; cin >> val;
        cards.push(val);
    }
    helper(cards,q);
}

StockSpan

//The stock span problem is a financial problem where we have a series of N daily price quotes for a stock and we need to calculate span of stock’s price for all N days. You are given an array of length N, where ith element of array denotes the price of a stock on ith. Find the span of stock's price on ith day, for every 1<=i<=N.
//A span of a stock's price on a given day, i, is the maximum number of consecutive days before the (i+1)th day, for which stock's price on these days is less than or equal to that on the ith day.
//
//Input Format
//First line contains integer N denoting size of the array.
//Next line contains N space separated integers denoting the elements of the array.
//
//Constraints
//1 <= N <= 10^6
//
//Output Format
//Display the array containing stock span values.
//
//Sample Input
//5
//30
//35
//40
//38
//35
//Sample Output
//1 2 3 1 1 END
//Explanation
//For the given case
//for day1 stock span =1
//for day2 stock span =2 (as 35>30 so both days are included in it)
//for day3 stock span =3 (as 40>35 so 2+1=3)
//for day4 stock span =1 (as 38<40 so only that day is included)
//for day5 stock span =1 (as 35<38 so only that day is included)
//hence output is 1 2 3 1 1 END

#include<iostream>
#include <bits/stdc++.h>
using namespace std;

stack<pair<int,int>> stk;
int getPrice(int price){
    int count = 1;
    while(!stk.empty() && stk.top().first <= price){
        count += stk.top().second;
        stk.pop();
    }
    stk.push({price,count});
    return count;
}

int main() {
    vector<int> res;
    int n; cin >> n;
    while(n--){
        int val; cin >> val;
        res.push_back(getPrice(val));
    }

    for(auto i : res) cout << i << " ";
    cout << "END" << endl;
    return 0;
}