LeetCode - Largest Plus Sign

09 Mar 2018 • LeetCode(Second)

Question Definition

In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.

An “axis-aligned plus sign of 1s of order k” has some center grid[x][y] = 1 along with 4 arms of length k-1 going up, down, left, and right, and made of 1s. This is demonstrated in the diagrams below. Note that there could be 0s or 1s beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1s.

More …

LeetCode - Kth Largest Element in an Array

09 Mar 2018 • LeetCode(Second)

Question Definition

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.

Java Solution

public int findKthLargest(int[] nums, int k) {
    if(nums.length == 0 || k < 0 || k > nums.length) return -1;
    int start = 0;
    int end = nums.length - 1;
    while(true){
        int index = partition(nums, start, end);
        if(index == k - 1) return nums[index];
        if(index > k - 1)
            end = index - 1;
        else
            start = index + 1;
    }
}

private int partition(int[] a, int lo, int hi){
    int i = lo, j = hi+1; // left and right scan indices
    int v = a[lo]; // partitioning item
    while (true)
    { // Scan right, scan left, check for scan complete, and exchange.
        while (++i < hi && a[i] > v);
        while (--j > lo && v > a[j]) if (j == lo) break;
        if (i >= j) break;
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    int temp = a[lo];
    a[lo] = a[j];
    a[j] = temp;
    return j;
}

LeetCode - H-Index II

09 Mar 2018 • LeetCode(Second)

Question Definition

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Java Solution

public int hIndex(int[] citations) {
    int len = citations.length, left = 0, right = len - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (citations[mid] == len - mid) return len - mid;
        else if (citations[mid] > len - mid) right = mid - 1;
        else left = mid + 1;
    }
    return len - left;
}