Permutations

This is a very interesting article on permutations.

http://wordaligned.org/articles/next-permutation

For this problem, permutations is basically switching all the elements. See below for more details.
Permutations
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Idea: We start from the head element and will be exchange it with the other elements one by one while backtracking till the end.

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        int n = num.size();
       
        vector<vector<int>> ret;
        bt(ret, num,0,n-1);
       
        return ret;
    }
   
    void bt(vector<vector<int>> &r,  vector<int> num, int k, int n)
    {
        if (k==n)
        {
            r.push_back(num);
        }
        else
        {
            for (int i=k;i<=n;i++)
            {
                //switch num[i] and num[k]
                int tmp = num[i];
                num[i] = num[k];
                num[k] = tmp;
               
                bt(r,num, k+1,n);
            }
        }
    }
};

What if there are duplicates? We need to decide when to do the switches.

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > ret;
        int n = num.size();
        perm(num,0,n-1,ret);
        return ret;
    }
   
    bool swap(int k, int i, const vector<int> num){
        for (int j=k;j<i;j++){
            if (num[j]==num[i]){
                return false;
            }
        }
        return true;
    }
 
    void perm(vector<int> num, int k, int n, vector<vector<int>> &ret)
    {
        if (k==n)
        {
        ret.push_back(num);
        }
        else
        {  
            for (int i=k;i<=n;i++)
            {
                if (swap(k,i,num))
                {
                   int t = num[i];
                   num[i] = num[k];
                   num[k] = t;
           
                   perm(num, k+1,  n, ret);
       
                }
            }
        }
    }      
};

Subsets

Subsets
Given a set of distinct integers, S, return all possible subsets.
Note:
•Elements in a subset must be in non-descending order.
•The solution set must not contain duplicate subsets.

For example,
 If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

 1. (a)
I would like to call it induction
•For n=1, the set of subsets is {{}, {S[0]}}
•For n>1, find the subsets of 1,...,n-1. Make two copies of it. For one of them, add n to each subset.
Then take the union of the two copies.

For example,
•The set of subsets of {S[0]} is {{}, {S[0]}}
•For {S[0], S[1]}, take {{}, {S[0]}}, add S[1],  to each subset to get {{ S[1]}, { S[0], S[1]}} and take the union with {{}, { S[0]}} to get {{}, {S[0]}, {S[1]}, {S[0], S[1]}}
•Repeat till you reach S[n-1] (or finish all the elements)

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        if (S.empty()) return res;
       
        int n = S.size();
        sort(S.begin(),S.end());
        vector<int> empty;
        res.push_back(empty);
       
        for (int i=0; i<n; i++)
        {
            vector<vector<int>> tmp=res;
            for (int j=0; j<tmp.size();j++)
            {
                tmp[j].push_back(S[i]);
            }
           
            for (int j=0; j<tmp.size();j++)
            {
                res.push_back(tmp[j]);
            }
        }
       
        return res;
    }
};


1(b). Same idea, different implementation. 增量构造法 Ref: http://m.blog.csdn.net/blog/mysee1989/39619401

Using vector::back() will simplify the code
http://www.cplusplus.com/reference/vector/vector/back/

  vector<vector<int> > subsets(vector<int> &s) {
               vector<vector<int>> res;
             
               if (s.empty()) return res;
               sort(s.begin(), s.end());
               res.clear();
               res.resize(1);
               int n = s.size();
               for (int i = 0; i<n; i++)
                   {
                       int size = res.size();
                          for (int j = 0; j<size; j++)
                          {
                                 res.push_back(res[j]);
                                 res.back().push_back(s[i]);
                          }
                   }
                    return res;
  }

2. Backtracking with recursion. We need to set a bool vector as the solution vector a
class Solution {
public:
    vector<vector<int> > subsets(vector<int> &s) {
        vector<vector<int>> ret;
        int n=s.size();
        //if (n==0) return ret;
        sort(s.begin(),s.end());
        vector<bool> a(n,false);
        helper(s,a,ret,n,0);
       
        return ret;
    }
   
   
    void helper(vector<int> &s, vector<bool> &a, vector<vector<int>> &r, int n, int k)
    {
        if (k==n)
        {
            //process sol
            vector<int> v;
              for (int j = 0; j<n; j++)
               {
                    if (a[j] == true)
                     v.push_back(s[j]);
                   }
            r.push_back(v);
            return;
        }
        else
        {
            a[k]=true;
            helper(s,a,r,n,k+1);
            a[k]=false;
            helper(s,a,r,n,k+1);
        }
    }
};

