The problem of the Day

LeetCode + GeeksforGeeks { 11–09–2021 }

Basic Calculator

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

CODE — >

int calculate(string s) 
{
    int result=0;
    int sign=1; //1 represents +ve -1 represents -ve
    int j=0;
    int len=s.length();
    stack<int> stk;
        
    while(j<len)
    { 
        if(s[j]=='+')
            //get +ve the number
            sign=1;
            
        else if(s[j]=='-')
            //get -ve the number
            sign=-1;
            
        else if(isdigit(s[j]))
        {
            //get the number 
            int num=s[j]-'0';
            while(j+1<len && isdigit(s[j+1]))
            {
                num=num*10+(s[j+1]-'0');
                j++;
            }
                
            //now add it to the result along with sign
            result+=num*sign;
        }
        else if(s[j]=='(')
        {
            //we push the current result and current sign into the stack
            stk.push(result);
            stk.push(sign);
            result=0;
            sign=1;
        }
        else if(s[j]==')')
        {
            //get the last result and the sign from the stack
            int xsign=stk.top();
            stk.pop();
                
            int xresult=stk.top();
            stk.pop();
                
            //add the curr result in parenthesis to prev result and update the entire result
            result=result*xsign + xresult;
            //xsign will be the sign before the begin of parenthesis
        }
        j++;
    }
    return result;
}

Max Rectangle

Example 1:

Input:
n = 4, m = 4
M[][] = {{0 1 1 0},
         {1 1 1 1},
         {1 1 1 1},
         {1 1 0 0}}
Output: 8
Explanation: For the above test case the
matrix will look like
0 1 1 0
1 1 1 1
1 1 1 1
1 1 0 0
the max size rectangle is 
1 1 1 1
1 1 1 1
and area is 4 *2 = 8.

CODE →

int maxArea(int M[MAX][MAX], int n, int m) 
{
    //Code here
    int result = maxHist(M[0], m);
 
    for (int i = 1; i < n; i++) 
    {
        for (int j = 0; j < m; j++)
            if (M[i][j])
                M[i][j] += M[i - 1][j];
        result = max(result, maxHist(M[i], m));
    }
    return result;
}

Don’t forget to give us your 👏 !