LeetCode 1482.

Tags: LeetCode

Intuition

I use dynamic programming on my first thought. It works but turns out to be TLE.

Then I saw the range of input parameters that each bloomDay[i] should be smaller than 10^9.

The implementation should be simplified to a searching problem so I try Binary Search on my second thought.

Approach

Assume the answer is ans, 1 <= ans <= 10^9. Use BS to find the answer.

Initialize the parameters we’ll use:

left = 1
right = 10^9
mid = 1 + (10^9-1)/2
answer=mid

If bloomDay is qualified to current mid, then the answer must be located in the range of left and mid (left <= ans <= mid). Otherwise, it must be located between mid+1 and right (mid+1 <= ans <= right)

When bloomDay is qualified, left <= answer <= mid

Otherwise, mid + 1<=answer<=right

Complexity

Time complexity: O(nlogn)
Space complexity: O(logn)

Code

class Solution {
    
    // First Attempt
    /*
    public static int minDays(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) return -1;
        // Try Dynamic Programming
        // arr[n - k + 1], 表示從index處開始取k個的值
        int[] minCost = new int[bloomDay.length - k + 1];
        for (int i=0; i<bloomDay.length - k + 1; i++) {
            minCost[i] = bloomDay[i];
            for (int j=1; j<k; j++) {
                minCost[i] = Math.max(minCost[i], bloomDay[i + j]);
            }
        }
        // GOAL: 取m個值總和最小; CONSTRAINT: 兩者相隔必須k
        return dp(minCost, k, 0, m, 0);
    }

    public static int dp(int[] minCost, int k, int start, int left, int cost) {
        if (cost < 0) return -1;
        if (left == 0) return cost;
        if (start >= minCost.length) return -1;
        int n = minCost.length + k - 1;
        if ((n - start - 1) / k + 1 < left) return -1;

        int get = dp(minCost, k, start + k, left-1, Math.max(cost, minCost[start]));
        int pass = dp(minCost, k, start + 1, left, cost);
        if (get < 0 && pass < 0) return -1;
        else if (get < 0) return pass;
        else if (pass < 0) return get;
        return Math.min(get, pass);
    }
    */

    // Second Attempt: BS
    public int minDays(int[] bloomDay, int m, int k) {
        if (m * k > bloomDay.length) return -1;
        
        //由於結果只會在1和10^9之間產生則使用BS
        int l = 1, r = 1000000000;
        int min = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int consecutive = 0, count = 0;
            for (int i=0; i<bloomDay.length; i++) {
                if (bloomDay[i] <= mid) {
                    if (++consecutive == k) {
                        consecutive = 0;
                        count++;
                    }
                }else{
                    consecutive = 0;
                }
            }
            if (count >= m) {
                min = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return min;
    }
}

Check out the description of this problem at LC 1482.