Leetcode 46 Permutations Solutions

Problem Statement could be found @https://leetcode.com/problems/permutations/

class Solution {
   
    vector<vector<int>> retvec;
public:

void swap(vector<int> &nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

void helper(vector<int> &nums, int index){
    if (index == nums.size()){
        retvec.push_back(nums);
        return ;
    }
    for (int i=index; i< nums.size();i++){
       
        swap(nums, i, index);
        helper(nums, index+1);
        swap(nums, i, index);
    }
   
}
    vector<vector<int>> permute(vector<int>& nums) {
       
        helper(nums,0);
        return retvec;
    }
};

Leetcode 31 : Next Permutation Solution

Problem Statement could be found @https://leetcode.com/problems/next-permutation/

Approach-
There are 2 ways to solve this problem:

Way 1:
1. Find all permutations,then sort them.
2. Search for the input permutation and then select the next one

Way 2:
Let us understand this by an example. Assume the input is
2, 5,4,1

If we start from the last element  can we put 1 anywhere to get a larger permutation.
Answer is No
Now lets analyze 2nd element, can we put it anywhere to get a larger permutation.
Answer is Yes. We can swap it with 2 and get a larger permutation.
But is it the next largest of input ? No. But it moves us in the right direction
If we swap, then our input would be 4,5,2,1
Here we if we sort elements except 4 then we get our answer.Which would be 4,1,2,5

But how do we fix on 4 to be swapped? So lets look another time & try to refine.

Can we swap (1 and 4) to get a higher perm?
No
Can we swap (4 and 5) to get a higher perm?
No
Can we swap (2 and 5) to get a higher perm?
Yes. But it won't give the result.
Only thing it tells is 2 is eligible candidate for removal.Why?
Because there is at least one larger element on right side. Now how do we find ideal candidate?

The definition of ideal candidate is "Smallest element on the right side which is larger than 2".
Once you find the ideal candidate swap it with 2. Swapping would ensure left seq till 2 are in order.
Now you have to only worry about getting smallest sequence on right of 2. How do we get it?
Use sorting:)

Following is the code for it


Code Snippet:

class Solution {
public:

void swap(vector<int> &nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] =temp;
 
}
 int getElementIndex(vector<int> &nums,int val,int index){
    int minVal = nums[index];
    int minIndex =index;
    while (index < nums.size()){
        if ((nums[index] > val) &&(minVal > nums[index])){
            minVal = nums[index];
            minIndex = index;
           
        }
        index ++;
       
    }
    return minIndex;
 }
   
    void nextPermutation(vector<int>& nums) {
        for (int i=nums.size()-1;i>0;i--)    {
            if (nums[i-1] < nums[i]){
                int index =getElementIndex(nums,nums[i-1],i);
                swap(nums, index,i-1);
                sort(nums.begin()+i,nums.end());
                return ;
            }
        }
        sort(nums.begin(),nums.end());
    }
};

Leetcode 40. Combination Sum II Solution

Problem Statement could be found @ https://leetcode.com/problems/combination-sum-ii/

Approach-
1. Sort the number.This will give an ordering to the numbers
2. Start with a number and keep on adding next number
     A. If their sum is more than target then this is invalid combination, so don't add any more numbers.
    B. If the sum is less than target then more numbers could be added
    C. If the sum is equal to target, then we have our answer. But We need to be careful not to try same combination again.

Code Snippet-

class Solution {
    vector<vector<int>> retvec;
public:

  void helper(vector<int> &nums, int index, int target, vector<int> &temp, int sum){
      if (sum == target){
          retvec.push_back(temp);
          return;
         
      }
     
      for (int i=index;i< nums.size();i++){
          if ((i > index) && (nums[i]==nums[i-1])){
              continue;
          }
          if ((nums[i]+sum) > target){
              return;
          }
          temp.push_back(nums[i]);
          helper(nums, i+1, target, temp, sum+nums[i]);
          temp.pop_back();
      }
  }
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> temp;
        int sum=0;
        helper(nums,0, target, temp, sum);
        return retvec;
    }
};

Leetcode 60: Permutation Sequence Solution

Problem Statement could be found @https://leetcode.com/submissions/detail/85159040/



Code Snippet:

class Solution {
public:
    string getPermutation(int n, int k) {
        k=k-1;
        string str="";
        for (int i=0;i<n;i++){
            char x = '0'+i+1;
            str = str.append(1,x);
        }
       
   
       
        int div = 1;
        int counter = n-1;
        while (counter > 1){
            div =div * counter;
            counter--;
        }
       
        string temp="";
        counter =n-1;
        while ( k>0){
            int index = k/div;
            temp = temp + str.at(index);
            str = str.erase(index,1);
           
            k = k%div;
            div = div/counter;
            counter--;
            if (div == 0){
                div=1;
            }
        }
        temp = temp+str;
        return temp;
    }
};

Leetcode 70 : Climbing Stairs Solutions

Problem Statement could be found @https://leetcode.com/problems/climbing-stairs/

Approach -
Let us consider n =5

Initially we are at Step 0
How many ways to reach :

Step 1 : There is only 1 way ie by taking 1 step at step 0
Step 2 : There are 2 ways - By taking 1 step at step 1 or by taking 2 steps at step 0
 so f(2) = f(0) + f(1)
Step 3- We can reach from step 1 and step 2 both. If we come from step 1,then there is 1 way.
If we come from step 2, then there are 2 ways ( as to reach step 2 from step 0 there were 2 ways)
So again f(3) = f(2) + f(1)

Similarly, for f(4) = f(3) + f(2)

