leetcode Question: Kth Largest Element in an Array

Kth Largest Element in an Array


Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.

Analysis:

This is a good practice of using data structure Heap ! We know that C++ STL already has heap operations, but here in this post, I'd like to write the heap data structure of our own. In one of my previous post (here), I have already introduced the heap sort, in which the code can be applied in this problem perfectly.  Now I will briefly describe how to construct a heap.

In this problem, we utilize array  (list in python) to represent heap, literally heap is a Tree structure, which has the following property:
The value of parent node is greater/smaller than that of its children.
(Be careful with the definition, it has no constrains about the child nodes in the same level)

Before we start to construct heap, firstly let's review the tree representation using array. Simply, let's use a vector<int> to define a binary tree A, where the value of node is type int. Then let's define the tree structure:
(1) Every element is used to represent a tree node.
(2) The root node is defined as the 1st element of A, A[0].
(3) For each node A[i], its left child is A[i*2+1], its right child is A[i*2+2].
(4) For each node A[i], its parent node is A[(i-2)/2], when (i-2)/2 >=0

This is not a very complete definition, but enough for our heap implementation. Now we construct the heap, as well as heap sort algorithm.

The most important step in the algorithm is called "downshift". This downshift operation, takes the root node of the binary tree, compare to its left and right children, swap the value with the greater/smaller child, recursively.  This can be implemented as a standalone function.

Since the tree leaves has no child node, so the leaf nodes are left without any downshift operation. To construct the heap, we can downshift all the non-leaf nodes, from bottom to top. After this loop, the tree is now called a heap.

In order to get the heap sort result (which is usually an array), one more operation is needed. Currently the heap is a binary tree, to get the sorted array, every time we take the root node (which is biggest/smallest element), and then swap the root node with the last node in the tree. (Remember we have used an array to represent a tree?) , then apply downshift of the root node, to keep the tree as a heap.


Code(C++):

class Solution {
public:
    void downshift(vector<int> &h, int n, int parent){
        if (parent < 0){return;}
        int left = parent*2+1;
        int right = parent*2+2;
        int mxch;
        if (left>=n) {return;}
        if (right>=n){mxch=left;}
        else{
            mxch = h[left]>=h[right]?left:right;
        }
        if (h[parent]<h[mxch]){
            int tmp = h[parent];
            h[parent] = h[mxch];
            h[mxch] = tmp;
            downshift(h,n,mxch);
        }
    }


    void constructHeap(vector<int>& h, int n){
        int parent = (n-2/2);
        for (; parent>=0;parent--){
            downshift(h, n, parent);
        }
    }
    
    void heapsort(vector<int> &h, int n){
        constructHeap(h,n);
        int i=n-1;
        vector<int> b(n,0);
        while (i>=0){
            b[n-i-1]=h[0];
            int tmp = h[0];
            h[0] = h[i];
            h[i] = tmp;
            downshift(h,i,0);
            i--;
        }
        for (int i=0;i<n;i++){
            h[i] = b[i];
        }
    }
    
    int findKthLargest(vector<int>& nums, int k) {
        heapsort(nums,nums.size());
        return nums[k-1];
    }
};


Code(Python):

class Solution:
    def downshift(self, nums, n, parent):
        if parent < 0:
            return
        left = parent * 2 + 1
        right = parent * 2 + 2
        if left >= n:
            return
        if right >=n:
            mxch = left
        else:
            if nums[left] >= nums[right]:
                mxch = left
            else:
                mxch = right
                
        if nums[parent]<nums[mxch]:
            nums[parent], nums[mxch] = nums[mxch], nums[parent]
            self.downshift(nums, n, mxch)

    def constructHeap(self, nums, n):
        parent = (n-2)/2
        for i in range(parent,-1,-1):
            self.downshift(nums, n, i)
    
    def heapSort(self, nums, n):
        self.constructHeap(nums, n)
        i = n - 1
        num_tmp = []
        while i>=0:
            num_tmp.append(nums[0])
            nums[0], nums[i] = nums[i], nums[0]
            self.downshift(nums,i,0)
            i -= 1
        return num_tmp
    
    # @param {integer[]} nums
    # @param {integer} k
    # @return {integer}
    def findKthLargest(self, nums, k):
        new = self.heapSort(nums,len(nums))
        return new[k-1]
        

leetcode Question: Course Schedule II

Course Schedule II

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
4, [[1,0],[2,0],[3,1],[3,2]]
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Analysis:

This is highly related to the previous question Course Schedule. You can find all the details in this previous post and the only difference in this question is to add an array storing the results. The straightforward  way is to modify the BFS algorithm.


