GeeksForGeeks Important Questions

max.cpp

/*
Author - Vinit Shahdeo
Brute force - sliding window
link -- https://practice.geeksforgeeks.org/problems/maximum-of-all-subarrays-of-size-k/0
*/
#include<iostream>
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n,k;
	    cin>>n>>k;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    for(int i=0;i<=n-k;i++)
	    {
	        int m=a[i];
	        for(int j=0;j<k;j++)
	        {
	            m=max(m,a[i+j]);
	        }
	        cout<<m<<" ";
	    }
	    cout<<endl;
	}
	return 0;
}

max1.cpp

#include<bits/stdc++.h>
using namespace std;
void slidingWindow(int a[],int n,int k)
{
    deque<int> q;
    int i;
    for(i=0;i<k;i++)
    {
        while(!q.empty() && a[q.back()]<=a[i])
            q.pop_back();
        q.push_back(i);
    }
    for(;i<n;i++)
    {
        cout<<a[q.front()]<<" ";
        while(!q.empty() && q.front()<=i-k)
            q.pop_front();
        while(!q.empty() && a[q.back()]<=a[i])
            q.pop_back();
        q.push_back(i);
    }
    cout<<a[q.front()]<<" ";
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n,k;
	    cin>>n>>k;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    slidingWindow(a,n,k);
	    cout<<endl;
	}
	return 0;
}

NGE.cpp

/*
Author - Vinit Shahdeo
*/
#include<bits/stdc++.h>
using namespace std;
void printNGE(int a[],int n)
{
    stack<int> s;
    map<int,int> m;
    for(int i=0;i<n;i++)
    {
        if(s.empty())
        {
            s.push(a[i]);
            continue;
        }
        while(!s.empty() && s.top()<a[i])
        {
            m[s.top()]=a[i];
            s.pop();
        }
        s.push(a[i]);
    }
    while(!s.empty())
    {
        m[s.top()]=-1;
        s.pop();
    }
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" "<<m[a[i]]<<endl;
    }
}
int main() {
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    printNGE(a,n);
    return 0;
}

pythagorean.cpp

/*
Author - Vinit Shahdeo
LINK - https://practice.geeksforgeeks.org/problems/pythagorean-triplet/0/?ref=self
Brute force
*/
#include<bits/stdc++.h>
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    map<int,int> m;
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	        m[a[i]*a[i]]++;
	    }
	    string ans="No";
	    for(int i=0;i<n-1;i++)
	    {
	        for(int j=i+1;j<n;j++)
	        {
	            int x=a[i]*a[i]+a[j]*a[j];
	            if(m.find(x)!=m.end())
	            {
	                ans="Yes";
	                break;
	            }
	        }
	    }
	    cout<<ans<<endl;
	}
	return 0;
}

pythagorean_tri.cpp

/*
Author - Vinit Shahdeo
LINK - https://practice.geeksforgeeks.org/problems/pythagorean-triplet/0/?ref=self
Optimized
*/
#include<bits/stdc++.h>
using namespace std;
bool isTriplet(int arr[], int n)
{
    
    for (int i=0; i<n; i++)
        arr[i] = arr[i]*arr[i];
    sort(arr, arr + n);
 
    for (int i = n-1; i >= 2; i--)
    {
        int l = 0; 
        int r = i-1; 
        while (l < r)
        {
            // A triplet found
            if (arr[l] + arr[r] == arr[i])
                return true;
 

            else if(arr[l]+arr[r]>arr[i])
            {
                r--;
            }
            else
            {
                l++;
            }
        }
    }

    return false;
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
        if(isTriplet(a,n))
        cout<<"Yes"<<endl;
        else
        cout<<"No"<<endl;
	}
	return 0;
}

reverse_stack.cpp

/* Reverse a stack using recursion */
#include <iostream>
#include <stack>

using namespace std;

stack<int> S, R; // S is original stack, R is reversed stack

void reverseStack() {
    if(!S.empty()) {
        R.push(S.top());
        S.pop();
        reverseStack();
    }
    return;
}

int main() {
    S.push(1);
    S.push(2);
    S.push(3);
    S.push(4);
    S.push(5);

    reverseStack();

    // Check if R is reversed
    while(!R.empty()) {
        cout << R.top() << " ";
        R.pop();
    }
    return 0;
}

sort0_1_2.cpp

/*
@Author-VinitShahdeo
Link - https://practice.geeksforgeeks.org/problems/sort-an-array-of-0s-1s-and-2s
*/
#include<bits/stdc++.h>
using namespace std;
void sort(int a[],int n)
{
    int low=0,mid=0,high=n-1;
    while(mid<=high)
    {
        switch(a[mid])
        {
            case 0: swap(a[low],a[mid]);
                    low++;
                    mid++;
                    break;
            case 1: mid++;
                    break;
            case 2: swap(a[mid],a[high]);
                    high--;
                    break;
        }
    }
}

int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    sort(a,n);
	    for(int i=0;i<n;i++)
	    {
	        cout<<a[i]<<" ";
	    }
	    cout<<endl;
	}
	return 0;
}

sort_string_using_stack.cpp