So this is coming up like a recursion which when generalized would take form of
 f(n) = f(n-2) + f(n-1)

This relation is Fibonacci series



Code Snippet -


class Solution {
public:
    int climbStairs(int n) {
        int f1=0;
        int f2 = 1;
       
        int count =0;
       
        while (count <n){
            int temp = f1 + f2;
            f1 = f2;
            f2 = temp;
            count++;
           
        }
        return f2;
    }
};

Leetcode 22 : Generate Parentheses Solution

Problem Statement could be found @https://leetcode.com/problems/generate-parentheses/

Approach -

1.Take a char array of size 2*n.
2. At every value of n try putting '(' or ')'. Reduce count of open brackets and closed brackets
3. If both open brackets & close brackets count reduce to 0,then it means we have  got one combination
4. A condition to take care is - never count of open brackets is greater than close brackets as it would result in wrong code formation

Code Snippet-

class Solution {
public:
    vector<string> retVec;
   
    void helper(int open ,int close, int n, char *x,int index){
        if ((open == 0) && (close ==0)){
            retVec.push_back(x);
            return;
        }
        //results in wrong formation
        if (open > close){
            return;
        }
       
        if (open > 0){
            x[index] = '(';
            helper((open-1),close, n, x, index+1);
        }
       
        if (close > 0){
            x[index] = ')';
            helper(open,close-1, n, x, index+1);
        }
    }
   
    vector<string> generateParenthesis(int n) {
        char *ptr = new char[2*n+1];
        ptr[2*n] = 0;
        helper(n,n,n,ptr,0);
        return retVec;
    }
};

Leetcode 15 : 3Sum Solution

Problem Statement could be found @https://leetcode.com/problems/3sum/

Approach -
A brute force solution like below is simple
1. Fix one element and then find next 2 elements such that sum of 3 elements becomes zero
2. In a random shuffled array above point would be O(n*n*n)

We can try optimizing above
1. Let us try to sort the array first O(nlogn)
2. Now start from first  element (lets say i), pick (i+1)th element and last element. Sum of these 3 if zero then we have one solution. Otherwise, if it is less than zero, then increase (i+1) else decrease last.
3. Trying step 2 in a for loop would give us result but it would have duplicates
4. We can eliminate duplicates by few additional checks as in code below



Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> retVec;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
         
            int a =  nums[i];
            if (a >0){
                break;
            }else {
                while((i<nums.size()) && (i>0) && (nums[i] == nums[i-1] )){
                    i++;
                }
            }
            a = nums[i];
            int j = i+1;
            int k = nums.size()-1;
           
            while(j <k){
                int comp = a + nums[j] + nums[k];
                if (comp == 0){
                    vector<int> v;
                    v.push_back(a);
                    v.push_back(nums[j]);
                    v.push_back(nums[k]);
                    retVec.push_back(v);
                    j++;
                    k--;
                    while ( (j <k) &&(nums[j] == nums[j-1]) ){
                        j++;
                    }
                    while ( (j <k) &&(nums[k] == nums[k+1]) ){
                        k--;
                    }
                 
                }
                if (comp < 0){
                    j++;
                }
                if (comp>0){
                    k--;
                }
               
            }
        }
        return retVec;
    }
};

Leetcode 20 : Valid Parentheses Solution

Problem Statement could be found @https://leetcode.com/problems/valid-parentheses/

Approach -

1. Take a stack and start iterating over the string.
2. Push open bracket of any type to the stack
3. Whenever a closing bracket is encountered compare it with top element of stack.
     a. If both elements are same, then remove the top most element of stack.
     b. If both are different then it is an error straight away
4. If at last stack is not empty, then it is error scenario which implies opening brackets are more than closing ones
5. There is one more scenario in which error can occur. It is where there is a closing symbol at starting of string or after equilibrium state. Ex: ][] or []{}]
In this scenario stack would be empty and a closing symbol would be encountered


Code :
class Solution {
   
    stack<char> st;
    char closeBrace,sqBrackeClose, curlyBraceClose ;
    char openBrace, sqBrackeOpen, curlyBraceOpen;
   
public:
    void init(){
        closeBrace = ')';
        openBrace = '(';
        sqBrackeClose = ']';
        sqBrackeOpen = '[';
        curlyBraceClose = '}';
        curlyBraceOpen = '{';
    }
    bool isValid(string s) {
        init();
        for (int i=0;i<s.size();i++){
            char x = s.at(i);
            if ((x == curlyBraceClose ) || (x == sqBrackeClose ) || (x == closeBrace)){
                if (st.size() == 0){
                    return false;
                }else{
                    char atTop = st.top();
                    if (
                        ( (atTop == curlyBraceOpen) && (x == curlyBraceClose) )
                            || ( (atTop == sqBrackeOpen) && (x == sqBrackeClose) )
                            || ( (atTop == openBrace) && (x == closeBrace ) )
                        ){
                           
                            st.pop();
                        }else{
                            return false;
                        }
                }
            }else{
                st.push(x);
            }
           
        }
        return (st.size() == 0);
    }
};

Leetcode 49 : Group Anagrams Solution

Problem Statement could be found @https://leetcode.com/problems/anagrams/

Approach -
1. To put all anagrams of a string together we need some way to bucket, so that all anagrams land up in same bucket
2. To get to bucket we can use integer hashing but problem there would be collision.
3. To avoid collision we are using a string key (acting as a hash). For each string we take the smallest string lexicographic-ally which can be created from it as the hash key and store the all strings which have occurred so far.

