Next Permutation

/*

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

*/
class Solution {
public:
    void swap(vector<int> &num, int i, int j){
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
    }
    int partition(vector<int> &num, int i, int j){
        int smallIndex = i;;
        int pivot =  num[i];
       
        int k;
        for(k=i+1; k<=j; k++){
            if(num[k]<pivot){
                smallIndex++;
                swap(num, smallIndex, k);
            }
        }
       
        swap(num, i, smallIndex);
       
        return smallIndex;
    }
    void sort(vector<int> &num, int i, int j){
        int k;
        if(i<j){
            k = partition(num, i, j);
            sort(num, i, k-1);
            sort(num, k+1, j);
        }  
    }
    void nextPermutation(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size<=1) return;
       
        int i;
        int j;
        for(i=size-2; i>=0; i--){
            for(j=size-1; j>i; j--){
                if(num[i]<num[j]){
                    swap(num, i, j);
                    sort(num, i+1, size-1);
                    return;
                }
               
            }
        }
       
        int mid = size/2 - 1;
        for(i=0; i<=mid; i++){
            swap(num, i, size-1-i);
        }
    }
};

Combination Sum

/*

Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, � , a_k) must be in non-descending order. (ie, a₁ ? a₂ ? � ? a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

*/
class Solution {
public:
    vector<vector<int>> findSum(vector<int> candidates, int size, int target){
       vector<vector<int>> result;
       if(size==-1) return result;
       result = findSum(candidates, size-1, target);
       int elem = candidates[size];
       int num;
       vector<int> newComb;
       if(elem > target) return result;
      
       num = target/elem;
       if(target%elem == 0){
          newComb.insert(newComb.begin(), num, elem);
          result.push_back(newComb);
       }
       vector<vector<int>> inter;
      
       int j;
       int i;
       for(j=1; j<=num; j++){
       inter = findSum(candidates, size-1, target-j*elem);
       for(i=0; i<inter.size(); i++){
         inter[i].insert(inter[i].begin()+inter[i].size(), j, elem);
       }
       result.insert(result.begin()+result.size(), inter.begin(), inter.end());
       }
      
       return result;
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
        if(target<=0) return result;
        int size = candidates.size();
        int i;
        set<int> inter;
        for(i=0; i<size; i++){
         inter.insert(candidates[i]);
        }
        candidates.clear();
        set<int>::iterator it;
        for(it=inter.begin(); it!=inter.end(); it++){
         candidates.push_back(*it);
        }
        return  findSum(candidates, size-1, target);
    }
};

Remove Duplicates from Sorted Array

/*

Remove Duplicates from Sorted ArrayFeb 16 '12

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

*/
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n==0 || n==1) return n;
        int i;
        int const Impossible = -500;
        int curr;
       
        curr = A[0];
        for(i=1; i<n; i++){
            if(A[i]==curr){
                A[i] = Impossible;
            } else {
                curr = A[i];
            }
        }
        int pos = 1;
        while(A[pos]!=Impossible && pos<n){
            pos++;
        }
        if(pos==n) return n;
       
        curr = pos+1;
        while(curr<n){
            while(A[curr]==Impossible && curr<n){
              curr++;
            }
            if(curr!=n){
              A[pos] = A[curr];
              A[curr] = Impossible;
              while(A[pos]!=Impossible && pos<n){
                  pos++;
              }
            }
        }
       
        if(A[pos]==Impossible) return pos;
        else return pos+1;
    }
};

Merge k Sorted Lists

