leetCode Question: H-Index

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Analysis:

This problem is pretty straightforward.The easist way which requires more time is sorting the array, the time complexity will be O(n log n) (we ignore this method in this post).

Another way is to use more space, but we can get O(n) time, which is faster than the sorting approach. Thinking about the definition of H-index, the max number of h is the number of paper we have. So we could use a map (or vector in my case), to store: if current paper has i citations, we add map[i] by 1. Note that if citation is more than the number of papers, we added 1 to the last index of the map.

In this way, for each key i in our map, we only need to add the sum of all values afer i to the end, we will know how many papers are there have more then i citations. The maximum i is what we want.

Code (C++):

class Solution {

public:

int hIndex(vector<int>& citations) {

int ssum = 0;

int sz = citations.size();

vector<int>mp(sz+1,0);

for (int i=0;i<sz;++i){

mp[min(sz,citations[i])] +=1;

}

for (int i=sz;i>=0;--i){

ssum += mp[i];

if (ssum >= i){return i;}

}

return 0;

}

};

Code (Python):

class Solution(object):

def hIndex(self, citations):

"""

:type citations: List[int]

:rtype: int

"""

ssum = 0

sz = len(citations)

mp = [0]*(sz+1)

for ci in citations:

mp[min(sz,ci)] +=1

for i in range(sz,-1,-1):

ssum += mp[i]

if ssum>=i:

return i

return 0

leetcode Question: Valid Anagram

Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Analysis:

This simple but important problem would provide you some thinking when dealing with quite a lot of programming questions. The first one is to use sorting, while the other is to use map/hashmap/dictionary.

Considering this problem, the definition of anagram requires two string have exactly same type of chars and the same count of the chars.

Therefore, what we need is to compare  the two strings in some ways, so that we can check both the type and the count of the chars in two strings.  Obviously,  find some data structure to save each char would work well. Then it is naturally comes the use of map, which stores the key and value pair in the buffer, and the "check" process takes only O(1) time.  See the code below you will easily find how it works in just several lines of code.

Using a map will definitely open some new spaces to save the key-value pairs. What if we do not use extra space?  In this problem, if we could "move"  the chars of both strings, check if the two strings are same would solve the anagram. One way of "move" chars is to use sort, since sorting chars is unique to every string and will never lose any of the chars (so the count of chars will not change). So, just sort the strings in same order, then a simple comparison will work well. However, it will take more time, where the sorting have O(n log n) complexity.

Code(C++):

class Solution {
public:
    bool isAnagram(string s, string t) {
        
        int mp[26] = {0};
        if (s.size()!= t.size()){return false;}
        for (int i=0;i<s.size();++i){
            mp[s[i]-'a'] += 1;
            mp[t[i]-'a'] -= 1;
        }
        for (int i=0; i< 26;i++){
            if (mp[i] != 0) {return false;}
        }
        return true;
        
        
        //sort(s.begin(),s.end());
        //sort(t.begin(),t.end());
        //return s == t;
    }
};

Code(Python):

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        mp = [0 for x in range(26)]
        for i in range(len(s)):
            mp[ord(s[i])-ord('a')] += 1
            mp[ord(t[i])-ord('a')] -= 1
        for i in range(26):
            if mp[i] != 0:
                return False
        return True
            

leetcode Question: Copy List with Random Pointer

Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Analysis:

This problem returns a new linked list, which has the same value and structure of the original one. First we can create a new linked list without considering the Random pointer, which is straight forward:  Scan every node in the original list and create the new list (line 21- 27 in the code below).

But how to keep the random pointer also correct ? If we only point the new random pointer to the original random pointer, which is not a deep copy (since the deletion of nodes in original list will delete the new one as well).  So, how to memorize the relative position of the random node to the current node? Firstly I think to use the length from head node to the random node. For each node, I stored the position of its random node, same position node in the new list is the random node for the node in the new list. This idea can work, but is not efficient. For every node you have to search from the start to the end to find the random, the total complexity is O(n^2). Can we quickly locate the position of the node?  Yes!  Hash map!  A map with the node as key and node as the value can finish the job! We can use the original list node as the key, and the same node in the new list as the value.  Now the map[node_old] = node_new, therefore the node_new->random = map[node_old->random]. In this way, the complexity decreases to O(n).

Code:

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (!head){return NULL;}
        map<RandomListNode*,RandomListNode*> mp; //map <originalNode, newNode>
        mp.clear();
        RandomListNode *res=new RandomListNode(0);
        RandomListNode *p=head;
        RandomListNode *q=res;
        
        while (p){
            RandomListNode *tmp = new RandomListNode(p->label);
            q->next = tmp;
            mp[p]=tmp;
            p=p->next;
            q=q->next;
        }
        p=head;
        q=res->next;
        while (p){
            if (p->random==NULL){
                q->random==NULL;
            }else{
                q->random = mp[p->random];
            }
            p=p->next;
            q=q->next;
        }
        return res->next;
    }
};