/*
Created by Vinit Shahdeo.
Link - https://ide.geeksforgeeks.org/RLP7y8gwtT
*/

#include<bits/stdc++.h>
using namespace std;
string reverse(string s)
{
    stack<char> s1,s2;
    for(int i=0;i<s.size();i++)
    {
        if(s1.empty())
        {
            s1.push(s[i]);
            continue;
        }
        if(s1.top()>=s[i])
        {
            s1.push(s[i]);
        }
        else
        {
            while(!s1.empty() && s1.top()<s[i])
            {
                s2.push(s1.top());
                s1.pop();
            }
            s1.push(s[i]);
            while(!s2.empty())
            {
                s1.push(s2.top());
                s2.pop();
            }
        }
    }
    string ans="";
    while(!s1.empty())
    {
        ans+=s1.top();
        s1.pop();
    }
    //reverse(ans.begin(),ans.end());
    return ans;
}
int main(){
    string s;
    cin>>s;
    cout<<reverse(s)<<endl;
    //cout<<s<<endl;
    return 0;
}

spanStock.cpp

/* Stack Approach 
Author - Vinit Shahdeo
Link - https://practice.geeksforgeeks.org/problems/stock-span-problem/0
*/
#include<bits/stdc++.h>
using namespace std;
void stockSpan(int a[],int n)
{
    stack<int> s;
    int span[n];
    // s.push(0);
    // span[0]=1;
    for(int i=0;i<n;i++)
    {
        if(s.empty())
        {
            s.push(i);
            span[i]=1;
            continue;
        }
        while(!s.empty() && a[s.top()]<=a[i])
        {
            s.pop();
        }
        if(!s.empty())
        span[i]=i-s.top();
        else
        span[i]=i+1;
        s.push(i);
    }
    for(int i=0;i<n;i++)
    {
        cout<<span[i]<<" ";
    }
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int price[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>price[i];
	    }
	    stockSpan(price,n);
	    cout<<endl;
	}
	return 0;
}

spiral_matrix.cpp

/* Author - Vinit Shahdeo 
Link - https://practice.geeksforgeeks.org/problems/spirally-traversing-a-matrix/0
*/
#include<iostream>
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n,m;
	    cin>>n>>m;
	    int a[n][m];
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            cin>>a[i][j];
	        }
	    }
	    int top=0,bottom=n-1;
	    int left=0,right=m-1;
	    int dir=0;
	    while(top<=bottom && left<=right)
	    {
	        if(dir==0)
	        {
	            for(int i=left;i<=right;i++)
	            cout<<a[top][i]<<" ";
	            top++;
	        }
	        else if(dir==1)
	        {
	            for(int i=top;i<=bottom;i++)
	            {
	                cout<<a[i][right]<<" ";
	            }
	            right--;
	        }
	        else if(dir==2)
	        {
	            for(int i=right;i>=left;i--)
	            cout<<a[bottom][i]<<" ";
	            bottom--;
	        }
	        else if(dir==3)
	        {
	            for(int i=bottom;i>=top;i--)
	            cout<<a[i][left]<<" ";
	            left++;
	        }
	        dir=(dir+1)%4;
	    }
	    cout<<endl;
	}
	return 0;
}

stockSpan.cpp

/* Naive Approach 
Author - Vinit Shahdeo
Link - https://practice.geeksforgeeks.org/problems/stock-span-problem/0
*/
#include<iostream>
using namespace std;
void stockSpan(int a[],int n)
{
    int span[n];
    span[0]=1;
    for(int i=1;i<n;i++)
    {
        int j=i-1;
        while(j>=0 && a[i]>=a[j])
        {
            j--;
        }
        span[i]=i-j;
    }
    for(int i=0;i<n;i++)
    {
        cout<<span[i]<<" ";
    }
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int price[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>price[i];
	    }
	    stockSpan(price,n);
	    cout<<endl;
	}
	return 0;
}

string_permutations.cpp

/*
Author - Vinit Shahdeo
URL - https://practice.geeksforgeeks.org/problems/permutations-of-a-given-string/0
*/
#include<bits/stdc++.h>
using namespace std;
void permutate(string s,int l,int r)
{
    if(l==r)
    cout<<s<<" ";
    for(int i=l;i<=r;i++)
    {
        swap(s[l],s[i]);
        permutate(s,l+1,r);
        swap(s[l],s[i]);
    }
}
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    string s;
	    cin>>s;
	    sort(s.begin(),s.end());
	    permutate(s,0,s.size()-1);
	    cout<<endl;
	}
	return 0;
}

subarraySum.cpp

#include<iostream>
/* Link - https://practice.geeksforgeeks.org/problems/zero-sum-subarrays/0 */
using namespace std;
int main()
 {
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++)
	    {
	        cin>>a[i];
	    }
	    int j=0;
	    int sum=0;
	    int count=0;
	    for(int i=0;i<n;i++)
	    {
	        sum+=a[i];
	        if(sum==0)
	        count++;
	        if(i==n-1)
	        {
	            i=j;
	            j=i+1;
	            sum=0;
	        }
	    }
	    cout<<count<<endl;
	}
	return 0;
}