/*

Merge k Sorted ListsFeb 14 '12

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = lists.size();
        if(size==0) return NULL;
        if(size==1 && lists[0]!=NULL) return lists[0];
        if(size==1 && lists[0]==NULL) return NULL;
        int const MaxVal = 500;
       
        int i;
        ListNode *node = NULL;
        ListNode *curr = NULL;
        int currVal = MaxVal;
        int k = -1;
        for(i=0; i<size; i++){
            if(lists[i]!=NULL){
                if(lists[i]->val < currVal){
                    currVal = lists[i]->val;
                    curr = lists[i];
                    k = i;
                }
            }
        }
        if(k!=-1){
            node = lists[k];
            lists[k] = lists[k]->next;
        }
        if(node!=NULL) node->next = mergeKLists(lists);
       
        return node;
    }
};

Swap Nodes in Pairs

/*

Swap Nodes in PairsFeb 15 '12

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(head==NULL) return NULL;
        if(head->next == NULL) return head;
        ListNode *first = head;
        ListNode *second = head->next;
        int temp;
        while(first!=NULL && second!=NULL){
            temp = first->val;
            first->val = second->val;
            second->val = temp;
            first = second->next;
            if(first!=NULL) second = first->next;
        }
       
        return head;
    }
};

Convert Sorted List to Binary Search Tree

/*

Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
TreeNode *findMidNode(ListNode *head){
        if(head==NULL) return NULL;
    ListNode *prev = NULL;
        ListNode *curr = head;
        ListNode *tail = curr->next;
        if(tail!=NULL) tail = tail->next;
        while(tail!=NULL){
prev = curr;
            curr = curr->next;
            tail = tail->next;
            if(tail!=NULL) tail = tail->next;
        }
if(curr==NULL) return NULL;
TreeNode *node = new TreeNode(curr->val);
        if(prev!=NULL) prev->next = NULL;
        if(head!=curr) node->left = findMidNode(head);
        node->right = findMidNode(curr->next);
        return node;
    }
   
    TreeNode *sortedListToBST(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(head==NULL) return NULL;
        if(head->next==NULL){
           TreeNode* root = new TreeNode(head->val);
           return root;
        }
       
        return findMidNode(head);
    }
};

Longest Consecutive Sequence

/*

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.

*/
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        if(size==0) return 0;
        if(size==1) return 1;
        int const MaxNum = 50000;
        int const offset = MaxNum/2;
        vector<bool> existNum;
        existNum.insert(existNum.begin(), MaxNum, false);
        int i;
        for(i=0; i<size; i++){
          if((num[i]+offset) > MaxNum || (num[i]+offset) <0 ) return 0;
          existNum[num[i]+offset] = true;
        }
        int longest = 0;
        int currSum = 0;
        for(i=0; i<MaxNum; i++){
           if(i==0 && existNum[i]==true){
             currSum = 1;
           }
           if(i>0 && existNum[i-1]==true && existNum[i]==1){
            currSum++;
           }
           if(i>0 && existNum[i-1]==0 && existNum[i]==1){
            currSum = 1;
           }
           if(i>0 && existNum[i-1]==1 && existNum[i]==0){
            longest = max(longest, currSum);
            currSum = 0;
           }
          
           if(i==MaxNum-1){
            longest = max(longest, currSum);
           }
        }
       
        return longest;
    }
};

move Element

/*

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

*/
class Solution {
public:
    void swap(int A[], int i, int j){
      int temp = A[i];
      A[i] = A[j];
      A[j] = temp;
    }
    int removeElement(int A[], int n, int elem) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return 0;
       
        int i = 0;
       
        while(i<n && A[i]!=elem){
          i++;
        }
       
        if(i==n) return n;
       
        int j = n-1;
        while(j>=0 && A[j]==elem){
          j--;
        }
       
        if(j==-1) return 0;
       
        if(i>=j) return i;
               
        int pos = 0;              
        while(i<j){
          swap(A, i, j);
          pos = i;
          i++;
          j--;
          while(i<n && A[i]!=elem){
           i++;
          }
          while(j>=0 && A[j]==elem){
           j--;
          }
        }
       
        while(pos<n && A[pos]!=elem){
         pos++;
        }
        return pos;
    }
};

Rotate Image (to add alternative method)

/*

Rotate Image

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?

*/
class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = matrix.size();
        if(size==0) return;
        if(matrix[0].size()!=size) return;
        vector<vector<int>> result = matrix;
        for(int i=0; i<size; i++){
           for(int j=0; j<size; j++){
              result[i][j] = matrix[size-1-j][i];
           }
        }
        matrix = result;
        return;
    }
};

Pow(x, n)