3. This is to use an int's bits as a mask for solution vector. If i's position is 1, then choose S[i], otherwise, do not include S[i] in the solution vector.
For example, for n=3 or {1,2,3}, lets assign bits to each outcome  -> First bit to 1 , Second bit to 2 and third bit to 3
Has = 1
No = 0
0) 0 0 0  -> No 3 , No 2 , No 1 = { }
1) 0 0 1  -> No  3 , No 2 ,   Has 1       =  {1 }
2) 0 1 0  -> No 3 ,    Has 2  , No 1 = { 2 }
3) 0 1 1  -> No 3 ,    Has 2 ,      Has 1    = { 1 , 2 }
4) 1 0 0  ->    Has 3      , No  2  , No 1 = { 3 }
5) 1 0 1  ->    Has 3      , No  2  ,     Has 1     = { 1 , 3 }
6) 1 1 0  ->    Has 3      ,    Has 2       , No 1 = { 2 , 3 }
7) 1 1 1  ->    Has 3     ,      Has 2     ,      Has 1     = { 1 , 2 , 3 }

class Solution {
public:
    vector<vector<int> > subsets(vector<int> &S) {
        vector<vector<int>> res;
        if (S.empty()) return res;
       
        sort(S.begin(),S.end());
        int n=S.size();
       
        int numVec = pow(2,n);
       
        for (int i=0; i<numVec; i++)
        {
            vector<int> v;
            for (int j=0; j<n; j++)
            {
                if (i&1<<j)
                    v.push_back(S[j]);
            }
            res.push_back(v);
            v.clear();
        }
      
       return res; 
    }
};

Search Insert Position

Problem:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

Solution:
This is relatively simple problem, just a small modification of the binary search. Pay attention to =.

class Solution {
public:
    int searchInsert(int A[], int n, int target) {
        int low=0, hi=n-1,mid=0;
       
        while(low<=hi)
        {
            mid=low+(hi-low)/2;
            if (target>A[mid])
            {
                low=mid+1;
            }
            else if(target<A[mid])
            {
                hi=mid-1;
            }
            else
            {
                return mid;
            }
        }       
        return low;
    }
};

Sort Colors (Dutch National Flag problem)

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.

 

Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

Algorithm:
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/
Three-way partition where 3 pointers are used, 1 for left, 1 for right.
Assume that the array has starting point at lo and ending point at hi.


Reference: This picture is from http://algs4.cs.princeton.edu/23quicksort/

It's based on a single left-to-right  pass through the array that maintains a pointer left such that a[lo...left-1] is less than v, a pointer right such that a[right+1,...hi] is greater than v, and a pointer i such that a[left, i-1] are equal to v,  and a[i...right] are not yet examined.

class Solution {
public:
    void sortColors(int A[], int n) {
        int left = 0, right = n-1, i=left, v = 1;
       
        while(i<=right)  //See above picture, needs to make sure i<=right
        {
            if (A[i]>v)
            {
                swap(A[i],A[right]);
                right--;
            }
            else if (A[i]<v)
            {
                swap(A[i],A[left]);
                i++;
                left++;
            }
            else
               i++;           
        }       
    }
};
 

First Missing Positive

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.

The challenging part of this problem is to 'uses constant space'. We need to find out how to manipulate the array itself to achieve this goal.

For A[n] to contain {1,2,3,4,......},  A[I]=I+1 or I = A[I]-1; If this condition doesn't hold, swap A[I] with A[A[I]-1] till we can't swap them anymore.

More specifically,
For n numbers, the answer must be in [1, n + 1].
1. If n numbers are 1, 2, 3, ..., n, then the answer is n + 1.
2. use a number x (x <= 0 || x > n) to replace a number in 1, 2, 3, ..., n. There must be a number less than n+1.

This is the key to write the following code.

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        for (int i=0; i<n; i++)
        {
            while (A[i]>0 && A[i]<=n && A[i]!=A[A[i]-1])
            {
                swap(A[i], A[A[i]-1]);
            }
        }
        for (int i=0; i<n; i++)
        {
            if (A[i]!=i+1)
               return i+1;
        }
        return n+1;
    }
};

MergeSort

For arrays:

1. Top-down:

Any better way to write this code?

 vector<int> aux;
 void merge(vector<int>& a, int lo, int mid, int hi)
 {
       int i = lo, j = mid + 1;
       for (int k = lo; k <= hi; k++)
      {
           aux[k] = a[k];
       }
       for (int k = lo; k <= hi; k++)
       {
             if (i > mid)
              a[k] = aux[j++];
             else if (j > hi)
              a[k] = aux[i++];
             else if (aux[i] > aux[j])
              a[k] = aux[j++];
             else
              a[k] = aux[i++];
       }
 }

 void sort(vector<int> &a, int lo, int hi)
 {
       if (hi <= lo) return;
       int mid = lo + (hi - lo) / 2;
       sort(a, lo, mid);
       sort(a, mid + 1, hi);
       merge(a, lo, mid, hi);
 }

 void mergeSort(vector<int> &a)
 {
       int len = a.size();
       aux = a;
       sort(a, 0, len - 1);
 }

