data structure: Binary tree

Binary tree: at least two children of each node in the tree
binary search tree: for each node in the tree, the value of that node is smaller than all nodes in its right subtree and the value of that node is larger than all nodes in its left subtree.
complete binary tree: in every level of the tree, except possibly the last level, all nodes are completely filled, and the nodes are as far left as possible.
balanced binary tree: for each node in the tree, the height of its left subtree and the height of its right subtree differ by 1 or less.
Tree Tranversal:
pre-order, in-order, post-order.
These three traversal method both can be implemented by recursion. In some problems, we need to traverse the whole binary tree to get the result.

Q1 -> Q5 are basic recursion method used in the binary tree problems.
The basic idea is kind of like the pre-order traversal, check if the root node satisfy the requirement then check recursively check the left subtree and right subtree.
The rest questions of binary tree problem is the extension of the basic recursion method.
Q1: insert into binary search tree
Insert a key in a binary search tree if the binary search tree does not already contain the key. Return the root of the binary search tree.
analysis:
For most tree related problems, recursion is the simplest way to solve. Since each node in a tree has the same property, we can recursively search the root->left and root->right to get the answer. The problem apply to the whole tree can be apply to the left subtree and right subtree.
To insert a value into binary search tree, if the root is NULL, return the new node, else find the right position to insert the value, the right position to insert the value is left or right child of a leaf node. If the value of the root is < value, insert the value into the right subtree, if the value of the root is > value, insert the value into the left subtree, if the two value equals, no need to insert, return.
class Solution {
 private:
  void helper(TreeNode* &root, int value) {
//base case
    TreeNode* nnode = new TreeNode(value);
    if (root == NULL) {
      root = nnode;
    }
    //if value is larger than the value of root, insert the value into right subtree
    if (root->value < value)  helper(root->right, value);
    if (root->value > value)  helper(root->left, value);
    if (root->value == value) return;
    return;
  }
 public:
  TreeNode* insert(TreeNode* root, int value) {
    // Write your solution here.
    //step1: find the position first
    //step2: insert
    helper(root, value);
    return root;
  }
};
time complexity: O(logn)
space complexity: O(1)
Q2: search in binary search tree
find the target value in binary search tree, if the value is not in the tree, return NULL, else return the root.
class Solution {
 public:
  TreeNode* solve(TreeNode* root, int value) {
    //base case
    if (root == NULL) return NULL;
    if (root->value == value) return root;
    //recusive rule->subproblem
    if (root->value < value) return solve(root->right, value);
    if (root->value > value) return solve(root->left, value);
    return root;
  }
};
Time complexity: O(n) n is the total number of nodes in the binary tree
The recursion code is a pre-order traversal, the time complexity is equal to the time-complexity of pre-order traversal.
Space complexity: O(1)

Q3: Tweaked Identical Binary Trees
Determine whether two given binary trees are identical assuming any number of ‘tweak’s are allowed. A tweak is defined as a swap of the children of one node in the tree.

class Solution {
 public:
  bool isTweakedIdentical(TreeNode* r1, TreeNode* r2) {
    //base case
    if (r1 == NULL && r2 == NULL) return true;
    else if (r1 != NULL && r2 != NULL) {
      if (r1->value == r2->value) return (isTweakedIdentical(r1->left, r2-> right) && isTweakedIdentical(r1->right, r2->left)) || (isTweakedIdentical(r1->left, r2-> left) && isTweakedIdentical(r1->right, r2->right));
      else return false;
    }
    else return false;
    return 0;
  }
};
time complexity: O(n^2)
space complecity: O(1)

Q4: Is Binary Search Tree Or Not
Determine if a given binary tree is binary search tree.

