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);
    }
};