Following is the code snippet

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
          map<string, vector<string>> m;
         
          for (int i=0; i<strs.size();i++){
             
              string s = strs[i];
              sort(s.begin(), s.end());
              vector<string> v;
              if(m.count(s) >0){
                  v = m[s];
              }
              v.push_back(strs[i]);
              m[s]=v;
          }
         
          vector<vector<string>> retvec;
          for(auto a=m.begin(); a!= m.end(); a++){
              retvec.push_back(a->second);
          }
          return retvec;
    }
};

Leetcode 39 : Combination Sum solution

Problem Statement could be found @ https://leetcode.com/problems/combination-sum/

Approach - Let us consider the example given in  problem statement itself.

input - [2, 3, 6, 7]
target - 7

Here, we have to consider each element multiple times so we will first start with 2
So, first we pick 2,2,2,2 then sum becomes 8, so noway picking 2 or any other number from input another time would give us desired target. And Hence we need to go back

Now, when we go back we have 2,2,2 and next number we pick up is 3.Again sum is 9,so we need to go back. Similarly, we pick  6 & 7 next. This step could have been optimized to short circuit at 2,2,2,2 itself, but here I'm not doing that much optimization.

Next we go back and have 2,2. Next number picked up is 3. So the sum becomes 7 which is desired . Hence we store it in output.

Points to consider
1. The input array may not be sorted so it is better to sort it initially
2. Since numbers are not negative, we can leverage on total sum being greater than target to stop
3. At every step we are almost doing the same step hence recursion can be used and point 2 can be used as terminating condition for recursion


Code Snippet-

class Solution {
    vector<vector<int>> retvec;
    vector<int> val;
    int target;
public:
void helper(int index, int sum, vector<int> &v){
   
    if (sum > target){
        return;
    }
   
    if ( sum == target){
        retvec.push_back(v);
        return;
    }
   
    for (int i=index;i<val.size();i++){
        v.push_back(val[i]);
        helper(i, sum+val [i],v);
        v.pop_back();
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        this->target = target;
       
        val = candidates;
        sort(val.begin(), val.end());
        vector<int> v;
        helper(0,0,v);
        return retvec;
    }
};

Leetcode17 : Letter Combinations of a Phone Number Solution

Problem statement could be found @https://leetcode.com/problems/letter-combinations-of-a-phone-number/

This code is very simple and just works on the recursion.

Approach -
1. Create a mapping of digits and corresponding characters
2. For each digit given in the input,  pick  one character at a time from the mapping and then move to next digit.

Code snippet -

class Solution {
public:
    map<char, string> dict;
    string digits;
    vector<string > retvec;
    void init(){
        dict[2] = "abc";
        dict[3] = "def";
        dict[4] = "ghi";
        dict[5] = "jkl";
        dict[6] = "mno";
        dict[7] = "pqrs";
        dict[8] = "tuv";
        dict[9] = "wxyz";
    }
    void helper( int index, string s){
        if ( index >= digits.length()){
            retvec.push_back(s);
            return ;
        }
        string x = dict[digits[index]-'0'];
        for ( int i=0;i<x.length();i++){
            helper(index+1, s+ x[i]);
           
        }
    }
    vector<string> letterCombinations(string digits) {
        this-> digits = digits;
        if ( digits.length() == 0){
            return retvec;
        }
        init();
        string s;
        helper(0, s);
        return retvec;
    }
};

Solution to Leetcode 9 : Palindrome Number

Problem statement could be found@ https://leetcode.com/problems/palindrome-number/

Approach - Reverse the actual number and then compare it with original.If two number are same, then the given number is palindromic

Points to remember
1. Negative numbers never palindromic
2. Integer might overflow on reversal, hence it is important to store it in long variable

Following is the code snippet

class Solution {
public:
    int reverse(long x, long a){
        if (x==0){
            return a;
        }else{
            a=a*10+x%10;
            return reverse(x/10,a);
        }
    }
    bool isPalindrome(int x) {
      if (x<0)
        return false;
      long temp = x;
      long y = reverse(x,0);
      return (x==y);
    }
};

Leetcode 7 : Reverse Integer Solution

Problem statement could be found @https://leetcode.com/problems/reverse-integer/

Analysis -

The solution (code)  to this problem is very simple, but there are two points should be taken care of -

1. While reversing a integer, there  might be an overflow ie reversed integer might not fit into an integer value, so to store the reversed value  in a long variable.
2. Once the final value is calculated, check whether it fits in integer range or not. If not, then return 0


class Solution {
public:
    int reverse(int x) {
       long rev=0;
       
        while (x != 0){
            rev = (rev * 10) + x%10;
            x = x/10;
        }
        if( (rev > INT_MAX) || (rev < INT_MIN))
            rev = 0;
        return rev;  
    }
};

LeetCode 441: Arranging Coins Solution

Problem Statement could be found @https://leetcode.com/contest/11/problems/arranging-coins/


Code Snippet - Code, I believe, is self explainatory

class Solution {
public:
    int arrangeCoins(int n) {
       int i = 1;
       if (n ==0)
        return 0;
       while ( (n-i) >=0){
           n = n-i;
           i++;
         
       }
     
       return (i-1);
    }
};

Leetcode 3: Longest Substring Without Repeating Characters

Problem statement could be found @https://leetcode.com/problems/longest-substring-without-repeating-characters/

Code Snippet -


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        long start = 0;
        long current =0;
        long arr[256];
        for (int i=0;i<256;i++)
            arr[i]= -1;
        int maxL = 0;
       
