H-Index [LeetCode]

Problem Description

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.

Solution

As we know, H-Index is a measure of productivity and citation impact of a researcher. It is also called Hirsch index or Hirsch number after the name of the physicist Jorge Hirsch.

Picture 1: H-Index for decreasing citations array (Credit: Wiki)

Supposed that citations is an array of numbers of citations of a researcher. We can easily see that the following formula holds if citations is sorted in decreasing order:

h-index of citations = max (min (citations[i], i) for all i from 1 to number of papers)

Therefore, we can easily implement the calculation of h-index by sorting the array in decreasing order then applying the above formula. Below is the 2-line Python code in O(nlogn) time.

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        citations.sort(reverse=True)
        return max([min(k+1, v) for k,v in enumerate(citations)]) if citations else 0

By sorting, it takes O(nlogn) time complexity.
However, we can do much better by an O(n) time algorithm. Pause yourself for a few minutes to think about it before continue reading ^_^.

We have some simple observation here, but it really helps to improve the performance. For each number h from 0 to n where n is the number of papers, we need to find out how many citations of a paper equal h called equal_h. Based on this, we can find the number of citations values that is at least h, and no more than h. To find the number of citations value that is at least h, we take sum of equal_h[i] for i from h to n!!! And similarly, to find the number of citations values that is no more than h citations each, we can sum up equal_h[i] for i from 0 to i. And we can find the h-index by simple running from the back of the array equal_h.
So if running from the back of the array equal_h , and h is the first index that satisfies the following conditions:
equal_h[h] + equal_h[h+1] + ... + equal_h[n] >= h (*)
equal_h[0] + equal_h[1] + ... + equal_h[h] >= N-h (**)
Then h is what we are looking for.
However, we have:
equal_h[0] + equal_h[1] + ... + equal_h[n] = n
Therefore:
equal_h[0] + equal_h[1] + ... + equal_h[h] = n- (equal_h[h+1] + ... + equal_h[n])
Another note is that since h is the first element satisfies the 2 above conditions, then h+1 does not satisfies one of them, meaning that either
(1): { equal_h[h+1] + equal_h[h+2] + ... + equal_h[n] <= h
or (2): { equal_h[h+1] + equal_h[h+2] + ... + equal_h[n] >= h+1
and equal_h[0] + equal_h[1] + ... + equal_h[h+1] < N-(h+1) }
(1) suggests that:
equal_h[0] + equal_h[1] + ... + equal_h[h] >=N-h which is (**)
(2) suggests that:
equal_h[h+2] + equal_h[h+3] + ... + equal_h[n] >= h+2
This inequality will be repeated until equal_h[n] >= n , which is wrong.

So all we need is to find the first h satisfies the condition (*), and we do not need to check the condition (**).
Below are the codes implement in different languages.

I. Python code - O(n) 

class Solution(object):
    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        n = len(citations)
        equal_h = [0] * (n+1)
        for h in range(n):
            if citations[h] >= n: equal_h[n] += 1
            else: equal_h[citations[h]] += 1
        
        s = 0
        for h in range(n,0, -1):
            s += equal_h[h]
            if s>=h:
                return h
            
        return 0

II. Java Code - O(n)

public class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int [] equal_h = new int[n+1];
        for (int h = 0; h<n; h++){
            if(citations[h] >= n) equal_h[n] += 1;
            else equal_h[citations[h]] += 1;
        }
        int s = 0; //we don't need check overflow here coz sum always <= n
        for (int h = n; h>0; h--){
            s += equal_h[h];
            if (s >= h) return h;
            
        }
        return 0;
    }
}

Container With Most Water

Problem Description

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Solution
In this problem, we use 2 pointers, one runs from the 0, one runs backward.

public class Solution {
    public int maxArea(int[] height) {
        //we assume the array height.length > 0
        int max = 0;
        int area;
        for(int i=0, j=height.length-1; i<j;){
            
            if(height[i] > height[j]){
                area = (j-i) * height[j];
                j--;
            }else {
                area = (j-i) * height[i];
                i++;
            }
            if(area > max) max = area;
        }
        return max;
    }
}