/*

Pow(x, n)

Implement pow(x, n).

*/
class Solution {
public:
    double abs(double x){
      if(x<0) return (-1)*x;
      return x;
    }
    double pow(double x, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n==0) return 1;
        if(x==0) return 0;
        if(x==1) return 1;
        if(x==-1){
          if(n%2==0) return 1;
          else return -1;
        }
        bool neg = false;
        if(n<0) {
          neg = true;
          n = -n;
        }
        int i = 1;
        double result = x;
        while(i<n){
          result = x*result;
          i++;
          if(abs(result)<0.00000001 || abs(result) > 1000000) break;
        }
        if(neg) result = 1/result;
        return result;
    }
};

Jump Game

/*

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

*/
class Solution {
public:
    bool canJump(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n<=0) return true;

        int pos = 0;
        while(pos<n && A[pos]!=0){
           pos = pos + A[pos];
        }
        if(pos<n && A[pos]==0 && pos!=(n-1)) return false;
        return true;
    }
};

Merge Intervals

/*

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

*/
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
   void findIndex(vector<Interval> intervals, int & startPrevIndex, int num){
       int size = intervals.size();
       if(num<intervals[startPrevIndex].start) return;
       while(startPrevIndex<size){
         if(intervals[startPrevIndex].start <= num && (startPrevIndex == (size-1) || num < intervals[startPrevIndex+1].start)){
            return;
         }
         startPrevIndex++;
       } 
    }
      void findEndIndex(vector<Interval> intervals, int & endPrevIndex, int num){
       int size = intervals.size();
       if(num<intervals[endPrevIndex].end) return;
       while(endPrevIndex<size){
         if(intervals[endPrevIndex].end <= num && (endPrevIndex == (size-1) || num < intervals[endPrevIndex+1].end)){
            return;
         }
         endPrevIndex++;
       } 
    }
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(newInterval.start > newInterval.end) return intervals;
        int size = intervals.size();
        if(size==0){
          intervals.push_back(newInterval);
          return intervals;
        }
       
        int start = newInterval.start;
        int end = newInterval.end;
       
        if(end < intervals[0].start){
          intervals.insert(intervals.begin(), newInterval);
          return intervals;
        }
        if(end == intervals[0].start){
          intervals[0].start = newInterval.start;
          return intervals;
        }
        if(start > intervals[size-1].end){
          intervals.push_back(newInterval);
          return intervals;
        }
        if(start == intervals[size-1].end){
          intervals[size-1].end = newInterval.end;
    return intervals;
        }
       
        int startPrevIndex = 0;
        findIndex(intervals, startPrevIndex, start);
        int endPrevIndex = 0;
        findEndIndex(intervals, endPrevIndex, end);
       
        if(start<intervals[startPrevIndex].end && end<=intervals[startPrevIndex].end){
     if(startPrevIndex==0 && start<intervals[startPrevIndex].start){
      intervals[startPrevIndex].start = start;
     }
           return intervals;
        }
       
        int i;
       
        if(start<=intervals[startPrevIndex].end){
    
   if(startPrevIndex==0 && start<intervals[startPrevIndex].start){
      intervals[startPrevIndex].start = start;
     }
     i = startPrevIndex+1;
     if(endPrevIndex==size-1){
      while(i<=size-1){
     intervals.erase(intervals.begin()+startPrevIndex+1);
                 i++;
      }
      intervals[startPrevIndex].end = end;
      return intervals;
     }
           if(end<intervals[endPrevIndex+1].start){
             intervals[startPrevIndex].end = end;
             if(startPrevIndex==endPrevIndex) return intervals;
             while(i<=endPrevIndex){
               intervals.erase(intervals.begin()+startPrevIndex+1);
               i++;
             }
             return intervals;
           }
          
           if(end>=intervals[endPrevIndex+1].start){
             i = startPrevIndex+1;
             intervals[startPrevIndex].end = intervals[endPrevIndex+1].end;
             while(i<=(endPrevIndex+1)){
               intervals.erase(intervals.begin()+startPrevIndex+1);
               i++;
             }
             return intervals;
           }
        }
       
        if(start>intervals[startPrevIndex].end && end<intervals[startPrevIndex+1].start){
           intervals.insert(intervals.begin()+startPrevIndex+1, newInterval);
           return intervals;
        }
       
        if(start>intervals[startPrevIndex].end){
           intervals[startPrevIndex+1].start = start;
           i = startPrevIndex+2;
     if(endPrevIndex==size-1){
     while(i<=size-1){
      intervals.erase(intervals.begin()+startPrevIndex+2);
      i++;
     }
     intervals[startPrevIndex+1].end = end;
     return intervals;
     }
           if(end >= intervals[endPrevIndex+1].start){
             intervals[startPrevIndex+1].end = intervals[endPrevIndex+1].end;
             while(i<=(endPrevIndex+1)){
                intervals.erase(intervals.begin()+startPrevIndex+2);
                i++;
             }
             return intervals;
           }
          
           if(end < intervals[endPrevIndex+1].start){
             while(i<=(endPrevIndex)){
               intervals.erase(intervals.begin()+startPrevIndex+2);
               i++;
             }
             intervals[startPrevIndex+1].end = end;
             return intervals;
           }
        }     
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = intervals.size();
        if(size<=1) return intervals;
       
        vector<Interval> result;
        result.push_back(intervals[0]);
       
        int i;
        for(i=1; i<size; i++){
          result = insert(result, intervals[i]);
        }
       
        return result;
    }
};