        while(current < s.size()){
            int x = s.at(current);
         
            // if character has already occurred
            if (arr[x] != -1 ){
                // if the current character, has just repeated
                if ( ( arr[x] +1) == current){
                    start = current;
                }else{
                    // to handle string like "abcdbx", here second occurence of b changes the start index
                    if (start <= arr[x])
                        start = arr[x] +1;
                   
                }
            }
            if ((current-start+1) > maxL){
                 maxL = current-start+1;
            }
            arr[x] = current;
           
            current++;
        }
     
        return maxL;
    }
};

Leetcode 2: Add Two Numbers Solution

Problem statement could be found @https://leetcode.com/problems/add-two-numbers/

Solution-

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
       
        if (l1 == NULL)                                
            return l2;
        if (l2 == NULL)
            return l1;
       
        ListNode *sNode = new ListNode((l1->val+l2->val)%10);              
        int carry = (l1->val+l2->val)/10;
        ListNode *temp = sNode;
        l1 = l1->next;
        l2= l2->next;
       
        while (l1 != NULL && l2!=NULL){
           int v = l1->val+l2->val + carry;  
           temp->next = new ListNode(v%10) ;
           carry = v/10;
           temp = temp->next;
           l1 = l1->next;
           l2 = l2->next;
        }
        ListNode *p = NULL;
        if (l1 == NULL && l2 !=NULL){
            p = l2;
        }
        if (l2 == NULL && l1 !=NULL){
            p = l1;
        }  
        while (p!=NULL){
           int v = p->val+ carry;  
           temp->next = new ListNode(v%10) ;
           carry = v/10;
           temp = temp->next;
           p = p->next;
         
        }
        if (carry !=0){
            temp->next = new ListNode(carry);
        }
        return sNode;
    }                                                                                                                                                          
   
};

Status - Accepted by Leetcode

Leetcode 1: Two Sum Solution

Problem statement could be found @https://leetcode.com/problems/two-sum/


Code Snippet -

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> retVec;
        int vSize = nums.size();
        for (int i=0;i<vSize;i++){
            int cur = nums[i];
            for (int j=(i+1);j<vSize;j++){
             
                if ((cur + nums[j]) == target){
                     retVec.push_back(i);
                    retVec.push_back(j);
                     return retVec;
                }
            }
        }
          return retVec;
    }
};

Status - Accepted
Runtime: 386 ms

Leetcode 437: Path Sum III Solution

Problem Statement could be found @https://leetcode.com/problems/path-sum-iii/

Solution -
Idea is to save the sum of all intermediate nodes  from Root Node to a given node. Try adding the value of current nodes to all the stored values and compare it with the required value. To store all required value we can use stack. Here, I'm using vector to implement Stack

Following is the code which is accepted by Leetcode. It took 138 msec to execute 126 test cases

class Solution {
    int count;
    int k;
public:
    void trav(TreeNode *root, vector<int> s){
        if (root == NULL){
            return;
        }
        if (root->val == k){
            count++;
        }
        vector<int> temp;
        for (int i=0;i<s.size();i++){
            if ((s[i] + root->val) == k){
                count ++;
               
            }
            temp.push_back(s[i] + root->val);
        }
        temp.push_back(root->val);
        trav(root->left, temp);
        trav(root->right, temp);
        temp.pop_back();
    }
    int pathSum(TreeNode* root, int sum) {
        count = 0;
        k = sum;
        vector<int> s;
        trav(root, s);
        return count;
    }
};

Solution to Leetcode 423: Reconstruct Original Digits from English

Problem statement could be found @https://leetcode.com/problems/reconstruct-original-digits-from-english/


Thought process -

The first approach that came to my mind was recursion + backtracking, but given the length of input string could go upto 50,000 there was a high possibility of the solution giving timeout.

Next I started thinking of unique properties of the number strings, there is realized there some unique characters in number like
1. x in six, x does not occur in any other number
2. w in two, w also does not occur in any other number
3. u in four, u doesn't occur in any other number
4. Similarly, z in zero & g in eight

So it is extremely easy to identify number like two,six, four, zero and eight. But what about other numbers? So, lets see what are the remaining numbers
one, three,  five,  seven, nine.

Lets check the uniqueness in above numbers
1. o in one
2. t in Three
3. s in Seven
4. f in Five
5. i in Nine

Hence, finding the count of o, t, s, f and i, we  can get remaining characters.

Following is the code, the solution is accepted by Leetcode and runs in 26 msec for all testcases

class Solution {
    map<char, string> uDict;
    map<char, int> uMap;
 
    map<char, string> sDict;
    map<char, int> sMap;
    int handled;
    int toHandle ;
public:
    void uDigit(){
        uDict['z'] = "zero";
        uDict['w'] = "two";
        uDict['g'] = "eight";
        uDict['u'] = "four";
     
        uDict['x'] = "six";
     
        uMap['z'] = 0;
        uMap['w'] = 2;
        uMap['g'] = 8;
        uMap['u'] = 4;
   
        uMap['x'] = 6;
     
    }
 
    void sDigit(){
        sDict['t'] = "three";
        sDict['o'] = "one";
        sDict['s'] = "seven";
        sDict['i'] = "nine";
        sDict['f'] = "five";
        sMap['t'] = 3;
        sMap['o'] = 1;
        sMap['s'] = 7;
        sMap['i'] = 9;
        sMap['f'] = 5;
    }
 
    bool  rem(int arr[], int count, string str){
        for (auto s=str.begin(); s != str.end();s++){
            if ( arr[*s-'a']  < count )
                return false;
         
        }
        for (auto s=str.begin(); s != str.end();s++){
            arr[*s-'a']  =  arr[*s-'a'] - count;
         
        }
        handled = handled+ str.size() * count;
        return true;
    }
 
