Mac keyboard shortcuts

To go to/show desktop - Combination of Fn + F11 (This works only if the current window is not in full screen mode)

Page up - Command + up arrow key
Page down - Command + down arrow key
Copy - Command + C
Paste - Command +  V
Cut - Command + X
Command + Space - Open spotlight

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