Insert Interval

/*

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

*/
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
          void findIndex(vector<Interval> intervals, int & startPrevIndex, int num){
       int size = intervals.size();
       if(num<intervals[startPrevIndex].start) return;
       while(startPrevIndex<size){
         if(intervals[startPrevIndex].start <= num && (startPrevIndex == (size-1) || num < intervals[startPrevIndex+1].start)){
            return;
         }
         startPrevIndex++;
       } 
    }
      void findEndIndex(vector<Interval> intervals, int & endPrevIndex, int num){
       int size = intervals.size();
       if(num<intervals[endPrevIndex].end) return;
       while(endPrevIndex<size){
         if(intervals[endPrevIndex].end <= num && (endPrevIndex == (size-1) || num < intervals[endPrevIndex+1].end)){
            return;
         }
         endPrevIndex++;
       } 
    }
    vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(newInterval.start > newInterval.end) return intervals;
        int size = intervals.size();
        if(size==0){
          intervals.push_back(newInterval);
          return intervals;
        }
       
        int start = newInterval.start;
        int end = newInterval.end;
       
        if(end < intervals[0].start){
          intervals.insert(intervals.begin(), newInterval);
          return intervals;
        }
        if(end == intervals[0].start){
          intervals[0].start = newInterval.start;
          return intervals;
        }
        if(start > intervals[size-1].end){
          intervals.push_back(newInterval);
          return intervals;
        }
        if(start == intervals[size-1].end){
          intervals[size-1].end = newInterval.end;
    return intervals;
        }
       
        int startPrevIndex = 0;
        findIndex(intervals, startPrevIndex, start);
        int endPrevIndex = 0;
        findEndIndex(intervals, endPrevIndex, end);
       
        if(start<intervals[startPrevIndex].end && end<=intervals[startPrevIndex].end){
     if(startPrevIndex==0 && start<intervals[startPrevIndex].start){
      intervals[startPrevIndex].start = start;
     }
           return intervals;
        }
       
        int i;
       
        if(start<=intervals[startPrevIndex].end){
    
   if(startPrevIndex==0 && start<intervals[startPrevIndex].start){
      intervals[startPrevIndex].start = start;
     }
     i = startPrevIndex+1;
     if(endPrevIndex==size-1){
      while(i<=size-1){
     intervals.erase(intervals.begin()+startPrevIndex+1);
                 i++;
      }
      intervals[startPrevIndex].end = end;
      return intervals;
     }
           if(end<intervals[endPrevIndex+1].start){
             intervals[startPrevIndex].end = end;
             if(startPrevIndex==endPrevIndex) return intervals;
             while(i<=endPrevIndex){
               intervals.erase(intervals.begin()+startPrevIndex+1);
               i++;
             }
             return intervals;
           }
          
           if(end>=intervals[endPrevIndex+1].start){
             i = startPrevIndex+1;
             intervals[startPrevIndex].end = intervals[endPrevIndex+1].end;
             while(i<=(endPrevIndex+1)){
               intervals.erase(intervals.begin()+startPrevIndex+1);
               i++;
             }
             return intervals;
           }
        }
       
        if(start>intervals[startPrevIndex].end && end<intervals[startPrevIndex+1].start){
           intervals.insert(intervals.begin()+startPrevIndex+1, newInterval);
           return intervals;
        }
       
        if(start>intervals[startPrevIndex].end){
           intervals[startPrevIndex+1].start = start;
           i = startPrevIndex+2;
     if(endPrevIndex==size-1){
     while(i<=size-1){
      intervals.erase(intervals.begin()+startPrevIndex+2);
      i++;
     }
     intervals[startPrevIndex+1].end = end;
     return intervals;
     }
           if(end >= intervals[endPrevIndex+1].start){
             intervals[startPrevIndex+1].end = intervals[endPrevIndex+1].end;
             while(i<=(endPrevIndex+1)){
                intervals.erase(intervals.begin()+startPrevIndex+2);
                i++;
             }
             return intervals;
           }
          
           if(end < intervals[endPrevIndex+1].start){
             while(i<=(endPrevIndex)){
               intervals.erase(intervals.begin()+startPrevIndex+2);
               i++;
             }
             intervals[startPrevIndex+1].end = end;
             return intervals;
           }
        }     
    }
    };  