    void tryUMap(int arr[],int op[],
        map<char, string> &dict, map<char, int> &numMap){
            for (auto x = dict.begin(); x!= dict.end(); x++){
                if (handled == toHandle)
                    return ;
                if (arr[x->first-'a'] != 0){
                     int count = arr[x->first-'a'] ;
                    if ( rem(arr, count, x->second) == true){
                     
                        op[numMap[x->first] ] = op[numMap[x->first] ] + count;
                    }
                 
                 
                }
            }
        }
 
    string originalDigits(string s) {
        handled = 0;
        uDigit();
        sDigit();
        int arr[26] = {0};
        toHandle = s.size();
   
        for (int i=0;i<s.size();i++){
            arr[s.at(i) - 'a'] ++;
        }
        int op[10] = {0};
     
     
        tryUMap(arr,op,uDict, uMap);
     
        tryUMap(arr,op,sDict, sMap);
        std::ostringstream oss;
        string os="";
        for (int i=0;i<10;i++){
            while (op[i] != 0){
                oss <<i;
                op[i]--;
            }
        }
       return oss.str();
    }
};

Solution to leetcode 315 Count of Smaller Numbers After Self

Problem statement could be found @https://leetcode.com/problems/count-of-smaller-numbers-after-self/

Analysis
This problem can have another form where one is asked to find number of inversions.

Approach
Use merge sort technique ie divide collection (here vector) into smaller parts and count inversions.

Following is the code -
1. Here I'm using a map to count inversions for an integer, hence the limitation of this code it doesn't work with duplicates.
2. Another important point is I'm filling the greatest element in vector first during merge. It helps simplify the code by following logic. So if an element is left half is larger than current element of right half, then following formula gives the count of element in right half with which left element is larger

   valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                                                  (rightBoundary - right + 1);

We could have tried filling smaller element first, in that case finding inversions would have taken a for loop.


class Solution {
    map<int, int> valMap;
private:
    void applyMerge(vector<int> &nums, int startIndex, int endIndex){
        if (startIndex >= endIndex){
            return ;
        }
       
        int midIndex = (startIndex+endIndex)/2;
        applyMerge(nums, startIndex, midIndex);
        applyMerge(nums, (midIndex+1),endIndex);
       
        int left = startIndex;
        int right = midIndex+1;
        int leftBoundary = midIndex;
        int rightBoundary = endIndex;
       
        vector<int> temp;
        while ((left<=leftBoundary) && (right<=rightBoundary)){
            if (nums[leftBoundary] > nums[rightBoundary]){
                valMap[nums[leftBoundary]] = valMap[nums[leftBoundary]] +
                                    (rightBoundary - right + 1);
                temp.insert(temp.begin(),nums[leftBoundary] ) ;
                leftBoundary--;
            }else{
                temp.insert(temp.begin(),nums[rightBoundary] ) ;
                rightBoundary--;
            }
        }
        while (right <= rightBoundary){
            temp.insert(temp.begin(),nums[rightBoundary] ) ;
            rightBoundary--;
        }
        while (left<=leftBoundary){
            temp.insert(temp.begin(),nums[leftBoundary] ) ;
            leftBoundary--;
        }
       
        for (int i=0;i<=(endIndex-startIndex);i++){
            nums[i+startIndex] =  temp[i];
        }
     
    }
public:
   
    vector<int> countSmaller(vector<int>& nums) {
        for (int i=0;i<nums.size();i++){
          valMap[nums[i]] = 0;
        }
       
        vector<int> temp(nums);
        vector<int> elemGt;
        applyMerge(nums,0, nums.size()-1);
        for (int i=0;i<temp.size();i++){
            elemGt.push_back(valMap[temp[i]]);
        }
        return elemGt;  
    }
};

Solution to Leetcode 406. Queue Reconstruction by Height

Problem statement could be found @https://leetcode.com/problems/queue-reconstruction-by-height/


Input -
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

Approach -


Arrange the inputs first in decreasing order of height, so it would start looking like
[7,0],,[7,1]
[6,1],
[5,0],[5,2]
[4,4]

Now pick one element at a time and put it at index  k

First we pick [7,0] since this is the only element O/P vector is [7,0]
Next we pick [7,1] since its index is 1 we will put it at index 1 in O/P vector [7,0],[7,1]
Next we pick  [6,1] and place it index 1 so O/P vector is [7,0],[6,1],[7,1]
Next we pick  [5,0] and place it index 0 so O/P vector is [5,0],[7,0],[6,1],[7,1]
Next we pick  [5,2] and place it index 2 so O/P vector is [5,0],[7,0],[5,2],[6,1],[7,1]
Next we pick  [4,4] and place it index 4 so O/P vector is [5,0],[7,0],[5,2],[6,1],[4,4],[7,1]

Following is the code for above logic in C++

class Solution {
    private:
    struct compare
    {
        bool operator()(const pair<int, int> &p1,const pair<int, int> &p2) const{
          // ensures greater height comes first
            if (p1.first > p2.first)
                return true;
           // if there is tiebreak in height, then put smaller k index first
            if ( (p1.first == p2.first ) && (p1.second < p2.second))  
                return true;
            return false;  
           
        }
    };
public:
    vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
       
        vector<pair<int, int>> retVal;
        if (people.size() == 0)
            return retVal;
        std::sort(people.begin(), people.end(), compare());
     
     
        retVal.push_back(people[0]);
     