2. Bottom up

void mergesortBU(vector<int> &a, int l, int r)
{ 
        for (int m=l; m<=r-l; m=m+m)
           for (int i=l; i<=r-m; i+=2*m)
                merge(a, i, i+m-1; min(i+2*m-1,r));
}

For singly linked list:
1. Top down:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
        ListNode *a=head, *b = head->next;
       
        while(b!=NULL&&b->next!=NULL)
        {
            a=a->next;
            b = b->next->next;
        }
        b=a->next;
        a->next=NULL;
        return merge(sortList(head), sortList(b));
    }
   
    ListNode *merge(ListNode *a, ListNode *b)
    {
        if (a==NULL) return b;
        if (b==NULL) return a;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
       
        while(a!=NULL&&b!=NULL)
        {
            if ( a->val<b->val)
            {
                cur->next = a;
                cur = a;
                a=a->next;
            }
            else
            {
                cur->next = b;
                cur = b;
                b=b->next;
            }
        }
        cur->next = a!=NULL?a:b;
        return dummy.next;
    }
};

2. Bottom up: (Sort a linked list in O(n log n) time using constant space ) Is this constant space?
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
       
        queue<ListNode *>  Q;
        for (ListNode *a=NULL; head!=NULL; head=a)
        {
            a = head->next;
            head->next = NULL;
            Q.push(head);
        }
       
        ListNode *t = Q.front();
        Q.pop();
       
        while(!Q.empty())
        {
            Q.push(t);
            t = Q.front();
            Q.pop();
            ListNode *p = Q.front();
            Q.pop();
            t = merge(t,p);
        }
       
        return t;
    }
   
    ListNode *merge(ListNode *a, ListNode *b)
    {
        if (a==NULL) return b;
        if (b==NULL) return a;
        ListNode dummy(-1);
        ListNode *cur = &dummy;
       
        while(a!=NULL&&b!=NULL)
        {
            if ( a->val<b->val)
            {
                cur->next = a;
                cur = a;
                a=a->next;
            }
            else
            {
                cur->next = b;
                cur = b;
                b=b->next;
            }
        }
        cur->next = a!=NULL?a:b;
        return dummy.next;
    }
};

Insertion Sort

Background:

https://en.wikipedia.org/wiki/Sorting_algorithm

Insertion sort and selection sort are quite similar.
http://en.wikipedia.org/wiki/Insertion_sort

http://en.wikipedia.org/wiki/Selection_sort

'Among simple average-case Θ(n²) algorithms, selection sort almost always outperforms bubble sort and gnome sort. Insertion sort is very similar in that after the kth iteration, the first k elements in the array are in sorted order. Insertion sort's advantage is that it only scans as many elements as it needs in order to place the k + 1st element, while selection sort must scan all remaining elements to find the k + 1st element.'

As its name suggests, it's a sort to be used while elements are being inserted into the array (or vector or whatever it is you're using), or sometimes when the array is "almost sorted". For an unsorted array, it's better to use quick sort or merge sort if it needs to be stable. Note, however, that insertion sort is actually faster when sorting while inserting.

http://mathbits.com/MathBits/CompSci/Arrays/Insertion.htm

http://www.programiz.com/article/insertion-sort-algorithm-programming

http://see.stanford.edu/materials/icspacs106b/Lecture15.pdf

Intuitively, inserting into a list is easier than inserting into an array as one has to move the elements in an array that are bigger than cur to the right. In terms of implementation, insertion sort an array compares from cur back as j-- till head of the array, while insertion sort a list compares from the head of the list and proceed down the list till end of the list.

1. Sort an array using insertion sort.
  void InsertionSort(vector<int> &v)
 {
       int j, len = v.size();
       for (int i = 1; i <len; i++)
       {
              int cur = v[i];
             // Slide cur down into position to left,
            // and move all the elements bigger than cur to be one more position to the right
              for (j = i - 1; j >= 0 && v[j]>cur; j--)
             {
                   v[j + 1] = v[j];
              }
              v[j+1] = cur;
        }
 }


2. Sort a linked list using insertion sort.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (head==NULL||head->next==NULL) return head;
        ListNode *ret=NULL;
       
        ListNode *cur;
       
        while(head!=NULL)
        {
            cur = head;
            head = head->next;

           // insert into the head of the sorted list
            // or as the first element into an empty sorted list
            if (ret==NULL||cur->val< ret->val)
            {               
                cur->next = ret;
                ret = cur;
            }
            else
            {
                // insert current element into proper position in non-empty sorted list
                ListNode *p = ret;
                while(p!=NULL)
               {
                  if (p->next==NULL||cur->val<p->next->val)
                  {
                     // insert into middle of the sorted list or as the last element
                    cur->next = p->next;
                    p->next = cur;
                    break;
                  }
                p=p->next;
               }
            }
        }       
        return ret;       
    }
};