Set Matrix Zeroes

Problem Description
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Solution
At first, I came up with a solution: using the first column and first row to store the information about a row or column should be zero. However, the code is very ugly (See Appendix A). Later, I improved the code by use only the row that we first met an zero to store information about whether the column should be zero. Below is the clean code.

public class Solution {
    public void setZeroes(int[][] matrix) {

        int m = -1;
        for(int i = 0; i<matrix.length; i++){
            boolean foundZero = false;
            for(int j=0; j<matrix[i].length; j++){
                if(matrix[i][j] == 0){
                    foundZero = true;
                    break;
                }
            }
            if(foundZero && m==-1){
                m = i;
                continue;
            }
            if(foundZero){
                for(int j =0;j<matrix[i].length; j++){
                    if(matrix[i][j] == 0) matrix[m][j] = 0;
                    matrix[i][j] = 0;
                }
            }
        }
        if(m!= -1){
            for(int j = 0; j<matrix[m].length; j++){
                if(matrix[m][j] == 0)
                for(int i =0; i<matrix.length; i++)
                    matrix[i][j] = 0;
                matrix[m][j] = 0;
            }
        }
    }
}

Appendix A: How ugly it was

public class Solution {
    public void setZeroes(int[][] matrix) {
        
        boolean firstRowZero = false;
        boolean firstColZero = false;
        
        for(int i =0; i<matrix.length; i++)
            if(matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
            
        for(int i =0; i<matrix[0].length; i++)
            if(matrix[0][i] == 0) {
                firstRowZero = true;
                break;
            }
                
        for(int i = 1; i<matrix.length; i++){
            for(int j = 1; j<matrix[0].length; j++){
                if(matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        for(int i=1; i<matrix.length; i++){
            if(matrix[i][0] == 0)
            for(int j=1; j<matrix[0].length; j++){
                matrix[i][j] = 0;
            }
        }
        for(int i=1; i<matrix[0].length; i++){
            if(matrix[0][i] == 0)
            for(int j=1; j<matrix.length; j++){
                matrix[j][i] = 0;
            }
        }
        
        if (firstRowZero)
            for(int i =0; i<matrix[0].length; i++)
                matrix[0][i] = 0;
        if (firstColZero)
            for(int i=0; i<matrix.length; i++)
                matrix[i][0] = 0;
    }
}

Appendix B: Python Code for the good solution

class Solution(object):
    def setZeroes(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        m = -1
        for i in range(len(matrix)):
            found = False
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    found = True
                    break
            if found and m==-1:
                m = i
                continue
            if found:
                for j in range(len(matrix[i])):
                    if matrix[i][j] == 0:
                        matrix[m][j] = 0
                    matrix[i][j] = 0
        
        if m!=-1:        
            for j in range(len(matrix[m])):
                if matrix[m][j] == 0:
                    for i in range(0, len(matrix)):
                        matrix[i][j] = 0
                matrix[m][j] = 0

Maximum Rectangle

Problem Description
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Solutions
I. Solution by finding largest rectangle in histogram

class Solution:
    # @param matrix, a list of lists of 1 length string
    # @return an integer
    def maximalRectangle(self, matrix):
        if not matrix:
            return 0
        h, w = len(matrix), len(matrix[0])
        m = [[0]*w for _ in range(h)]
        for j in range(h):
            for i in range(w):
                if matrix[j][i] == '1':
                    m[j][i] = m[j-1][i] + 1
        return max(self.largestRectangleArea(row) for row in m)
    
    def largestRectangleArea(self, height):
        '''
        This uses the way we calculate maximum rectangle in histogram
        '''
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area

Largest Rectangle in Histogram

Problem Description
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

For example,
Given height = [2,1,5,6,2,3],
return 10.
Solutions
I. Using stack:
The idea is using stack to store non-decreasing elements.

class Solution:
    # @param {integer[]} height
    # @return {integer}
    def largestRectangleArea(self, height):
        height.append(0)
        stack, area = [], 0
        for i in range(len(height)):
            while stack and height[stack[-1]] > height[i]:
                h = height[stack.pop()]
                w = i if not stack else i-stack[-1]-1
                area = max(area, h*w)
            stack.append(i)
        return area

Further Discussion
This is a pretty interesting problem. It has many applications, one of which you can see in this post.
We also can expand the problem to some other problems. Can you solve the following problems? Please post a comment to discuss ^_^.
A. Find the largest rectangle in this special "Historgram"
We expand the histogram to both directions - positive and negative, as in the picture below.

B. Find the largest box in 3-d Histogram
The original problem is a 2D histogram. Suppose we have 3D histogram, can we find the box with maximum volume?

Distinct Subsequences

Problem Description

Given a string S and a string T, count the number of distinct sub-sequences of T in S.

A sub-sequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

NOTE: The above problem statement is not very clear. We can make it "cleaner" by re-stating the problem as:
Given a string S and a string T, counting the number of ways that we remove some (or none) characters in S to get the remaining string equal to T.

Solutions

For a string str, we denote str[0,j] is the sub-string of str from index 0 to j inclusively. We easily guess that this solution can be solved by Dynamic Programming.
If we call dp[i][j] is the number of ways to remove some characters from S[0,i] to get T[0,j], we have the recursive formula:
dp [i][j] = dp[i-1][j] if S[i] != T[j] , or
dp [i][j] = dp[i-1][j] + dp[i-1][j-1] if S[i] ==T[j]

Therefore, we can come up with solution I), and improve it on II).

I. O(m*n) space

public class Solution {
    public int numDistinct(String s, String t) {
        if(s.length()==0 || s == null || t == null || t.length() == 0) return 0;
        int[][] dp = new int[s.length()][t.length()];
        
        char c = t.charAt(0);
        for(int i=0; i<s.length(); i++){
            dp[i][0] = (i==0? 0: dp[i-1][0]) + (s.charAt(i)==c?1:0);
        }
        for(int i = 1; i<s.length(); i++){
            c = s.charAt(i);
            for(int j=1; j<t.length(); j++){
                dp[i][j] = dp[i-1][j] + (t.charAt(j)==c?dp[i-1][j-1]:0);
            }
        }
        return dp[s.length()-1][t.length()-1];
    }
}

II. O(n) space where n is length of T
We see that the formula of dp[i][j] refer to only dp[i-1][j] and dp[i-1][j-1]. This gives us the idea that we can reduce the space to O(n).
Since we need to make use of dp[i-1][j-1], we run backward!!!

public class Solution {
    public int numDistinct(String s, String t) {
        if(s == null || t == null || t.length() == 0) return 0;
        int[] dp = new int[t.length()];
        
        for(int i = 0; i<s.length(); i++){
            char c = s.charAt(i);
            for(int j=dp.length-1; j>=0; j--){
                if(c == t.charAt(j)){
                    dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
                }
            }
        }
        return dp[t.length()-1];
    }
}

House Robber : Part 1

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solutions

This problem is a typical dynamic programming problem. Here I just want to explain a little bit for those who are at the beginning of the long journey - programming every day! (For those who are familiar with DP, you can take a look at some solutions below, they might be useful for you ^_^.)

In dynamic programming problem, all we need to do is to find the recursion function. In many difficult problems, it is very hard to find the recursion functions. However, in this problem, it is pretty easy.

All you need to think is: which function we should choose in this problem? 

A typical thinking when encountering this problem is: we have some f(n) if array is of length n. How f(n+1) is calculated if array is of length (n+1)?

suppose the array is of length n, and the maximum amount of money you can rob is f(n). We need to make another condition here: we must rob the last house in that array! Why do we need this? To make it easy to calculate the function recursively. Yes it is.

I will list the recursion relation here, and you will think why:

f(n+3) = A[n+3] + max ( f(n+1) , f(n)) , where A is 1-based array of amounts of money you can rob.

And we can put this into code in java & python as below

I. Java

public class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n > 2)
            nums[2] += nums[0];
        for (int i = 3; i<nums.length; i++){
            nums[i] += Math.max(nums[i-2], nums[i-3]);
        }
        return Math.max(nums[n-1], nums[n-2]);
    }   
}