analysis: the property of binary search tree is that each node in the tree, the value of that node is < value of all nodes in the right subtree and > value of all nodes in the left subtree. For each root node, maintain a lower bound and a upper bound. For nodes in left subtree, the upper bound is root value, the lower bound is the lower bound of root node; For nodes in right subtree, the lower bound is root value, the upper bound is the upper bound of root node.
class Solution {
 private:
  bool helper(TreeNode* root, int lower, int upper) {
    //base case
    if (root == NULL) return true;
    if (root->value < upper && root->value > lower) {
      return helper(root->left, lower, root->value) && helper(root->right, root->value, upper);
    }else return false;
  }
 public:
  bool isBST(TreeNode* root) {
    bool rst;
    return helper(root, INT_MIN, INT_MAX);
  }
};
TIME COMPLEXITY: O(n)
SPACE COMPLEXITY: O(1)
Q5: Get Keys In Binary Search Tree In Given Range
Get the list of keys in a given binary search tree in a given range[min, max] in ascending order, both min and max are inclusive.
analysis:
search all nodes with value < max and search all nodes with value > min, if the value of the node is >=min and <= max, push back into result. One thing to notice is that the result should be in ascending order, for binary search tree, the only traversal method to make the result in ascending order is in-order traversal. Therefore, the recursion should follow in-order traversal recursion method.
class Solution {
 private:
  void helper(vector<int> &rst, TreeNode* root, int min, int max) {
    //base case
    if (root == NULL) return;
    if (root->value > min) {
      helper(rst, root->left, min, max);
    }
    //in order to keep the result in ascending order, for binary search tree, we have to use inorder traversal
    if (root->value <= max && root->value >= min) rst.push_back(root->value);
    if (root->value < max) {
      helper(rst, root->right, min, max);
    }
   
  }
 public:
  vector<int> getRange(TreeNode* root, int min, int max) {
    //sanity check
    vector<int> rst;
    if (root == NULL) return rst;
    helper(rst, root, min, max);
    return rst;
  }
};
time complexity: O(n)
space complexity: O(1)

Data Structure: Linklist

class ListNode {
  public:
      int value;
      ListNode* next;
      ListNode (int v) {
           value(v);
           next(NULL);
      }
}
Q1: reverse linklist
Reverse a singly-linked list.
analysis: operations on linklist is operations on pointers. On most questions, we have to preserve a next and pre pointers of the linklist. To reverse a linklist, we can use both iterative way and recursive way to solve.
M1: iterative way
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* cur = head;
        ListNode* pre = NULL;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};M2: recursive way
class Solution {
 public:
  ListNode* reverse(ListNode* head) {
    //base case
    if (head == NULL || head->next == NULL) return head;
    ListNode* cur = head;
    ListNode* next = cur->next;
    ListNode* NodeN = reverse(next);
    next->next = cur;
    cur->next = NULL;
    return NodeN;
  }
};
time compelxity: O(n)
space complexity: O(1)

Q2: Reverse Linked List In Pairs
Reverse pairs of elements in a singly-linked list.
analysis:
for any reverse problems of linklist, recursion is the most easiest way to solve. recursion need know the base case and recursive rule. for recursive rule, try to solve one simplest case of the begining part of the linklist and treat the rest part of linklist as subproblem, use recursive function to solve the subproblem.
class Solution {
 public:
  ListNode* reverseInPairs(ListNode* head) {
    // write your solution here
    //base case
    if (head == NULL || head->next == NULL) {
      return head;
    }
    ListNode* cur = head;
    ListNode* next = cur->next;
    ListNode* NodeN = reverseInPairs(next->next);//this is the subproblem
    next->next = cur;
    cur->next = NodeN;
    return next;
  }
};
time complexity: O(n)
space complexity: O(1)
Q3:middle node of linklist
Find the middle node of a given linked list.
analysis:
In linklist, a simple way to find the middle node is use fast and slow pointers. Initially, these two pointers are at the first node and fast pointer move two steps each iteration and slow pointer move one step each iteration. When the fast pointer reaches the end of the linklist, the middle node is the node which slow pointer point to. Notice the corner case when the fast pointer move two steps.

class Solution {
 public:
  ListNode* middleNode(ListNode* head) {
    // write your solution here
    //sanity check
    if (head == NULL) return NULL;
    ListNode* slow = head;
    ListNode* fast = head;
    //for the number of listnodes in linklist is odd and even
    while (fast->next && fast->next->next) { // fast can't be null
      fast = fast->next->next;
      slow = slow->next;
    }
    return slow;
  }
};
time complexity: O(n)
space complexity: O(1)
Other related questions using slow and fast pointer is check if the linklist has circle
Q4:Insert to a sorted linklist
Insert a value in a sorted linked list.
analysis:
insert a value in a sorted linked list. the position of the value could be in the head of the list, the tail of the list or somewhere in the linklist. Since the head of the list may be changed, we can use a dummy node to simplify the corner cases. To find the inserted position, we need to find the node with the value larger than the inserted value. case 1: insert to the head, dummy node is the pre node; case2: insert to the tail, outside the while loop,insert after pre node; case 3: insert into the list, insert between the pre and cur node 
class Solution {
 public:
  ListNode* insert(ListNode* head, int value) {
    // write your solution here
    //the head of the link list may be changed due to the inserted value, apply dummy node
    //sanity check
    ListNode* nnode = new ListNode(value);
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* pre = dummy;
    ListNode* cur = head;
    while (cur != NULL) {
      if (cur->value < value) {
        pre = cur;
        cur = cur->next;
      }else {
        break; //find the position
      }
    }
    //insert the node
    pre->next = nnode;
    nnode->next = cur;
    return dummy->next;
  }
};
time complexity: O(n)
space complexity: O(1)

