Leetcode.110: Balanced Binary Tree Edit This Blog

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 depth of the two subtrees of every node never differ by more than 1.
Example 1:
Given the following tree [3,9,20,null,null,15,7]:
    3
   / 
  9  20
    /  
   15   7
Return true.

Example 2:
Given the following tree [1,2,2,3,3,null,null,4,4]:
       1
      / 
     2   2
    / 
   3   3
  / 
 4   4
Return false.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int height(TreeNode *rt){
        if (!rt)
            return -1;
        if(rt->left == NULL && rt->right == NULL)
           return 0;
        else {
            int lf = height(rt->left);
            int rf = height(rt->right);
            return max(lf,rf)+1;
        }
             
    }
    bool isBalanced(TreeNode* root) {
        if(root == NULL)
            return true;
        else if(abs(height(root->left)-height(root->right))>1)
                return false;
        else {
            bool lb = isBalanced(root->left);
            bool rb = isBalanced(root->right);
            if(lb && rb)
                return true;
            return false;
        }
    }
};



.: Edit This Blog

        



leetcode.202: happy number Edit This Blog

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy number

class Solution {
public:
    bool isHappy(int n) {
         map m;
        int squares = 0;
        while(n) {
        	squares = squares(n);
        	if(squares == 1)
        		return true;
        	if(m[squares])
        		return false;
        	else
        		m[squares]++;
        	n = squares;
		}
		return false;
    }
    
    int squares(int n) {
    	int squares = 0;
    	while(n) {
    		squares += (n%10) * (n%10);
		n /= 10; 
		}
		return squares;
	} 
    
};


if it is repeating then it s infinite loop else continue till equal to 1

leetcode.43 String: Multiply Strings Edit This Blog

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"
Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"
Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        int sz=0;
        reverse(num1.begin(),num1.end());
        reverse(num2.begin(),num2.end());
        vector > hold;
        int zeroAdd=0,carry;
        for(int i=0;i temp;
            for(int j=0;j


.

leetcode.230 BST: Kth Smallest Element in a BST Edit This Blog

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: 
You may assume k is always valid, 1 ≤ k ≤ BST s total elements.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void inorder(TreeNode *root,int k,int &ct,int &ans){
        if(!root) return;
        inorder(root->left,k,ct,ans);
        if(ct==k-1) ans=root->val;
        ct++;
        inorder(root->right,k,ct,ans);
    }
    int kthSmallest(TreeNode* root, int k) {
        int ans=INT_MIN,ct=0;
        inorder(root,k,ct,ans);
        return ans;
    }
};


.

leetcode.414 Array: Third Maximum Number Edit This Blog

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

class Solution {
public:
    int thirdMax(vector& nums) {
        int F,S,T;
        int f1=0,f2=0,f3=0;
        for(int val:nums){
            if(!f1 || val>F){
                T=S; S=F; F=val; 
                if(f2) f3=1;
                if(f1) f2=1;
                f1=1;
            }
            else if(!f2 && val=F) continue;
            else if(val>S && valT && val 


.

leetcode.581 Array: Shortest Unsorted Continuous Subarray Edit This Blog

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

using namespace std;
class Solution {
public:
    int findUnsortedSubarray(vector& nums) {
        
        int len=nums.size();
        stack stk1,stk2;
        int i=1,f=1;
        stk1.push(0); stk2.push(len-1);
        while(i=0 && nums[j]<=nums[stk2.top()])  stk2.push(j--);
        while(inums[i]) {stk1.pop(); f=0;}
            i++;
        }
        while(j>=0){
            while(!stk2.empty() && nums[stk2.top()]


.

leetcode.55 Array: Jump Game Edit This Blog

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

class Solution {
public:
    bool canJump(vector& nums) {
        int possible=0,steps=nums.size();
        for(int i=0;ipossible) break;
            possible=max(possible,i+nums[i]);
        }
        return possible>=steps-1;
    }
};


.

Leetcode.153: Sorted rotated array Edit This Blog

Array

class Solution {
    public int findMin(int[] arr) {
       
        int left = 0;
        int right = arr.length - 1;
        
        if(arr.length == 1)
            return arr[0];
        
        if(arr[left] < arr[right])
            return arr[left];
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            
            if(arr[mid] > arr[mid + 1])
                return arr[mid + 1];
            
            if(arr[mid - 1] > arr[mid])
                return arr[mid];
            
            if(arr[mid] > arr[0]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return -1;
    }
}


Array

.: Edit This Blog

        



.: Edit This Blog

        



.: Edit This Blog

        



Leetcode.palleramkashyap: 242. Valid Anagram Edit This Blog

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length())
            return false;
        
        map mp;
        
       for(char c:s)
           mp[c]++;
        for(char c:t)
        {
            if(mp.find(c)==mp.end()|| mp[c]==0)
                return false;
            mp[c]--;
        }
          return true;   
            
        }
        
    
    
};


1.Check if lengths of string s and string t are not equal. 2.If they are not equal, then t is not anagram of s. 3.If the lengths are equal, add the characters of string s to a map where each character being key and the occurrences being value. 4.Check if number of occurrences of characters in string s equal to number of characters in string t , this is done by iterating over string t and comparing the occurrences in hash map(reduce the count by 1 for every character in string t so that at the end of iteration the count becomes zero for very character at the end of loop).

.: Edit This Blog