        for(int i=1;i<people.size();i++){
            pair<int, int> px = people[i];
            retVal.insert(retVal.begin() + px.second, px);
         
        }
        return retVal;
    }
};

Solution to Leetcode 404 Sum of Left Leaves

Problem Description could be found @https://leetcode.com/problems/sum-of-left-leaves/

Solution

class Solution {

public:
    int helper(TreeNode* root, TreeNode *parent){
        if (root->left == NULL && root->right  == NULL && root == parent->left ){
            return root->val;
        }
       
        int rightVal = 0;
        int leftVal = 0;
       
        if (root->left != NULL)
            leftVal = helper(root->left, root);
     
       if ( root->right != NULL)
            rightVal = helper(root->right, root);
       
        return (leftVal + rightVal);
    }
    int sumOfLeftLeaves(TreeNode* root) {
        if (root == NULL )
            return 0;
        if (root->left == NULL && root->right == NULL)
            return 0;
           
     
        int num = helper(root, NULL);
        return num;
     
    }
};

Solution to Leetcode 402 Remove K Digits

Problem Statement could be found @https://leetcode.com/problems/remove-k-digits/

Approach - Idea is to start from first character of string and compare it with next character, if current character is smaller then next then it can be removed. If the very first  character is larger than second then remove it. All the while take care of zeros at the start

Following is the code
class Solution {
public:
    string truncZero(string num){
         while (num.size() > 1 && num.at(0) == '0'){
                num = num.substr(1);
         }
        return num;  
    }
    string removeKdigits(string num, int k) {
     
       
        while ( k >0){
            while (num.size() !=0 && num.at(0) == '0'){
                num = num.substr(1);
            }
            int length = num.size();
            if (length == 0){
                num = "0";
            }
            bool flag=  false;
            for (int i=0;i<length-1;i++){
               
                if ((num.at(i) ) > (num.at(i+1) )){
                    flag=  true;
                    if ( i == 0){
                        num = num.substr(1);
                       
                    }else{
                       
                        string tempStr = num.substr(0,i) ;
                        if ((i+1) < num.size()){
                           tempStr = tempStr + num.substr((i+1));
                        }
                        num = tempStr;
                    }
                    break;
                }
            }
            if (flag == false){
                num = num.substr(0,num.size()-1);
            }
           
            k--;
        }

        if (num.size() == 0)
            num = "0";
        if (num.size() > 1){
            num = truncZero(num);
        }
        return num;
    }
};

Leetcode 368. Largest Divisible Subset solution

Problem statement could be found @https://leetcode.com/problems/largest-divisible-subset/

Approach -

For every element n, check previous (n-1) elements and see if there modulo is zero. Whenever modulo is zero, store the chain length and index for the max value



Solution

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
       
        if (nums.size() <=1){
            return nums;
        }
       
        sort(nums.begin(), nums.begin() + nums.size());
        int *indexArr = new int[nums.size()];
        int *sizeArr = new int[nums.size()];
       
        for(int i=0;i<nums.size();i++){
            indexArr[i] = i;
            sizeArr[i] = 0;
        }
        int maxSize = 0;
        int maxIndex = 0;
        for(int i=0;i<nums.size();i++){
            for (int j=i-1;j>=0;j--){
                if ((nums[i]%nums[j]) == 0){
                    if (sizeArr[i] < (sizeArr[j] +1)){
                        sizeArr[i] = sizeArr[j] + 1;
                        indexArr[i] = j;
                        if (maxSize < sizeArr[i]){
                            maxSize = sizeArr[i];
                            maxIndex = i;
                        }
                    }
                   
                }
            }
        }
        vector<int> retVal;
        while (indexArr[maxIndex] != maxIndex){
            retVal.push_back(nums[maxIndex]);
            maxIndex = indexArr[maxIndex] ;
        }
        retVal.push_back(nums[maxIndex]);
        vector<int> opRetVal;
       
       for (int i=retVal.size()-1;i>=0;i--){
            opRetVal.push_back(retVal[i]);
        }
        return opRetVal;
    }
};

Leetcode 396. Rotate Function solution

Problem statement could be found @https://leetcode.com/problems/rotate-function/

Solution Approach-
Lets consider the numbers given in example [4,3,2,6] so we have following combinations
4 * 0 + 3* 1 + 2 *2 + 6 * 3
3 * 0 + 2 * 1 + 6 * 2 + 4 * 3
2 * 0 + 6 * 1 + 4 * 2 + 3 * 3
6 * 0 +  4 * 1 + 3 * 3 + 2 * 3

If one looks it closely it would seems like a sliding window for following array
4, 3,2,6,4,3,2

Above step means append  (n-1) elements to original vector.

Another optimization is  between first and second step, the difference is

In first step
Step 1. totalSum = 25
Step2. pSum = 3 +  2 + 6
Step 3. now in step2, total value has to be decreased by pSum as we shift left and now 4 * 3 has to be added, where 4 is the new element value & 3 (vector size -1).

At every slide of window these steps are applied



Following is the code

class Solution {
public:
   
    int maxRotateFunction(vector<int>& A) {
        if (A.size() == 0)
            return 0;
           
       
         if (A.size() == 1)
            return A[0]*0;
           
       int maxSum  = 0;
       int pSum = 0;
       int size = A.size();
     
       for (int i=0;i<size;i++) {
           maxSum = maxSum + (A[i] * i);
           if (i != 0 )
            pSum = pSum + A[i];
       }
       for (int i=0;i<size-1;i++){
           A.push_back(A[i]);
       }
      int gMax = maxSum;
    //  size = A.size();
      for (int i=1;i<size ;i++){
          //maxSum - pSum;
          maxSum  = maxSum - pSum + A[size+i-1] * (size - 1);
          pSum = pSum - A[i]  + A[i+size-1];
          if (maxSum > gMax)
            gMax = maxSum;
      }
      return gMax;
    }
};

