LIKE CODING: August 2020

Monday, August 31, 2020

LeetCode [1425] Constrained Subsequence Sum

1425. Constrained Subsequence Sum

Hard

Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        Deque<Integer> dq = new ArrayDeque<>();
        int n = nums.length, r = 0, ret = Integer.MIN_VALUE;
        int[] dp = new int[n];
        while(r<n){
            dp[r] = nums[r];
            if(r-k-1>=0 && !dq.isEmpty() && dq.peek()==dp[r-k-1]){
                dq.poll();
            }
            if(!dq.isEmpty() && dq.peek()>0){
                dp[r] += dq.peek();
            }
            while(!dq.isEmpty() && dp[r]>dq.peekLast()){
                dq.pollLast();
            }
            dq.add(dp[r]);
            ret = Math.max(ret, dp[r++]);
        }
        return ret;
    }
}

LeetCode [1438] Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Medium

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int n = nums.length, l = 0, r = 0, ret = 0;
        Deque<Integer> maxD = new ArrayDeque<>();
        Deque<Integer> minD = new ArrayDeque<>();
        while(r<n){
            while(!maxD.isEmpty() && nums[r]>maxD.peekLast()){
                maxD.pollLast();
            }
            while(!minD.isEmpty() && nums[r]<minD.peekLast()){
                minD.pollLast();
            }
            maxD.add(nums[r]);
            minD.add(nums[r]);
            while(maxD.peek()-minD.peek()>limit){
                if(maxD.peek()==nums[l]){
                    maxD.pop();
                }
                if(minD.peek()==nums[l]){
                    minD.pop();
                }
                l++;
            }
            ret = Math.max(ret, r-l+1);
            r++;
        }
        return ret;
    }
}

LeetCode [1462] Course Schedule IV

1462. Course Schedule IV

Medium

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have direct prerequisites, for example, to take course 0 you have first to take course 1, which is expressed as a pair: [1,0]

Given the total number of courses n, a list of direct prerequisite pairs and a list of queries pairs.

You should answer for each queries[i] whether the course queries[i][0] is a prerequisite of the course queries[i][1] or not.

Return a list of boolean, the answers to the given queries.

Please note that if course a is a prerequisite of course b and course b is a prerequisite of course c, then, course a is a prerequisite of course c.

Example 1:

Input: n = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false,true]
Explanation: course 0 is not a prerequisite of course 1 but the opposite is true.

Example 2:

Input: n = 2, prerequisites = [], queries = [[1,0],[0,1]]
Output: [false,false]
Explanation: There are no prerequisites and each course is independent.

Example 3:

Input: n = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true,true]

Example 4:

Input: n = 3, prerequisites = [[1,0],[2,0]], queries = [[0,1],[2,0]]
Output: [false,true]

Example 5:

Input: n = 5, prerequisites = [[0,1],[1,2],[2,3],[3,4]], queries = [[0,4],[4,0],[1,3],[3,0]]
Output: [true,false,true,false]

Constraints:

2 <= n <= 100
0 <= prerequisite.length <= (n * (n - 1) / 2)
0 <= prerequisite[i][0], prerequisite[i][1] < n
prerequisite[i][0] != prerequisite[i][1]
The prerequisites graph has no cycles.
The prerequisites graph has no repeated edges.
1 <= queries.length <= 10^4
queries[i][0] != queries[i][1]

class Solution {
    public List<Boolean> checkIfPrerequisite(int n, int[][] prerequisites, int[][] queries) {
        int[][] path = new int[n][n];
        for(int[] p : prerequisites){
            path[p[0]][p[1]] = 1;
        }

        for(int k=0; k<n; ++k){
            for(int i=0; i<n; ++i){
                for(int j=0; j<n; ++j){
                 //   System.out.println(i+" " + k+ " "+j);
                    path[i][j] |= path[i][k]&path[k][j];
                }
            }
        }

        List<Boolean> ret = new ArrayList<>();
        for(int[] q : queries){
            ret.add(path[q[0]][q[1]] == 1);
        }

        return ret;
    }
}

LeetCode [1482] Minimum Number of Days to Make m Bouquets

1482. Minimum Number of Days to Make m Bouquets

Medium

Given an integer array bloomDay, an integer m and an integer k.

We need to make m bouquets. To make a bouquet, you need to use k adjacent flowers from the garden.

The garden consists of n flowers, the ith flower will bloom in the bloomDay[i] and then can be used in exactly one bouquet.

Return the minimum number of days you need to wait to be able to make m bouquets from the garden. If it is impossible to make m bouquets return -1.

Example 1:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let's see what happened in the first three days. x means flower bloomed and _ means flower didn't bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

Example 2:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 2
Output: -1
Explanation: We need 3 bouquets each has 2 flowers, that means we need 6 flowers. We only have 5 flowers so it is impossible to get the needed bouquets and we return -1.

Example 3:

