LEETCODE SOLUTIONS

 VALID PARENTHESIS

REFER

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

bool isValid(string s) {

        stack<char>st;

        for(int i = 0; i < s.length(); i++){

            switch(s[i]){

                case '(':

                case '{':

                case '[':

                    st.push(s[i]);

                    break;

                case ')':

                    if(st.empty() || st.top() != '(')

                        return false;

                    else 

                        st.pop();

                        break;

                case '}':

                    if(st.empty() || st.top() != '{')

                        return false;

                    else 

                        st.pop();

                        break;

                case ']':

                    if(st.empty() || st.top() != '[')

                        return false;

                    else 

                        st.pop();

                        break;      

            }

        }

        return st.empty();

    }

BEST TIME TO BUY AND SELL STOCKS - 1

REFER

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

int maxProfit(vector<int>& prices) {

        int minSoFar = prices[0];

        int maxProfit = 0;

        for(int i = 0; i < prices.size(); i++){

            //minSoFar = minSoFar < prices[i] ? minSoFar : prices[i];

            minSoFar = min(minSoFar, prices[i]);

            int profit = prices[i] - minSoFar;

            maxProfit = max(profit, maxProfit);

            //if(profit > maxProfit)

                // maxProfit = profit;

        }

        return maxProfit;

    }

BEST TIME TO BUY AND SELL STOCKS - 2

REFER

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

int maxProfit(vector<int>& prices) {

        int totProfit = 0;

        for(int i = 1; i < prices.size(); i++){

            if(prices[i] > prices[i-1])

                totProfit += prices[i] - prices[i-1];

        }

        return totProfit;

    }

AVERAGE OF LEVELS IN BINARY TREE

REFER

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10-5 of the actual answer will be accepted.

vector<double> averageOfLevels(TreeNode* root) {

        vector<double>res;

        if(root == NULL)

            return res;

        queue<TreeNode*>q;

        q.push(root);

        long long sum = 0;

        int NodeCount = 0, n = 0;

        while(!q.empty()){

            NodeCount = q.size();

            n = NodeCount;

            sum = 0;

            while(NodeCount > 0){

                TreeNode* tmp = q.front();

                q.pop();

                sum += tmp->val;

                if(tmp->left != NULL)

                    q.push(tmp->left);

                if(tmp->right != NULL)

                    q.push(tmp->right);

                NodeCount--;

            }

            double avg = (double)sum/n;

            res.push_back(avg);

        }

        return res;

    }

BALANCED BINARY TREE

REFER

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

int height(TreeNode* node){

        if(node == NULL)

            return 0;

        int lh = height(node->left);

        int rh = height(node->right);

        return 1 + max(lh, rh);

    }

    bool isBalanced(TreeNode* root) {

        if(root == NULL)

            return true;

        if(abs(height(root->left) - height(root->right)) <= 1)

            return isBalanced(root->left) && isBalanced(root->right);

        return false;

    }