Spiral Matrix II

/*

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.
For example,
Given n = 3,
You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

*/
class Solution {
public:
    void fillOneRound(vector<vector<int>> & result, int const n, int & curr, int const step){
       if ((n-2*step)==0) return;
      
       if (n-2*step==1 && curr <= n*n) {
          result[step][step] = curr;
          curr++;
       }
      
       int i;
       for(i=step; i<=(n-step-2) && curr<=n*n; i++){
         result[step][i] = curr;
         curr++;
       }
       for(i=step; i<=(n-step-2) && curr<=n*n; i++){
         result[i][n-step-1] = curr;
         curr++;
       }
       for(i=(n-step-1); i>=(step+1) && curr<=n*n; i--){
         result[n-step-1][i] = curr;
         curr++;
       }
       for(i=(n-step-1); i>=(step+1) && curr<=n*n; i--){
         result[i][step] = curr;
         curr++;
       }
    }
   
    vector<vector<int> > generateMatrix(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
       
        if(n<=0) return result;
       
        vector<int> line(n, 0);
        result.insert(result.begin(), n, line);
       
        int round = n/2;
       
        int step;
       
        int currNum = 1;
       
        for(step=0; step<=round; step++){
           fillOneRound(result, n, currNum, step);
        }
       
        return result;
    }
};

Spiral Matrix

/*

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

*/
class Solution {
public:
    void printOutRound(vector<vector<int>> matrix, int m, int n, int step, vector<int> & result){
        int i;
       
        if((m-2*step)==0 || (n-2*step)==0) return;
       
        if((m-2*step)==1){
          for(i=step; i<=(n-step-1); i++){
            result.push_back(matrix[step][i]);
          }
          return;
        }
       
        if((n-2*step)==1){
          for(i=step; i<=(m-step-1); i++){
            result.push_back(matrix[i][step]);
          }
          return;
        }
       
        for(i=step; i<=(n-step-2); i++){
          result.push_back(matrix[step][i]);
        }
        for(i=step; i<=(m-step-2); i++){
          result.push_back(matrix[i][n-step-1]);
        }
        for(i=(n-step-1); i>=(step+1); i--){
          result.push_back(matrix[m-step-1][i]);
        }
        for(i=(m-step-1); i>=(step+1); i--){
          result.push_back(matrix[i][step]);
        }
    }
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        int m = matrix.size();
        if(m==0) return result;
        int n = matrix[0].size();
        if(n==0) return result;
       
        int limit = min(m, n);
        int round = limit/2;
       
        int i;
        for(i=0; i<=round; i++){
          printOutRound(matrix, m, n, i, result);
        }
       
        return result;
    }
};

Maximum Subarray

/*

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

More practice: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

*/
class Solution {
public:
    int maxSubArray(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int pos = 0;
        if(n<=0) return -1;
               
        int result = A[pos];
        while(A[pos]<=0 && pos<n){
          result = max(result, A[pos]);
          pos++;
        }
        if(pos==n) return result;
        result = A[pos];
        int end = pos;
       
        int currSum = result;
       
        pos++;  
        while(pos<n){
          if(A[pos]>=0){
            currSum = currSum + A[pos];
            result = max(result, currSum);
          }
          if(A[pos]<=0){
            if(currSum>=0){
              if ((currSum+A[pos])<0){
                currSum = 0;
              }
              else{
                currSum = currSum+A[pos];
              }
            }
          }
          pos++;
        }
       
        return result;
    }
};