Leetcode 365. Water and Jug Problem solution

Problem statement could be found @https://leetcode.com/problems/water-and-jug-problem/

Solution code

class Solution {
public:
    int getHCF(int x, int y){
         if ( y == 1)
            return 1;
        if (x%y == 0)
            return y;
        return getHCF(y, x%y);
    }
    bool canMeasureWater(int x, int y, int z) {
        if ( (x+y) < z){
            return false;
        }
        int hcf = 0;
        if (x > y)
            hcf = getHCF(x,y);
        else
            hcf = getHCF(y,x);
   
        if (z%hcf == 0)  
            return true;
        else
            return false;
    }
};

Leetcode 398. Random Pick Index solution

Problem statement could be found @https://leetcode.com/problems/random-pick-index/

Initial approach - Initially I started by creating a map of elements and their index list but this got TLE as the memory is given as constraint. The reason for this thought was index once and query multiple times.

Second approach - Compare the values on fly and save matching indexes. Then generate random value and mod by nos of instances of matching indexes, using the value received after mod to do find the index. This was accepted

Following is the code with second approach

class Solution {
 
    vector<int> elementVector;
    size_t vectorSize ;
public:
    Solution(vector<int> nums) {
      elementVector = nums;
      vectorSize = nums.size();
     
     
     
    }
   
    int pick(int target) {
        vector<int> indexVect;
        for (int i=0;i<vectorSize; i++){
            if (elementVector[i] == target)
                indexVect.push_back(i);
        }
        int indexSize = indexVect.size();
        int randVal = (rand()%indexSize);
        return indexVect[randVal];
    }
};

Leetcode 399 Evaluate Division Solution

Problem description could be found @https://leetcode.com/problems/evaluate-division/

Approach - The solution is a DFS to be done on Graph, where graph nodes are the divisor and dividends. Value obtained from result is the edge weight between divisor and dividend node

 The first idea in  my mind was to create adjacency matrix with assumption that there are only 1 length string but it failed as sample testcases had  strings like ab, cd. So had to go with Adjacency list solution. Following is the accepted code which ran in 3 msec

struct node{
  double weight;
  string adjacentNode;
 
  node (double wt, string dest){
      this->weight = wt;
      this->adjacentNode = dest;
  }
};

class Graph{
    private:
        map<string, list<node *> *> nodeMap;
    public:
        Graph(){
           
        }
        void addNode(string src, string des, double wt){
            node *tempNode = new node(wt, des);
           
            list<node *> *nodeList;
            if (nodeMap.count(src) == 0){
                nodeList = new list<node *>();
                nodeMap[src] = nodeList;
            }else{
               nodeList =  nodeMap.at(src);
            }
            nodeList->push_back(tempNode);
           
            // add in reverse way
            node *tempOppNode = new node(1.0/wt, src);
           
            list<node *> *revList;
            if (nodeMap.count(des) == 0){
                revList = new list<node *>();
                nodeMap[des] = revList;
               
            }else{
               revList =  nodeMap.at(des);
            }
            revList->push_back(tempOppNode);
        }
       
        bool contains(string key){
            if (nodeMap.count(key) != 0)
                return true;
            return false;
        }
       
        double dfs(string src, string dest, set<string> traversed){
            list<node *> *myList = nodeMap[src];
            if (traversed.find(src) != traversed.end())
                return -1.0;
               
            if (myList == NULL){
                return -1.0;
            }
            traversed.insert(src);
           for (list<node *>::iterator it=myList->begin();
                    it != myList->end() ; it++){
               node *listNode = *it;
               if (listNode->adjacentNode == dest){
                   traversed.erase(src);
                   return listNode->weight;
               }else{
                   double d = dfs(listNode->adjacentNode, dest, traversed);
                   if (d != -1.0){
                       traversed.erase(src);
                       return d * listNode->weight;
                   }
               }
           }
           traversed.erase(src);
           return -1;
        }
};


class Solution {
public:
 
    vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries) {
        Graph g ;
        for (int i=0;i<equations.size();i++)   {
            pair<string, string> val = equations[i];
            double value = values[i];
            g.addNode(val.first, val.second, value);
         
         
        }
       
        vector<double> retVal;
        for (size_t i=0;i<queries.size();i++){
            string src = queries[i].first;
            string dest = queries[i].second;
            if (src == dest){
                if (g.contains(src))
                    retVal.push_back(1.0);
                else
                    retVal.push_back(-1.0);
            }else{
                set<string> traversed;
                double d = g.dfs(src, dest, traversed);
                retVal.push_back(d);
            }
        }
        return retVal;
    }
}; 

Leetcode 395 Longest Substring with At Least K Repeating Character Solution

Problem Statement could be found @https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