Q5:Merge Two Sorted Linked Lists
Merge two sorted lists into one large sorted list.
analysis: Since the head of the new Linklist may be changed, use dummy node to simplify the corner cases. Maintain two node pointers, one is dummy node, the other is tail of the new linklist
class Solution {
 public:
  ListNode* merge(ListNode* one, ListNode* two) {
    // write your solution here
    //the head may be changed, use dummy node
    //sanity check
    if (one == NULL) return two;
    if (two == NULL) return one;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    while (one && two) {
      if (one->value < two->value) {
        cur->next = one;
        cur = one;
        one = one->next;
      } else {
        cur->next = two;
        cur = two;
        two = two->next;
      }
    }
    if (one) {
      cur->next = one;
    }else {
      cur->next = two;
    }
    return head->next;
  }
};
time complexity: O(n)
space complexity: O(1)

Q6: Partition Linked list
Given a linked list and a target value T, partition it such that all nodes less than T are listed before the nodes larger than or equal to target value T. The original relative order of the nodes in each of the two partitions should be preserved.
analysis:
the method is the same as merge two sorted linklist.If we need to extract some part of the linklist from the whole linklist, we can use dummy node as the new linklist's head to get the sub linklist. One thing is important to notice, after extract the sub linklist, don't forget to unlink the tail of the sub linklist(tail->next = NULL), otherwise, the new linklist may be unlimited long!!!That's terrible. I always make a mistake due to forgetting to unlink the sub linklist from the original linklist.
class Solution {
 public:
  ListNode* partition(ListNode* head, int target) {
    // write your solution here
    //sanity check
    if (head == NULL || head->next == NULL) return head;
    //find two linklist, smaller and  larger
    ListNode* smaller = new ListNode(0);
    ListNode* larger = new ListNode(0);
    ListNode* stail = smaller;
    ListNode* ltail = larger;
    ListNode* p = head;
    while (p) {
      if (p->value < target) {
        stail->next = p;
        stail = p;
        p = p->next;
      } else {
        ltail->next = p;
        ltail = p;
        p = p->next;
      }
    }
    stail->next = larger->next;
    //unlink the last node of larger linklist
    ltail->next = NULL;
      return smaller->next;
  }
};
time complexity: O(n)
space complexity: O(1)
Q7: Reorder linked list
Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 -> … -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3 -> Nn-2 -> … -> null
analysis:
Some questions about linked list is the composition of other simple problem. The input and output of this problem can be formed by 3 previous problems. Step1: find the middle node of the linklist Step2: reverse the second half of the linklist Step3: twist merge the first half of the linklist and the second half of the linklist. From this problem, we know that by observing the input and output of the problem,  try to find solve the problem by composition of simple problems.
class Solution {
 private:
  ListNode* reverse(ListNode* head) {
    //base case
    if (head == NULL || head->next == NULL) return head;
    ListNode* cur = head;
    ListNode* next = cur->next;
    ListNode* nodeN = reverse(next);
    next->next = cur;
    cur->next = NULL;
    return nodeN;
  }
 public:
  ListNode* reorder(ListNode* head) {
    // write your solution here
    //sanity check
    if (head == NULL || head->next == NULL) return head;
    //find the middle node of the linklist
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->next && fast->next->next) {
      fast = fast->next->next;
      slow = slow->next;
    }
    //slow is the middle node
    ListNode* half = slow->next;
    slow->next = NULL;
    ListNode* second = reverse(half);
    //twist merge second and head
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while(head && second){
      cur->next = head;
      cur = head;
      head = head->next;
      cur->next = second;
      cur = second;
      second = second->next;
    }
    if (head) cur->next  = head;
    else if (second) cur->next = second;
    return dummy->next;
  }
};
time complexity: O(n)
space complexity: O(1)