Triangle

/*

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

*/
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rowSize = triangle.size();
 if(rowSize==0) return 0;
 int const bigValue = 200;
 int lineMin = bigValue;
 int j;
 for(int i=0; i<rowSize; i++){
  if(triangle[i].size()!=(i+1)) return 0;
  if(i>0){
   for(j=0; j<(i+1); j++){
    lineMin = bigValue;
    if(j<triangle[i-1].size())
    lineMin = min(triangle[i-1][j] + triangle[i][j], lineMin);
    if(j>=1){
     lineMin = min(triangle[i-1][j-1] + triangle[i][j], lineMin);
    }
    triangle[i][j] = lineMin;
   }
  }
 }
         lineMin = bigValue;
 for(j=0; j<triangle[rowSize-1].size(); j++){
  lineMin = min(lineMin, triangle[rowSize-1][j]);
 }
 return lineMin;
    }
};

Reverse Linked List II

/*

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.

*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
ListNode *reverseBetween(ListNode *head, int m, int n){
 if(m>n) return NULL;
 if(m==n) return head;
 if(m<1) return NULL;
 ListNode *prep = head;
 int i = 0;
 while(i<(m-1)){
  prep = prep->next;
  i++;
 }
 stack<int> s;
 ListNode *curr;
 curr = prep;
 s.push(curr->val);
 while(i<(n-1) && curr!=NULL){
  curr = curr->next;
  if(curr!=NULL) s.push(curr->val);
  i++;
 }
 while(!s.empty()){
  prep->val = s.top();
  prep = prep->next;
  s.pop();
 }
 return head;
}
    };

Word Search

/*

Word Search

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

*/
class Solution {
public:
    vector<vector<int>> findLetter(vector<vector<char> > board, char c){
     vector<vector<int>> tempResult;
     int i, j;
     int rowSize = board.size();
     if(rowSize==0) return tempResult;
  int colSize = board[0].size();
     if(colSize==0) return tempResult;
     vector<int> onePair;
     for(i=0; i<rowSize; i++){
       for(j=0; j<colSize; j++){
         if(board[i][j]==c){
           onePair.clear();
           onePair.push_back(i);
           onePair.push_back(j);
           tempResult.push_back(onePair);
         }
       }
     }
     return tempResult;
    }
   
        bool containPair(map<vector<int>,bool> used, int row, int col){
  vector<int> pair;
  pair.push_back(row);
  pair.push_back(col);
  if(used.find(pair) != used.end()) return true;
  return false;
 }
   
       void findNextLetter(vector<vector<char>> board, vector<int> temp, int rowIdx, int colIdx, char c, vector<vector<int>> &result){
       vector<int> newLine;
    map<vector<int>, bool> used;
    int i;
    for(i=0; i<temp.size()-1; i=i+2){
     newLine.clear();
     newLine.push_back(temp[i]);
     newLine.push_back(temp[i+1]);
     used[newLine] = true;
    }
       if(colIdx >= 1 && board[rowIdx][colIdx-1]==c && !containPair(used, rowIdx, colIdx-1)) {
                     newLine.clear();
                     newLine = temp;
     newLine.push_back(rowIdx);
     newLine.push_back(colIdx-1);
                     result.push_back(newLine);
    }
       if((colIdx+1)< board[rowIdx].size() && board[rowIdx][colIdx+1]==c && !containPair(used, rowIdx, colIdx+1)) {
                     newLine.clear();
                     newLine = temp;
     newLine.push_back(rowIdx);
     newLine.push_back(colIdx+1);
                     result.push_back(newLine);
    }
       if(rowIdx>=1 && board[rowIdx-1][colIdx]==c && !containPair(used, rowIdx-1, colIdx)) {
                     newLine.clear();
                     newLine = temp;
     newLine.push_back(rowIdx-1);
     newLine.push_back(colIdx);
                     result.push_back(newLine);
    }
       if((rowIdx+1)< board.size() && board[rowIdx+1][colIdx]==c && !containPair(used, rowIdx+1, colIdx)) {
                     newLine.clear();
                     newLine = temp;
     newLine.push_back(rowIdx+1);
     newLine.push_back(colIdx);
                     result.push_back(newLine);
    }
    }
   