Solution:-
Idea is to first count all character occurrence in a string. If a character is repeated less than k times, then is shouldn't be considered and can act string splitter.
class Solution {
    int repeatCount;
    int maxSubSize;
public:
    int helper(string s){
        int tempMaxSize = 0;
        if (s.size() < repeatCount){
            return 0;
        }
        //int tempMaxSize
        int arr[26] = {0};
        for (int i=0;i<s.size();i++){
            arr[s.at(i) -'a'] ++;
        }
       
        int startLength = 0;
        int flag = false;
        int charCount = 0;
        for (int i=startLength;i<s.size();i++){
            // this could act as breaker
            int charVal = (s.at(i) -'a');
         
            if (arr[charVal] < repeatCount){
                if (charCount == 0)
                    charCount = 1;
                string temp = s.substr(startLength,charCount);
                int tempL = helper(temp);
                if (tempL > tempMaxSize)
                    tempMaxSize = tempL;
                startLength = i+1;
                flag = true;
                charCount = 0;
            }else{
                charCount ++;
            }
        }
        if (flag == false && s.size() >= repeatCount  ){
            //maxSubSize = s.size();
            tempMaxSize = s.size();
            return tempMaxSize ;
        }else{
            string temp = s.substr(startLength);
            int tempL = helper(temp);
            if (tempL > tempMaxSize){
                tempMaxSize = tempL;
            }
        }
           
        return tempMaxSize;
    }
    int longestSubstring(string s, int k) {
        repeatCount  = k ;
        maxSubSize = 0;
        int tempMaxSize = helper(s);
        if (tempMaxSize > maxSubSize)
            return tempMaxSize;
        else
            return maxSubSize;
    }
};

Leet code 397. Integer Replacement

Problem Statement could be found @ https://leetcode.com/contest/4/problems/integer-replacement/

Solution:

There are two important points in this problem:
1. A value might be touched upon multiple times hence it is important to memoize the values
2. If the value is the max value of int (2,147,483,647) , then using just int in algo would give wrong value as for odd case 2,147,483,647 would go out integer range. Hence one should use unsigned int

Following is the code

class Solution {
    int max;
    map<unsigned int, int> valMap;
public:
    int algo(unsigned int n){
         if (n == 1)
            return 0;
        if (valMap.count(n) != 0){
            return valMap[n];
        }
        if (n%2 == 0){
            valMap[n] = integerReplacement(n/2) + 1;
            return (valMap[n]);
        }else{
            int plusOne = integerReplacement(n + 1) +1;
            int minusOne = integerReplacement(n-1) + 1;
            if (plusOne < minusOne){
                valMap.insert(pair<unsigned int,int>( n,  (plusOne )));
                return (plusOne );
            }
            else{
                valMap.insert(pair<unsigned int,int> (n, (minusOne )));
                return (minusOne );
            }
               
        }
    }
    int integerReplacement(int n) {
      unsigned int l = n;
      return algo(n);
    }
};

Solution to 376. Wiggle Subsequence

Problem Statement could be found @ https://leetcode.com/problems/wiggle-subsequence/

Solution code


class Solution {
    vector<int> smaller;
    vector<int> larger;
public:
    int wiggleMaxLength(vector<int>& nums) {
        bool addToSmall ;
        int size = nums.size();
        for (int i=size-2; i>=0;i--){
            if (nums[i] == nums[i+1]){
                nums.erase(nums.begin() + (i+1));
            }
        }
       
        if (nums.size() <= 2)
            return nums.size();
           
       int index = 0;
       int count = 0;
       while (index < (nums.size()-1)){
           if (nums[index] < nums[index+1]){
               count ++;
               index = index+1;
               while ( (nums[index] < nums[index+1]) && (index < (nums.size()-1))){
                   index++;
               }
             
           }else{
                if (nums[index] > nums[index+1]){
                   count ++;
                    while ( (nums[index] > nums[index+1]) && (index < (nums.size()-1))){
                       index++;
                   }
                }
           }
       }
       return (count+1);
    }
};

Microsoft interview experience

Telephonic Round

1. 

Given n light bulbs, write two methods. 

isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range 

The question is present at career cup https://www.careercup.com/question?id=5668664122540032

2. Given a number n, tell the count of distinct binary search trees that could be formed from it

Face to Face

Round 1:

1. Implement Singleton design pattern

2. Find majority element in an array

Round 2:

1. Given a string, return longest palindromic sub string

Leetcode 393 UTF-8 Validation Solution

Problem Statement could be found at following link

https://leetcode.com/problems/utf-8-validation/

Solution:


class Solution {
    private:
    const static int singleByteMask = 0x00000080;
    const static int multiByteFollower = 0x000000C0;
 
    const static int byte2Mask = 0x000000E0;
    const static int byte3Mask = 0x000000F0;
    const static int byte4Mask = 0x000000F8;
public:
    bool isSingleByte(int val){
           val = val & singleByteMask;
           return (val == 0);
    }
 
    bool isMultiByteFollower(int val){
        val = val & multiByteFollower;
           return (val == 128);
    }
    bool validUtf8(vector<int>& data) {
        int multiCharCount = 0;
        for (int index=data.size()-1;index>=0;index--){
            int num = data[index];
            if ( isSingleByte(num) == true){
                if (multiCharCount != 0)
                    return false;
            }else{
                if (isMultiByteFollower(num)){
                    multiCharCount++;
                    if (multiCharCount > 3)
                        return false;
                }else{
                    if (multiCharCount ==0)
                        return false;
                    else{
                        if (multiCharCount == 1){
                            num = byte2Mask & num;
                            if (num != 192){
                             
                                return false;
                            }else{
                                multiCharCount = 0;
                            }
                        }else if (multiCharCount == 2){
                             num = byte3Mask & num;
                             if (num != 224){
                               
                                return false;
                             }else{
                                multiCharCount = 0;
                             }
                        }else if (multiCharCount == 3){
                            num = byte4Mask & num;
                             if (num != 240){
                               
                                return false;
                             }else{
                                multiCharCount = 0;
                             }
                        }
                    }
                }
             
            }
        }
        return (multiCharCount ==0) ;
    }
};