kth largest element in an unsorted array

sort the array and pick the kth

O(Nlog(N))

Use size k min heap

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int> ,greater<int>> pq;
        for(auto n : nums){
            pq.push(n);
            if (pq.size() > k)
                pq.pop();
        }
        return pq.top();
    }
};

We use a min heap of size k to filter through all elements and if after adding an element to heap causing the heap size to exceed k, then we pop it.

This algorithm will eventually contain the kth largest element since all elements smaller than kth largest elem will be at the internal or leaf. And any node larger than kth largest will eventually be at the top and get pop off.

Quick select

Bubble sort

Gonna start from the bottom and work my way up. Starting from Bubble sort!

Bubble sort, as the name implies, bubble up the largest element to the top of the array. For a size k array, it will iterate it k times, each times, bring the kth largest element to the top.

    vector<int> sortArray(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i ++){
            for(int j = 0; j < nums.size() - 1; j ++){
                if(nums[j] > nums[j + 1]){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }

We can optimize it 2 ways
1: we know that at kth iteration, 1st … kth largest element are already in their right place. So we can stop swapping loop at k – 1.

2: If no swapping happens in a loop, we know the array is already sorted.

LC102 Binary level traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
The result will be
[
[3],
[9,20],
[15,7]
]

    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        queue<int> level;
        q.push(root);
        level.push(1);
        int levelCount = 1;
        vector<vector<int>> result;
        vector<int> res;

        while(!q.empty()){
            int curLevel = level.front();
            level.pop();
            TreeNode* curNode = q.front();
            q.pop();
            if(curLevel != levelCount){
                levelCount = curLevel;
                result.push_back(res);
                res.clear();
            }
            if(curNode != NULL){
                res.push_back(curNode -> val);
                q.push(curNode -> left);
                q.push(curNode -> right);
                level.push(levelCount + 1);
                level.push(levelCount + 1);
            }
        }

        return result;
    }

LC 101 Symmetric tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note: Bonus points if you could solve it both recursively and iteratively.

Recursive

A tree is symmetric if the two subtrees beneath any root has:

  1. the left and right child has the same value
  2. The left child’s left matches with right child’s right
  3. The left child’s right matches with left child’s left.

The base case is when two leaf level node matches and they don’t have children.

    bool isSymmetric(TreeNode* root) {
        return isSym(root, root);
    }
    bool isSym(TreeNode* leftNode, TreeNode* rightNode){
        if(leftNode == NULL && rightNode != NULL) return false;
        if (leftNode != NULL && rightNode == NULL)return false;
        if(leftNode == NULL && rightNode == NULL) return true;
        return (leftNode -> val == rightNode -> val &&
            isSym(leftNode -> left, rightNode -> right) && 
            isSym(leftNode -> right , rightNode -> left));
    }

Improvement

In the previous code, we have three coditions to check, but observe that it only wants to know if both nodes are null or just one is null so we can do

if(leftNode == NULL && rightNode == NULL) return true;
if(left == NULL || right == NULL) return falase;

ITerative

    bool isSymmetric(TreeNode* root) {
        stack<TreeNode*> s;
        s.push(root);
        s.push(root);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode == NULL) continue;
            if(leftNode == NULL || rightNode == NULL) return false;
            if(leftNode -> val == rightNode -> val){
                s.push(leftNode -> left);
                s.push(rightNode -> right);
                s.push(leftNode -> right);
                s.push(rightNode -> left);
            }
            else
                return false;
        }
        return true;
    }

LC 100 Same tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Two tree are the same if

  1. Both root nodes are either both empty of both valid
  2. The left subtree of p is the same as the left sub tree of q
  3. The right subtree of p is the same as the right sub tree of q

So we can write a recursive code to check the above three conditions

    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) return true;
        if(p != NULL and q == NULL or(p == NULL and q != NULL))return false;
        return (p->val == q->val && isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right));
    }

ITerative

DFS

To use DFS, we want to first go as deep as possible, so we use a stack to enforce FILO policy so we will always go deep with the current node and only explore other branch when the current branch hit the bottom (null on both left and right children)

    bool isSameTree(TreeNode* p, TreeNode* q) {
        stack<TreeNode*> s;
        s.push(p);
        s.push(q);
        while(!s.empty()){
            TreeNode* leftNode = s.top();
            s.pop();
            TreeNode* rightNode = s.top();
            s.pop();
            if(leftNode == NULL && rightNode != NULL) return false;
            if(leftNode != NULL && rightNode == NULL) return false;
            if(leftNode != NULL && rightNode != NULL){
                if(leftNode -> val == rightNode -> val){
                    s.push(leftNode -> left);
                    s.push(rightNode -> left);
                    s.push(leftNode -> right);
                    s.push(rightNode -> right);
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }

LC95 Unique Binary Search Tree

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n < 1)
            return vector<TreeNode*>(0);
        return genRoots(1, n);
    }
    vector<TreeNode*> genRoots(int start, int end){
        vector<TreeNode*> res;
        if(start > end){
            return vector<TreeNode*>(1,NULL);
        }

        for(int i = start; i <= end; i ++){
            vector<TreeNode*>left = genRoots(start, i - 1);
            vector<TreeNode*>right = genRoots(i + 1, end);    
            //then put the connect the root with all possible left and right child
            for(int j = 0; j < left.size(); j ++){
                for(int k = 0; k < right.size(); k ++){
                    TreeNode *curRoot = new TreeNode(i);
                    curRoot -> left = left[j];
                    curRoot -> right = right[k];
                    res.push_back(curRoot);
                }
            }
        }
    return res;   
    }
};

LC 96 Unique binary search tree