Code(C++, BFS):

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> ind(numCourses,0); //indegree vector
        vector<int> res;
         
        //construct map & get indegree of each vertex
        vector<vector<bool> > map(numCourses, vector<bool>(numCourses, false));
        for (int i=0;i<plen;i++){
            //Important: in case of duplicates in prerequisites, only +1 indegree 
            if (map[prerequisites[i].first][prerequisites[i].second] == false){
                map[prerequisites[i].first][prerequisites[i].second] = true;
                ind[prerequisites[i].first]++;
            }
        }
         
        //BFS
        stack<int> st;
        for (int i=0;i<numCourses;i++){
            if (ind[i]==0) st.push(i);
        }
         
        int count = 0;  // to get the bool result
         
        while (!st.empty()){
            int tmp = st.top();
            res.push_back(tmp);
            st.pop();
            count ++;
            for (int i=0;i<numCourses;i++){
                if (map[i][tmp]){
                    ind[i]--;
                    if (ind[i]==0) st.push(i);
                }
            }
        }
        if (count < numCourses){
            vector<int> emp; // empty array
            return emp;
        }
        else{
            return res;
        }
    }
};

Code(Python, BFS):

class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {integer[]}
    def findOrder(self, numCourses, prerequisites):
        map = [[] for x in range(numCourses)]
        ind = [0 for x in range(numCourses)]
        res = [] 
        for p in prerequisites:
            if p[0] not in map[p[1]]:
                ind[p[0]] += 1
                map[p[1]].append(p[0])
        st = []
        for i in range(numCourses):
            if ind[i] == 0:
                st.append(i)
        count = 0
        while st:
            tmp = st[0]
            st.pop(0)
            res.append(tmp)
            count += 1
            for i in map[tmp]:
                ind[i] -= 1
                if ind[i] == 0:
                    st.append(i)
                         
        if count < numCourses:
            return []
        else: 
            return res
         
        


leetcode Question: Add and Search Word - Data structure design

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

Analysis:


This is quite similar to the previous question  Implement Trie (Prefix Tree), where a Trie data structure is required to be implemented.

The only difference in this question is to add a DFS search (or back tracking). The figure below shows the general idea of this question.  Implement details is much similar to "Implement Trie (Prefix Tree)".  When you do search, be careful with the few lines of code related to backtracking. Note that, it is not "return search(...)", but you have to check every child of current node, if there is one True return, the result is True.




Code(C++):


class TrieNode {
public:
    TrieNode(){
        value = 0;
        for (int i=0;i<26;i++){
            children[i]=NULL;
        }
    }
    int value;
    TrieNode* children[26];
};


class WordDictionary {
private:
    TrieNode* trie;
    int count;
public:

    // Constructor
    WordDictionary(){
        trie = new TrieNode();
        count  = 0;
    }
    
    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode* p = trie;
        int l = word.size();
        for (int i=0;i<l;i++){
            int idx = word[i] - 'a';
            if (!p->children[idx]){
                p->children[idx] = new TrieNode();
            }
            p = p->children[idx];
        }
        p->value = ++count;
    }


    bool search2(string &word, int pos, TrieNode* p) {
        if (pos == word.size()){
            return  p->value == 0 ? false: true;
        }else{
            if (word[pos] == '.'){
                for (int j=0;j<26;j++){
                    if (p->children[j]){
                        if (search2(word, pos+1, p->children[j])){
                            return true;
                        }
                    }
                }
                return false;
            }else{
                int idx = word[pos] - 'a';
                if (p->children[idx]){
                    return search2(word, pos+1, p->children[idx]);
                }else{
                    return false;
                }
            }   
        }
    }
        
    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return search2(word, 0, trie);
    }
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");

Code(Python):

class TrieNode:
    def __init__(self):
        self.value = 0
        self.children = [None]*26
    
class WordDictionary:
    
    # initialize your data structure here.
    def __init__(self):
        self.trie = TrieNode()
        self.count = 0

    # @param {string} word
    # @return {void}
    # Adds a word into the data structure.
    def addWord(self, word):
        p = self.trie
        for ch in word:
            idx = ord(ch)-ord('a')
            if not p.children[idx]:
                p.children[idx] = TrieNode()
            p = p.children[idx]
        self.count += 1
        p.value = self.count
        

    def search2(self, word, pos, p):
        if pos == len(word):
            if p.value == 0:
                return False
            else:
                return True
        else:
            if word[pos] == '.':
                for pp in p.children:
                    if pp:
                        if self.search2(word, pos+1, pp):
                            return True
                return False
            else:
                idx = ord(word[pos])-ord('a')
                if not p.children[idx]:
                    return False
                else:
                    return self.search2(word, pos+1, p.children[idx])


    # @param {string} word
    # @return {boolean}
    # Returns if the word is in the data structure. A word could
    # contain the dot character '.' to represent any one letter.
    def search(self, word):
        return self.search2(word, 0, self.trie)
            
        

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")