Binary search

Q1: classic binary search

Given a target integer T and an integer array A sorted in ascending order, find the index i such that A[i] == T or return -1 if there is no such index.

analysis:
binary search is a search algorithm to find a target in a sorted array. find the middle element and compare with the target, if they are equal,find the target in the array, otherwise search the target in left half of the array or right half of the array. Every search kick off half of the elements in the array.
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right-left)/2;
      if (input[mid] < target) {
        left = mid+1;
      }else if (input[mid] > target) {
        right = mid-1;
      }else {
        return mid;
      }
    }
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)

Q2: first occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the first occurrence of T in A or return -1 if there is no such index.
analysis:
sorted search problem use binary search to solve. In this problem, if we use the classical binary search algorithm to solve, we will find the middle one of these duplicate elements. So we need to continue searching until find the leftmost one. when the array[mid] is larger or equal to target, we can search left half of the array. when the left and right pointers are neighbors, these two elements are the closest elements to target, but we don't know which one is the answer. we check left first and then right to see if the element is target.]
class Solution {
 public:
  int firstOccur(vector<int> input, int target) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] < target) {
        left = mid+1;
      }else if (input[mid] >= target) {
        right = mid;
      }
    }
    //post processing
    if (input[left] == target) return left;
    if (input[right] == target) return right;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1) 

Q3: Last Occurrence
Given a target integer T and an integer array A sorted in ascending order, find the index of the last occurrence of T in A or return -1 if there is no such index.  
analysis:
the same algorithm as the previous problem. the only difference is that when array[mid] is equal to the target, we have to continue searching the right half of the array.

 class Solution {
 public:
  int lastOccur(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] > target) {
        right = mid-1;
      }else {
        left = mid;
      }
    }
    //post processing
    if (input[right] == target) return right;
    if (input[left] == target) return left;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1) 

Q4: closest elements in sorted array
Given a target integer T and an integer array A sorted in ascending order, find the index i in A such that A[i] is closest to T. the target may be not in the array.
analysis:
search in sorted array but the target may not in the array. use binary search to find the two most closest elements in the array.In post processing, return the smallest difference of the two elements.
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] < target) left = mid;
      else if (input[mid] > target) right = mid;
      else return mid;
    }
    if (abs(target - input[left]) > abs(target - input[right])) return right;
    else return left;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)
Q5: K closest in sorted array 

Given a target integer T, a non-negative integer K and an integer array A sorted in ascending order, find the K closest numbers to T in A.
analysis:
if we can use binary search algorithm to find the most closest elements, which is the previous problem, then we can treat that element as a pivot and scan elements in two sides to find the k closest numbers.If Some corner cases have to be consider, if the left pointer reaches 0, then we have to push the right elements to result. The same when the right pointer reaches to the end.
class Solution {
 public:
  vector<int> kClosest(vector<int> array, int target, int k) {
    vector<int> rst;
    //sanity check
    if (array.size() == 0 || k == 0) return rst;
    //find the most closest element
    int left  = 0;
    int right = array.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (array[mid] < target) {
        left = mid;
      }else if (array[mid] > target) {
        right = mid;
      }else break;
    }
    int pivot = 0;
    if (array[mid] == target) pivot = mid;
    else if (abs(array[left] - target) > abs(array[right] - target)) pivot = right;
    else if (abs(array[left] -target) <= abs(array[right] - target)) pivot = left;
    rst.push_back(array[pivot]);
    left = pivot-1;
    right = pivot+1;
    for (int i = 0; i < k-1; i++) {
      while (left >= 0 && right <= array.size()-1) {
        if (abs(array[left] - target) > abs(array[right] - target)) {
          rst.push_back(array[right]);
          right++;
        } else {
          rst.push_back(array[left]);
          left--;
        }
       i++;
       if (i == k-1) return rst;
      }
      if (left >= 0) {
        rst.push_back(array[left--]);
      }
      if (right <= array.size()-1) {
        rst.push_back(array[right++]);
      }
    }
    return rst;
  }
};
time complexity: O(logn) + O(k) = O(logn)
space complexity: O(1)