II. Python

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        n = len(nums)
        if n == 0: return 0
        if n == 1: return nums[0]
        if n > 2:
            nums[2] += nums[0]
        for i in range(3, n):
            nums[i] += max(nums[i-2], nums[i-3])
            
        return max(nums[n-1], nums[n-2])

III. Python - 3 line version
You might not satisfied with the above the solutions. But thhe following code is too simple that makes me fall in love with python forever!

class Solution:
    # @param {integer[]} nums
    # @return {integer}
    def rob(self, nums):
        first, second = 0, 0
        for i in nums: first, second = second, max(first + i, second)
        return second

NOTE: the above code is based on the following formula:

f(0) = nums[0]
f(1) = max(nums[0], nums[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )

IV. Java version of the 3-line python version

public class Solution {

    public int rob(int[] num) {
        int first = 0; int second = 0; int t;
        for (int n :num) {
            t = second;
            second = Math.max(first + n, second);
            first = t;
        }
        return second;        
    }
}

Jump Game

Problem Description

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.

Solutions

The idea is obvious. We use dynamic programming technique, and scan the array forward or backward. Needless to say, the code has just a few lines.
I. Scanning Backward

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def canJump(self, nums):
        n = len(nums)
        last = n-1
        for i in range(2,n+1):
            if n-i + nums[-i] >= last:
                last = n-i
        return last == 0

II. Scanning Forward

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def canJump(self, nums):
        reachable = 0
        for i in range(len(nums)):
            if i > reachable: return False
            reachable = max(reachable, i+nums[i])
        return True

Unique Paths: Part 2

Problem Description

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Solutions

The solution for this problem is also pretty obvious. In the previous part, we examine dynamic solutions and combinatoric solution. However, in this problem, we are no longer able  to use the combinatoric solution! Below is just a dynamic solution in python.

class Solution:
    # @param {integer[][]} obstacleGrid
    # @return {integer}
    def uniquePathsWithObstacles(self, obstacleGrid):
        
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        a = [0] * (n+1)
        a[-1] = 1
        
        for i in range(1,n+1):
            if obstacleGrid[m-1][-i] == 0:
                a[n-i] = a[n-i+1]
        
        a[-1] = 0
        for j in range(2, m+1):
            for i in range(1, n+1):
                if obstacleGrid[m-j][-i] == 0:
                    a[n-i] += a[n-i + 1]
                else:
                    a[n-i] = 0
        return a[0]

Unique Paths : Part 1

Problem Description
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Solutions:
This is a typical problem using dynamic programming. However, this problem is the first level of dynamic programming problems! All you need is to find out the recursive relation, and implement it!
NOTE: small m & n would suggest us that this is a dynamic programming problem. However, since m & n are too small, it suggests that we can solve the problem using another method! Let's look at the 3rd solution for it ^_^
I. Simple Solution

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [[0] * (n+2) for i in range(m+1)]
        
        for i in range(1, n+1):
            a[m][i] = 1
        for i in range(1,m):
            for j in range(0,n):
                a[m-i][n-j] = a[m-i+1][n-j] + a[m-i][n-j+1]
                
        return a[1][1]

II. Improvement on Solution time & Space Complexity
In this solution, we use less space than the above solution.

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        a = [ 1 for i in range(n)]
        
        for j in range(1, m):
            for i in range(1,n):
                a[i] += a[i-1]
        return a[n-1]

III. Combinatoric Solution
We see that the robot is standing at location (1,1), and it wants to move to location (m,n). So in total, it needs to move (m-1) steps downwards, and (n-1) steps rightwards, in any orders! If we mark going down as 1, and going to the right as 0, we have a string of length (m+n-2) which consists of 1 and 0. So you guess it, there are how many strings like that? Yes, it is (m+n-2)!/[(n-1)!*(m-1)!]

class Solution:
    # @param {integer} m
    # @param {integer} n
    # @return {integer}
    def uniquePaths(self, m, n):
        # we assume m, n >= 1
        if m == 1 or n == 1: return 1
        
        m -= 1
        n -= 1
        if m > n:
            t = m
            m = n
            n = t
        
        result = 1
        for i in range(1,m+1):
            result *= (n + i)
            result /= i

Order Statistics: Minimum, Maximum, Median and k-th element

In this article, we are going to do some small researches about Order Statistics. Given a unsorted array, we need to find an elements that is k-th when that array is sorted. When k=0, we have the minimum element. If k=array.length-1, we have the maximum. We may also need to find the median of the array.
In part 1, we will examine the case of minimum and maximum with some little interesting problems.
If you think that this is easy for you, you can skip to part 2 where we discuss solving the general problem in linear time.

Part 1: Special Cases
I. Finding Minimum or Maximum
This is pretty easy problem. Below is the code for finding minimum. For finding maximum, it is similar. To solve this problem, we need to use n-1 comparisons where n is the length of the array.

public int findMinimum(int[] a){

    //We assume the array has at least 1 element        
    int min = a[0];
    for(int i=1; i<a.length; i++){
        if(a[i] < min)
            min = a[i];
    }
    return min;
}

II. Finding Minimum and Maximum
There are cases that we need to find both minimum and maximum of an unsorted array. We can easily find them by using the above algorithm. However, it requires 2 * (n-1) comparisons. We can do better in terms of number of comparisons! Pause yourself for a few seconds to think about it.

In order to solve this, we pick 2 elements at a time. We compare the smaller element with the current min, and the bigger element with the current max, and update min and max accordingly. The number of comparisons is around 3/2 * n.

public int[] findMinAndMax(int[] a){
    //we assume that the array has at least 2 elements
    int min = a[0]>a[1]?a[1]:a[0];
    int max = a[0]>a[1]?a[0]:a[1];
    
    int l = a.length % 2 == 0? a.length:a.length-1;
    int smaller, bigger;
    for(int i = 2; i<l;i+= 2){
        if(a[i] > a[i+1]){
            smaller = a[i+1]; bigger = a[i];
        }else{
            smaller = a[i]; bigger = a[i+1];
        }
        if (min > smaller) min = smaller;
        if (max < bigger) max = bigger;
    }
    
    if(a.length % 2 == 1){
        if(a[a.length-1] > max) max = a[a.length-1];
        else if (a[a.length-1] < min) min = a[a.length-1] ;
    }
    int result[] = new int[]{min, max};
    return result;
}

III. Finding the Second Smallest
To find the second smallest we can easily do it with 2 * n comparisons. And again, we can do better with only (roughly) n + lgn comparisons.
We solve this using divide and conquer approach. First, we find the smallest and second smallest of the first half of the array, then find the smallest of second smallest of the second half of the array. Then we can combine the results of the 2 halves. Below is the java code.

public int findSecondSmallest(int[] a){

    //We assume that the array has at least 2 elements
    return findMinAnd2ndSmallest(a, 0, a.length-1)[1];
} 

//find min & second smallest
private int[] findMinAnd2ndSmallest(int[] a, int start, int end){
    if(start == end) return new int[]{a[start], Integer.MAX_VALUE};
    int[] left = findMinAnd2ndSmallest(a, start, (start+end) / 2);
    int[] right = findMinAnd2ndSmallest(a,(start+end) / 2+1, end);
    int smallest = 0, secondSmallest = 0;
    if(left[0] < right[0]) { 
        smallest = left[0]; secondSmallest = right[0];
        if(right[0] > left[1]) secondSmallest = left[1];
    }else {
        smallest = right[0]; secondSmallest = left[0];
        if(left[0] > right[1]) secondSmallest = right[1];
    }
    return new int[]{smallest, secondSmallest};
}

Part 2: General Cases