leetcode Question 106: Substring with Concatenation of All Words

Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

Analysis:

Try to think this problem straightforward:
Say in L there are m strings with length n. 
What string is required to match in S?     A length of m*n string start with each position in S.
What is a match?  In the m*n long string, every string in L appear only once.

So the algorithm is:
Scan every m*n long string start from each position in S, see if all the strings in L have been appeared only once using Map data structure. If so, store the starting position.

Yes, do not consider any DP or DFS solutions, just using the hash map and loop.

Code(C++):

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        int num = L.size();
        int len = L[0].size();
        if (num==0){return res;}
        map<string,int> mp;  
        for (int i=0;i<num;i++){mp[L[i]]++;}      
         
        int i=0;
        while ((i+num*len-1)<S.size()){
            map<string,int> mp2;
            int j=0;
            while (j<num){
                string subs = S.substr(i+j*len,len);
                if (mp.find(subs)==mp.end()){
                        break;
                }else{
                    mp2[subs]++;
                    if (mp2[subs]>mp[subs]){
                        break;
                    }
                    j++;  
                }
            }
            if (j==num){res.push_back(i);}
            i++;
        }
     
        return res;
    }
};

Code(Python):

class Solution:
    # @param S, a string
    # @param L, a list of string
    # @return a list of integer
    def findSubstring(self, S, L):
        res = []            # result list
        num = len(L)        # length of the str list 
        ls = len(S)
        if num == 0:
            return []
        str_len = len(L[0]) # length of each str
        #create the map: count the occurrance of each string
        #Note that set(L) is used to reduce the time, otherwise will not pass the large test
        map_str = dict((x,L.count(x)) for x in set(L))
        i = 0
        while i + num * str_len - 1 < ls:
            map_str2 = {}
            j = 0
            while j < num:
                subs = S[i + j * str_len:i + j * str_len + str_len ]
                if not subs in map_str:
                    break
                else:
                    # Note that dict.get(key, default_val) is used to handel the case that key NOT exist
                    map_str2[subs] = map_str2.get(subs, 0) + 1
                    if map_str2[subs]>map_str[subs]:
                        break
                    j = j + 1
            if j == num:
                res.append(i)
            i = i + 1
        
        return res

        

leetcode Question 129: 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.

Analysis:

At first glance, the "longest" requirement may lead us to DP. But this problem actually tests data structure rather than a certain algorithm.

If there is no O(n) requirement, we can just sort the array (O(n log n)), then find then longest sequence after a scan.

With the time limit O(n), first of all, what comes to my mind is HASH MAP! Because hash map searches value by key in O(1) time. Note that in C++ STL, the map<> data structure is implemented by BST, so the insert in O(log n), therefore we need to use the unordered_map<>, which has O(1) time complexity.

Firstly, we put all the element into a map.
Secondly, how to find the consecutive elements? Since the O(n) requirement, scan the array is a must.
For each element, we need to find its consecutive elements. Consecutive means +1 or -1, a while loop is enough to handle. Search two directions respectively (+1, -1),  during the search if the key is found, remove the current item in the map. This is because if two items are consecutive, the longest elements for this two are the same, no need to search again. In this way, the length of longest consecutive elements can be easily found.

Note that in C++ map<>, find(key) function will return  the end() iterator if key does not exist, But if we use (mp[key]==false), when key is not in the map, the program will insert the key into the map with a default value, so use find function is a safer way.

Code (C++):

class Solution {
public:

    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,bool>mp;
        for (int i=0;i<num.size();i++){
            mp[num[i]]=true;
        }
        
        int res=0;
        for (int i=0;i<num.size();i++){
            int mx=1;      
            int fd = num[i];
            
            mp.erase(num[i]);
            while (mp.find(fd+1)!=mp.end()){
                mx++;
                mp.erase(fd+1);
                fd++;
            }
            
            fd = num[i];
            while (mp.find(fd-1)!=mp.end()){
                mx++;
                mp.erase(fd-1);
                fd--;
            }
            
            if (mx>res){res=mx;}
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dic = {}
        maxlen = 1
        for n in num:
            dic[n] = 1
        for n in num:
            if dic.has_key(n):
                tmp = n + 1
                l = 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp+=1
                tmp = n - 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp-=1
                maxlen = max(l, maxlen)
            else:
                continue
        return maxlen