    bool exist(vector<vector<char> > &board, string word) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(board.size()==0) return false;
        if(board[0].size()==0) return false;
        int stringSize = word.length();
        if(stringSize==0) return true;
        vector<vector<int>> temp = findLetter(board, word[0]);
        int i = 1;
        int resultSize = temp.size();
        vector<vector<int>>::iterator it;
        vector<int>::iterator lineIt;
        int j;
        int lineSize;
        int rowIdx;
        int colIdx;
  int k;
        while(i<stringSize && resultSize>0){
           for(k=0; k < resultSize && temp[k].size()>=2; k++){
             lineSize = temp[k].size();
             rowIdx = temp[k][lineSize-2];
             colIdx = temp[k][lineSize-1];
             findNextLetter(board, temp[k], rowIdx, colIdx, word[i], temp);
            }
           temp.erase(temp.begin(), temp.begin() + resultSize);
           i++;
           resultSize = temp.size();
        }
       
        for(j=0; j<temp.size(); j++){
          if(temp[j].size() == stringSize*2){
            return true;
          }
        }
       
        return false;
    }
};

Word Ladder (to optimize)

/*

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,
Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.

*/
class Solution {
public:
    bool oneStep(string src, string des){
      if(src.length() != des.length()) return false;
      int difference = 0;
      for(int i=0; i<src.length(); i++){
        if(src[i]!=des[i]){
          difference++;
          if(difference>1) return false;
        }
      }
      if (difference==0) return false;
      else return true;
    }
   
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> inter;
        inter.push_back(start);
        dict.erase(start);
        int size = inter.size();
        int result = 1;
        int i;
        unordered_set<string>::iterator it;
        while(!inter.empty()){
          for(i=0; i<size; i++){
             if(oneStep(inter[i], end)){
              result++;
              return result;
             }
             it = dict.begin();
             while(it!=dict.end()){
              if(oneStep(inter[i],*it)){
                inter.push_back(*it);
                it = dict.erase(it);
              }
              else{
              it++;
              }
             }        
          }
          result++;
          inter.erase(inter.begin(), inter.begin()+size);
          size = inter.size();
        }
        return 0;
    }
};

Palindrome Partitioning

/*

Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return

  [
    ["aa","b"],
    ["a","a","b"]
  ]

*/
class Solution {
public:
    bool isPalindrome(string s){
      int size = s.length();
      int i = 0;
      int j = size-1;
      while(i<j){
        if(s[i]!=s[j]) return false;
        i++;
        j--;
      }
      return true;
    }
   
    vector<vector<string>> findPartition(string s, int pos){
      vector<string> line;
      vector<vector<string>> result;
      if(pos==0){
        line.push_back(s.substr(0,1));
        result.push_back(line);
        return result;
      }
     
      int i;
      result = findPartition(s, pos-1);
      int currectResultSize = result.size();
      for(i=0; i<currectResultSize; i++){
        result[i].push_back(s.substr(pos,1));
      }
     
      i = 0;
      string newString = s.substr(i, pos-i);
      int found = newString.find(s[pos]);
      vector<vector<string>> temp;
      int j;
      while(found!=string::npos){
         if(isPalindrome(s.substr(found+i, pos-i-found+1))){
         if((found+i)==0){
           line.clear();
           line.push_back(s.substr(found+i, pos-i-found+1));
           result.push_back(line);
         }
         else{
            temp.clear();
            temp = findPartition(s, found+i-1);
            for(j=0; j<temp.size(); j++){
               temp[j].push_back(s.substr(found+i, pos-i-found+1));
               result.push_back(temp[j]);
            }
         }
         }
         i = found+i+1;
         if(i<s.length()){
         newString = s.substr(i, pos-i);
         found = newString.find(s[pos]);
         }
         else{
          found = string::npos;
         }
      }
     
      return result;
    }
    vector<vector<string>> partition(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = s.length();
        vector<vector<string>> result;
        if(size==0) return result;
        return findPartition(s, size-1);
    }
};