We use dynamic programming. Given nodes[1,2,3….n], we could have n roots. If we calculate how many ways to arrange each root, we can just sum them up all ways.
Let’s call stores ways to arrange i nodes in uniqueShapes[i], and to calculate uniqueShapes[i], we just sum uniqueAtI[1],… till uniqueAtI[i].

To calculate uniqueAtI[j] when calculating uniqueShapes[i], j will be the root. There will be j – 1 nodes smaller than j and i – j nodes bigger than j. so j – 1 nodes will be on the left side of root j and i – j node will be on right side of root j.
There are uniqueShapes[j] ways to arrange j node and uniqueShapes[i – j] ways to arrange i – j, and arranging these two groups of nodes are not interfering with each other so we can use product rule:
While calculating uniqueShapes[i], we will iterate through 1…i as root and calculate uniqueAtI for each of them according to

uniqueAtI[j] = uniqueShapes[j - 1]* uniqueShapes[i - j]
class Solution {
public:
    int numTrees(int n) {
        vector<int> uniqueShapes(n + 1, 0);
        vector<int> uniqueShapesAtI(n + 1, 0);
        uniqueShapes[0] = 1;
        uniqueShapes[1] = 1;
        for(int i = 2; i <=n; i ++){
            int sum = 0;
            for(int j = 1; j <=i; j ++){
                uniqueShapesAtI[j] = uniqueShapes[j - 1] * uniqueShapes[i - j];
                sum += uniqueShapesAtI[j];
            }
            uniqueShapes[i] = sum;
        }
        return uniqueShapes[n];

    }

};

LC94 Inorder Traversal of binary tree

Given a binary tree, return the inorder traversal of its nodes’ values.
In order traversal means visit the left, then the root, then the right.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>res;
        recurTraverse(root, res);
        return res;
    }
    void recurTraverse(TreeNode* root, vector<int>& res){
        if(root == NULL) return;
        recurTraverse(root -> left, res);
        res.push_back(root -> val);
        recurTraverse(root -> right, res);
    }
};

Iterative solution

In this code, we will use a stack to keep track of parent nodes.
We will first put root and all its left child node push onto the stack. And once we finished pushing all left child, we will pop the stack, store its value to res. Then if the poped node has right child, in the next iteration, we will push it and all its left child onto the stack. This method will ensure left-middle-right order.

    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> parentStack;
        vector<int> res;
        TreeNode* currNode = root;
        while(!parentStack.empty() || currNode){
            if(currNode){
                parentStack.push(currNode);
                currNode = currNode -> left;
            }
            else{
                TreeNode* tempNode = parentStack.top();
                parentStack.pop();
                res.push_back(tempNode -> val);
                currNode = tempNode -> right;
            }
        }
        return res;
    }

LC 93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: “25525511135” Output: [“255.255.11.135”, “255.255.111.35”]

An IP address has 4 parts. Each part will have a valid number in [0,255] Since each group can have 1, 2 or 3 numbers, we have 3x3x3x3 ways to splice the number.

BF

Just all 81 ways to splice the number and output all possible combination.

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        //use 4 nested for loop to generate all possible way 
        //to slice
        vector<string> res;
        for(int i = 1; i <= 3; i ++){
            for(int j = 1; j <= 3; j ++){
                for(int k = 1; k <= 3; k ++){
                    for(int l = 1; l <= 3; l ++){
                        if(i + j + k + l != s.size())
                            continue;
                        int i1 = stoi(s.substr(0, i));
                        int i2 = stoi(s.substr(i, j));
                        int i3 = stoi(s.substr(i + j, k));
                        int i4 = stoi(s.substr(i + j + k, l));
                        //cout<<i1 << " " << i2 <<" "<< i3<<" " << i4<< '\n';
                        if(i1 <= 255 && i2 <= 255 && i3 <= 255 && i4 <=255){
                            string ans = to_string(i1) + "." + to_string(i2) + "." + to_string(i3) + "." + to_string(i4);
                            //cout<<"ans is "<< ans<<endl;
                            if(ans.size() == s.size() + 3){
                                res.push_back(ans);
                                //cout<<ans<<endl;
                            }

                        }
                    }
                }
            }
        }//end of most outer forloop
        return res;
    }

};

LC 92 Reverse Linked List II

We will iterate to the node before the start of the reversion. Then reverse.At the time of reverse, curr -> next will point to the tail of reversed inner linked list.
After reverse, we have three linked list, the first part, the reversed part, and the third part.
We want to point the tail of first part to the head of reversed part, which is pointed by prev. We also need to point the tail of reversed part, which is pointed by curr -> next, to head of third part, which is pointed by tempCurr.

tempCurr will point to the node after reversed inner linked 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 (head == NULL)
            return head;
        //go ahead m - 1 step and reverse (n - m + 1 times )
        //then point prev 
        ListNode dummyNode(-1);
        dummyNode.next = head;
        ListNode* curr = &dummyNode;
        for(int i = 0; i < m - 1; i ++){
            curr = curr -> next;
        }
        //curr will be right before the to-be-reversed node


        ListNode* tempNext = NULL;
        ListNode* prev = NULL;
        ListNode* tempCurr = curr -> next;
        for(int i = m - 1; i < n; i ++){
            tempNext = tempCurr -> next;
            tempCurr -> next = prev;
            prev = tempCurr;
            tempCurr = tempNext;
        }
        //after reversing n - m + 1 nodes, prev will be on the next node
        //need to point tail of reverse(pointed by curr -> next) to tempCurr.
        //need to point curr to head of reversed(pointed by prev) to tempCurr
        curr -> next -> next = tempCurr;
        curr -> next = prev;

        return dummyNode.next;
    }
};