Q6: total occurance
Given a target integer T and an integer array A sorted in ascending order, Find the total number of occurrences of T in A.  
analysis:
search in sorted array use binary search algorithm. we can find the first occurrence of the target in the array then find the last occurrence of the target in the array and return the difference + 1;
class Solution {
 public:
  int totalOccurrence(vector<int> input, int target) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return 0;
    //find the first occurance of the target
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] >=target) {
        right = mid;
      }else left = mid+1;
    }
    int pivot = 0;
    if (input[left] == target) pivot = left;
    else if (input[right] == target) pivot = right;
    else return 0;
    //find the last occurrence of the target
    left = 0;
    right  = input.size()-1;
    while (left < right-1) {
      mid = left + (right-left)/2;
      if (input[mid] <= target) left = mid;
      else right = mid-1;
    }
    if (input[right] == target) return right - pivot+1;
    if (input[left] == target) return left - pivot +1;
    return 0;
  };
time complexity: O(logn) + O(logn) = O(logn)
space complexity: O(1)

Q7:shift position
Given an integer array A, A is sorted in ascending order first then shifted by an arbitrary number of positions, For Example, A = {3, 4, 5, 1, 2} (shifted left by 2 positions). Find the index of the smallest number.There are no duplicate elements in the array.
analysis:
For shifted sorted array(without duplicate elements in the array), the important property is the whole array can be treated as two parts in ascending order. Think this scenario in two extremely cases: only one element shifted and only one element isn't shifted. These two cases can be detected by comparing the middle element and the rightmost element. if mid < right, it means elements from mid to right are in ascending order, which is case one.Then we can continue searching the smallest element in the left part of the middle element. if mid > right, it means elements from left to mid are in ascending order, which is case two. Then we can continue searching the smallest element in the right part of the middle element.
 class Solution {
 public:
  int shiftPosition(vector<int> input) {
    // Write your solution here
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left < right-1) {
      mid = left + (right - left)/2;
      if (input[mid] < input[right]) { //mid-right is in ascending order
        right = mid;
      }else if (input[mid] > input[right]) { //left-mid is in ascending order
        left = mid+1;
      }
    }
    if (input[left] < input[right]) return left;
    else return right;
    return -1;
  }
};
time complexity: O(logn)
space complexity: O(1)

Q8:search in shifted array(without duplicates)
Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.
analysis:
This is an extension of the previous problem. For each case, case 1: mid -> right is in ascending order, the target can only be in two parts, one is between mid and right, the other is smaller than mid; case 2: left->mid is in ascending order, the target can only be in two parts, one is between left and mid and the other is larger than mid. One corner case is that if the mid , left  and right are in the same position, then each case is allowed.
class Solution {
 public:
  int search(vector<int> input, int target) {
    // Write your solution here
    //sanitary check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right - left) / 2;
      if (input[mid] == target) return mid;
      if (input[mid] <= input[right]) { //mid-right ascending order
        if (input[mid] < target && input[right] >= target) {
          left = mid + 1;
        }else right = mid - 1;
      }else{
        if (input[mid] > target && input[left] <= target) {
          right = mid - 1;
        }else left = mid + 1;
      }
    }
    return -1;
  }
};
time complexity: O(log(n))
space complexity: O(1)
Q9: Search In Shifted Sorted Array II
Given a target integer T and an integer array A, A is sorted in ascending order first, then shifted by an arbitrary number of positions.
analysis:
extension from previous problem, duplicates are allowed. If duplicates exists, three cases should be considered,which is different from the previous one. case 1: mid->right is in ascending order; case 2: left->mid is in ascending order; case 3: input[mid] == input[right], for case 3, do right--, change the position of mid to make it not equal to input[right].
class Solution {
 public:
  int solve(vector<int> input, int target) {
    //sanity check
    if (input.size() == 0) return -1;
    int left = 0;
    int right = input.size()-1;
    int mid = 0;
    while (left <= right) {
      mid = left + (right-left)/2;
      if (input[mid] == target) return mid;
      if (input[mid] < input[right]) {
        if (input[mid] < target && input[right] >= target) {
          left = mid+1;
        }else {
          right  = mid-1;
        }
      } else if (input[mid] > input[right]) {
        if (input[mid] > target && input[left] <= target) {
          right = mid-1;
        }else {
          left = mid+1;
        }
      }else {
        right--;
      }
    }
    return -1;
  }
};
time complexity : O(n) 
in worst case, right-- cause the time complexity changing from O(logn) to O(n)
space complexity: O(1)

Sorting algorithm

Q1: Selection sort
Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.

Analysis:
selection sort algorithm sort an unordered array in this way: iterate the unordered array, in each iteration, find the smallest element and swap that element with leftmost element in this iteration