Input: bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
Output: 12
Explanation: We need 2 bouquets each should have 3 flowers.
Here's the garden after the 7 and 12 days:
After day 7: [x, x, x, x, _, x, x]
We can make one bouquet of the first three flowers that bloomed. We cannot make another bouquet from the last three flowers that bloomed because they are not adjacent.
After day 12: [x, x, x, x, x, x, x]
It is obvious that we can make two bouquets in different ways.

Example 4:

Input: bloomDay = [1000000000,1000000000], m = 1, k = 1
Output: 1000000000
Explanation: You need to wait 1000000000 days to have a flower ready for a bouquet.

Example 5:

Input: bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
Output: 9

Constraints:

bloomDay.length == n
1 <= n <= 10^5
1 <= bloomDay[i] <= 10^9
1 <= m <= 10^6
1 <= k <= n

class Solution {
    public int minDays(int[] bloomDay, int m, int k) {
        int l = 1, r = (int)1e9;
        int n = bloomDay.length;
        if(m*k>n) return -1;
        while(l<r){
            int mid = l+(r-l)/2;
            int f = 0, b = 0;
            for(int i=0; i<n; ++i){
                if(bloomDay[i]<=mid){
                    f += 1;
                    if(f>=k){
                        b++;
                        f -= k;
                    }
                }else{
                    f = 0;
                }
            }
            if(b<m){
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return l;
    }
}

LeetCode [1463] Cherry Pickup II

1463. Cherry Pickup II

Hard

Given a rows x cols matrix grid representing a field of cherries. Each cell in grid represents the number of cherries that you can collect.

You have two robots that can collect cherries for you, Robot #1 is located at the top-left corner (0,0) , and Robot #2 is located at the top-right corner (0, cols-1) of the grid.

Return the maximum number of cherries collection using both robots by following the rules below:

From a cell (i,j), robots can move to cell (i+1, j-1) , (i+1, j) or (i+1, j+1).
When any robot is passing through a cell, It picks it up all cherries, and the cell becomes an empty cell (0).
When both robots stay on the same cell, only one of them takes the cherries.
Both robots cannot move outside of the grid at any moment.
Both robots should reach the bottom row in the grid.

Example 1:

Input: grid = [[3,1,1],[2,5,1],[1,5,5],[2,1,1]]
Output: 24
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

Input: grid = [[1,0,0,0,0,0,1],[2,0,0,0,0,3,0],[2,0,9,0,0,0,0],[0,3,0,5,4,0,0],[1,0,2,3,0,0,6]]
Output: 28
Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Example 3:

Input: grid = [[1,0,0,3],[0,0,0,3],[0,0,3,3],[9,0,3,3]]
Output: 22

Example 4:

Input: grid = [[1,1],[1,1]]
Output: 4

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

/*
- 3D-DP question
- m: rows. n: columns
- Must move down at every step, hence there are m-1 steps
- dp is n*n matrix.
- Update dp at every step k=1..m-1
- At step k, dp[i][j] maintains the max cherries when robot1 is at [k,i] and robot2 is at [k,j]
*/
class Solution {
    int[] shift = new int[]{-1,0,1};
    
    public int cherryPickup(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[n][n];
        for(int t=0; t<n; ++t) Arrays.fill(dp[t], -1);
        dp[0][n-1] = grid[0][0] + grid[0][n-1];
 
        int ret = 0;
        for(int k=1; k<=m-1; ++k){
            int[][] tmp = new int[n][n];
            for(int t=0; t<n; ++t) Arrays.fill(tmp[t], -1);
            for(int i=0; i<n; ++i){
                for(int j=0; j<n; ++j){
                    int cherries = -1;
                    for(int di : shift){
                        for(int dj : shift){
                            if(i+di>=0 && i+di<n && j+dj>=0 && j+dj<n){
                                cherries = Math.max(cherries, dp[i+di][j+dj]);
                            }
                        }
                    }
                    if(cherries<0) continue;
                    tmp[i][j] = cherries + grid[k][i] + (j==i?0:grid[k][j]);
                    ret = Math.max(ret, tmp[i][j]);
                }
            }
            dp = tmp;
        }
        
        return ret;
    }
}

Thursday, August 27, 2020

LeetCode [1477] Find Two Non-overlapping Sub-arrays Each With Target Sum

1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Medium

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 1000
1 <= target <= 10^8

class Solution {
    public int minSumOfLengths(int[] arr, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,-1);
        int n = arr.length;
        int sum = 0;
        for(int i=0; i<n; ++i){
            sum += arr[i];
            map.put(sum, i);
        }

        sum = 0;
        int minLeft = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        for(int i=0; i<n; ++i){
            sum += arr[i];
            if(map.containsKey(sum-target)){ //left subarr exists
                minLeft = Math.min(minLeft, i-map.get(sum-target));
            }

            if(minLeft != Integer.MAX_VALUE && map.containsKey(sum+target)){
                min = Math.min(min, minLeft+map.get(sum+target)-i);
            }
        }
        return min==Integer.MAX_VALUE?-1:min;
    }
}