class Solution {
 public:
  vector<int> solve(vector<int> a) {
    //sanity check
    if (a.size() <= 1) return a;
    for (int i = 0; i < a.size()-1; i++) {
      //find the index of the smallest element
      int small = i;
      int j = 0;
      for (j = i+1; j < a.size(); j++) {
        if (a[j] <= a[small]){
          small = j;
        }
      }
      swap(a[i], a[small]);
    }
    return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)
 
Q1-1： selection sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The selectoin sort algorithm should be used to solve this problem.
analysis:
For linklist, the algorithm is as same as selection sort in array. Track the smallest pointer of the node and swap the value of that node with the leftmost node value. 
class Solution {
 public:
  ListNode* selectionSort(ListNode* a) { 
    // write your solution here
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    ListNode *smallest;
    ListNode *p = a;
    while (p->next != NULL) {
      smallest = p;
      ListNode *q = p->next;
      while (q) {
        if (q->value < smallest->value) {
          smallest = q;
        }
        q = q->next;
      }
      int tmp = smallest->value;
      smallest->value = p->value;
      p->value = tmp;
      p = p->next;
    }
    return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)
 

Q2: merge sort
Given an array of integers, sort the elements in the array in ascending order. The merge sort algorithm should be used to solve this problem.
analysis: 


class Solution {
 private:
  vector<int> combine(vector<int> left, vector<int> right) {
    vector<int> rst;
    int i = 0;
    int j = 0;
    while (i < left.size() && j < right.size()) {
      if (left[i] < right[j]) {
        rst.push_back(left[i]);
        i++;
      }else {
        rst.push_back(right[j]);
        j++;
      }
    }
    while (i < left.size()) {
      rst.push_back(left[i++]);
    }
    while (j < right.size()) {
      rst.push_back(right[j++]);
    }
    return rst;
  }
  vector<int> Merge(vector<int> array, int left, int right) {
    vector<int> solution;
    if (left > right) return solution;
    if (left == right) {
      solution.push_back(array[left]);
      return solution;
    }
    int mid = left + (right - left)/2;
    vector<int> left_solu = Merge(array, left, mid);
    vector<int> right_solu = Merge(array, mid+1, right);
    solution = combine(left_solu, right_solu);
    return solution;
  }
 public:
  vector<int> mergeSort(vector<int> array) {
    // Write your solution here
    //base case
    if (array.size() <= 1) return array;
    return Merge(array, 0, array.size()-1);
  }
};
Time complexity: O(nlogn)
split the array into half and half,  the height of  the recursion tree is logn, in each level of the tree, time complexity of merging two array is n, the total time complexity is O(nlogn).

space complexity: O(n)
for vector array, need space to store the temporary result, such as storing left half and right half of the array and when combining two sorted array, need extra space to store the result.

Q2-2: merge sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The merge sort algorithm should be used to solve this problem.

analysis:
the algorithm is the same as mergesort in array. To find the middle of the linklist, we use fast-slow pointers. The difference between array and linklist is that space complexity in linklist is O(1)

class Solution {
 private:
  ListNode* merge(ListNode* l1, ListNode* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    ListNode* head = new ListNode(0);
    ListNode* cur = head;
    while (p1 != NULL  && p2 != NULL) {
      if (p1->value < p2->value) {
        cur->next = p1;
        cur = p1;
        p1 = p1->next;
      } else {
        cur->next = p2;
        cur = p2;
        p2 = p2->next;
      }
    }
    if (p1 != NULL) {
      cur->next = p1;
    }
    if (p2 != NULL) {
      cur->next = p2;
    }
    return head->next;
  }
 public:
  ListNode* mergeSort(ListNode* a) {
    // write your solution here
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    //find middle node
    ListNode* slow = a;
    ListNode* fast = a;
    while (fast->next != NULL && fast->next->next != NULL) {
      fast = fast->next->next;
      slow = slow->next;
    }
    ListNode* mid = slow;
    ListNode* right = mid->next;
    mid->next = NULL;
    ListNode* left = a;
    ListNode* left_solu = mergeSort(left);
    ListNode* right_solu = mergeSort(right);
    return merge(left_solu, right_solu);
  }
};
time complexity: O(nlogn)
space complexity: O(1)

Q3:quick sort
Given an array of integers, sort the elements in the array in ascending order. The quick sort algorithm should be used to solve this problem
analysis:
quick sort try to find the right position for each element. When the first element find its position, that position is called pivot. Recursively, we can do this algorithm for all the elements in leftside and rightside of the pivot. How to find the right position for an element? Use two boarders to swap elements so that the elements are in the right position:
boarder i: left side of i is elements smaller than pivot element
boarder j: right side of j is elements larger than pivot element
position between i and j are to be discovered.

class Solution {
 private:
  void swap(vector<int> &array, int i, int j) {
    int tmp = array[i];
    array[i] = array[j];
    array[j] = tmp;
  }
  int pivot(vector<int> &array, int left, int right) {
    //swap left and right
    swap(array, left, right);
    int i = left;
    int j = right;
    while (i < j) {
      if (array[i] < array[right]) {
        i++;
      }else {
        j--;
        swap(array, i, j);
      }
    }
    swap(array, right, i);
    return i;
  }
  void quick(vector<int> &array, int left, int right) {
    //base case
    if (left >= right) return;
    int pivot1 = pivot(array, left, right);
    quick(array, left, pivot1-1);
    quick(array, pivot1+1, right);
  }
 public:
  vector<int> quickSort(vector<int> array) {
    //sanity check
    if (array.size() <= 1) {
      return array;
    }
   quick(array, 0, array.size()-1);
    return array;
  }
};
time complexity: O(n^2)
worst case is when the array is sorted, in each iteration, all elements have to be swapped. 

space complexity: O(1)

Q3-1: quick sort linklist
Given a singly-linked list, where each node contains an integer value, sort it in ascending order. The quick sort algorithm should be used to solve this problem.
analysis:
the algorithm is slightly different from quicksort for array because it's hard to use boarders to swap elements in linklist to find the right position for pivot element. But we can iterate the whole linklist to find all elements that are smaller than the pivot element and all elements that are larger than the pivot element.

class Solution {
 public:
  ListNode* quickSort(ListNode* a) {
    //sanity check
    if (a == NULL || a->next == NULL) return a;
    //find a pivot
    ListNode* pivot = a;
    //find the linklist smaller than a->value
    //find the linklist larger than a->value
    ListNode* small = new ListNode(0);
    ListNode* cur1 = small;
    ListNode* large = new ListNode(0);
    ListNode* cur2 = large;
    ListNode* p = a;
    while (p != NULL) {
      if (p->value < pivot->value) {
        cur1->next = p;
        cur1 = p;
      }else if (p->value > pivot->value) {
        cur2->next = p;
        cur2 = p;
      }
      p = p->next;
    }
    cur1->next = NULL;
    cur2->next = NULL;
    ListNode* s_solu = quickSort(small->next);
    ListNode* l_solu = quickSort(large->next);
    //merge two linklist
    if (s_solu == NULL) {
      pivot->next = l_solu;
      return pivot;
    }
    cur1 = s_solu;
    while (cur1->next) {
      cur1 = cur1->next;
    }
    cur1->next = pivot;
    pivot->next = l_solu;
    return s_solu;
  //  return a;
  }
};
time complexity: O(n^2)
space complexity: O(1)



Q4: Rainbow sort
Given an array of balls, where the color of the balls can only be Red, Green or Blue, sort the balls such that all the Red balls are grouped on the left side, all the Green balls are grouped in the middle and all the Blue balls are grouped on the right side. (Red is denoted by -1, Green is denoted by 0, and Blue is denoted by 1).

analysis:
This problem is similar to array shuffling, rearranging the array by swapping elements. 3 boarders can be used to solve this problem:
1. left side of boarder i is -1
2. right side of boarder j is 1
3. boarder k between i and j is 0
4. position between k and j is to be discovered
initial position: since the unknown position is the whole array, i=k=0 and j = array.size()-1. Treat k as the explored position, if a[k] == 1, swap k and j, j--, else if a[k] == -1, swap k, i, k++,i++, else k++

class Solution {
 public:
  vector<int> rainbowSort(vector<int> a) {
    //sanity check
    if (a.size() <= 1) return a;
    int i = 0;
    int k = 0;
    int j = a.size()-1;
    while (k <= j) {
      if (a[k] == 1) {
        swap(a[k], a[j]);
        j--;
      }else if (a[k] == -1) {
        swap(a[k], a[i]);
        i++;
        k++;
      }else {
        k++;
      }
    }
    return a;
  }
};
time complexity: O(n)
space complexity: O(1)