DEV Community: Kardel Chen

Leetcode 1885 Count Pairs in Two Arrays

Kardel Chen — Sun, 16 Jan 2022 15:52:14 +0000

class Solution {
    public long countPairs(int[] nums1, int[] nums2) {
        // We are counting i&j that ((nums1[i]-nums2[i])+(nums1[j]-nums2[j])>0)
        int N = nums1.length;
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = nums1[i] - nums2[i];
        }
        // sort that, then this question is like a 2Sum question.
        Arrays.sort(nums);
        long res = 0;
        // Use two pointers like 2Sum
        int i = 0;
        int j = nums.length - 1;
        while(j > i){
            // if nums[i] + nums[j] > 0, then (j-i) are all available results
            if(nums[i] + nums[j] > 0){
                res += j - i;
                j--;
            }else{
                // or increase i to try new value to make the sum larger
                i++;
            }
        }
        return res;
    }
}

Leetcode 540 Single Element in a Sorted Array

Kardel Chen — Sun, 16 Jan 2022 15:50:55 +0000

class Solution {
    public int singleNonDuplicate(int[] nums) {
        return singleNonDuplicate(nums, 0, nums.length-1);
    }
    private int singleNonDuplicate(int[] nums, int l, int r){
        int mid = (r-l) / 2+l;
        int left = mid-l+1;
        // if there is only one element to search (nums[l])
        if(r == l){
            return nums[l];
        }
        // if nums[mid] is the unique element 
        if(nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]){
            return nums[mid];
        }else if(nums[mid] == nums[mid-1]){
            // if 
            if(left % 2 == 1){
                // if left is odd, then the unique element is at left [l, mid] 
                return singleNonDuplicate(nums, l, mid);
            }else{
                // if right is odd, then the unique is at [mid+1, r]
                return singleNonDuplicate(nums, mid+1, r);
            }
        }else{
            if(left % 2 == 1){
                // if left is odd, then the unique element is at right [mid, r]
                return singleNonDuplicate(nums, mid, r);
            }else{
                // if right is odd, then the unique element is at left [l, mid-1]
                return singleNonDuplicate(nums, l, mid-1);
            }
        }
    }
}

Leetcode 759 Employee Free Time

Kardel Chen — Sun, 16 Jan 2022 15:49:52 +0000

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        # In this question, we just find the union of schedules
        schedule_set = set()
        # flatten the intervals and use set to remove duplicates
        for employee in schedule:
            for interval in employee:
                schedule_set.add((interval.start, interval.end))
        # sort mainly by starting index
        working_times = sorted(list(schedule_set))
        start = -float("inf")
        end = float("inf")
        # res is the union of all working time
        res = []
        for working_time in working_times:
            # initial
            if start == -float("inf") and end == float("inf"):
                start = working_time[0]
                end = working_time[1]
            # if new working time is inside previous times
            elif start <= working_time[0] <= working_time[1] <= end:
                pass
            # if new game has overlapping with previous times but not inside it
            elif start <= working_time[0] <= end <= working_time[1]:
                end = working_time[1]
            # if there is no overlapping
            elif end < working_time[0]:
                res.append((start, end))
                start = working_time[0]
                end = working_time[1]
        # we pop the last element
        if not (start == -float("inf") and end == float("inf")):
            res.append((start, end))
        res2 = []
        # find leisure time
        for i in range(len(res) - 1):
            res2.append(Interval(res[i][1], res[i + 1][0]))

        return res2

Leetcode 1209 Remove All Adjacent Duplicates in String II

Kardel Chen — Sun, 16 Jan 2022 15:48:42 +0000

import java.util.Stack;

class Solution {
    class Wrapper{
        // wrapper for counting adjacent duplicates in String
        //c -> character
        char c;
        //n -> count number
        int n;
        Wrapper(char c, int n){
            this.c = c;
            this.n = n;
        }

        @Override
        public String toString() {
            return "Wrapper{" +
                    "c=" + c +
                    ", n=" + n +
                    '}';
        }
    }
    public String removeDuplicates(String s, int k) {
        Stack<Wrapper> stack = new Stack<>();
        int i = 0;
        //use sliding window O(n) to count duplicate adjacent elements
        while(i < s.length()){
            char c = s.charAt(i);
            int j = i+1;
            while(j < s.length() && s.charAt(j)==c){
                j++;
            }
            int left = (j-i);// duplicate numbers
            // find previous  Wrappers
            while(!stack.isEmpty() && stack.peek().c == c){
                Wrapper pop = stack.pop();
                left += pop.n;
            }
            left = left % k;
            if(left != 0) {
                stack.push(new Wrapper(c, left));
            }
            // update i
            i = j;
        }
        StringBuilder sb = new StringBuilder();
        for (Wrapper wrapper : stack) {
            sb.append(String.valueOf(wrapper.c).repeat(Math.max(0, wrapper.n)));
        }

        return sb.toString();
    }
}

Leetcode 1326 Minimum Number of Taps to Open to Water a Garden

Kardel Chen — Sat, 15 Jan 2022 22:35:31 +0000

from typing import List


class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        # find intervals starting from different locations
        intervals = []
        for center, width in enumerate(ranges):
            # if the element is 0, then this element is useless
            if width != 0:
                # restrict the interval in [0, n]
                interval = [max(0, center - width), min(center + width, n)]
                intervals.append(interval)
        # if every element is 0, then return -1
        if not intervals:
            return -1
        # find the furthest location it can reach from a current location
        d = {}
        for interval in intervals:
            if interval[0] not in d:
                d[interval[0]] = []
            d[interval[0]].append(interval[1])
        for k in d:
            d[k] = max(d[k])
        # current location
        loc = 0
        # result
        res = 0
        # if it doesn't reach the furthest location (n)
        while loc != n:
            # find the furthest location (max(...)) it can reach (<= d[k]) from our position (k)
            maxLocation = -1
            s = set()
            for k in d:
                if k <= loc:
                    s.add(k)
                    maxLocation = max(maxLocation, d[k])
            if maxLocation == -1:
                return -1
            # delete every element we iterate previously (we won't search elements again)
            for k in s:
                del d[k]
            res += 1
            loc = maxLocation
        return res

Leetcode 124 Binary Tree Maximum Path Sum

Kardel Chen — Fri, 14 Jan 2022 02:58:25 +0000


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    public int maxPathSum(TreeNode root){
        if(root.left == null && root.right == null){
            return root.val;
        }
        return maxPathSum2(root).maxV;
    }

    private ReturnWrapper maxPathSum2(TreeNode root) {
        if(root == null){
            return new ReturnWrapper(-2000, -2000, -2000);
        }
        ReturnWrapper rightMaxPath = maxPathSum2(root.right);
        ReturnWrapper leftMaxPath = maxPathSum2(root.left);
        int rootVal = root.val;
        int newEdgeV = Math.max(root.val, root.val + Math.max(rightMaxPath.edgeV, leftMaxPath.edgeV));
        int newSumV = Math.max(Math.max(root.val, root.val + rightMaxPath.edgeV + leftMaxPath.edgeV), root.val + Math.max(rightMaxPath.edgeV, leftMaxPath.edgeV));
        int newMaxV = Math.max(Math.max(newSumV, leftMaxPath.maxV), rightMaxPath.maxV);
        return new ReturnWrapper(newMaxV, newSumV, newEdgeV);
    }

    class ReturnWrapper{
        private int maxV;
        private int sumV;
        private int edgeV;
        public ReturnWrapper(int maxV, int sumV, int edgeV){
            this.maxV = maxV;
            this.sumV = sumV;
            this.edgeV = edgeV;
        }
        public ReturnWrapper(){

        }
        private boolean optimalIncludesRoot(){
            return maxV == sumV;
        }
        private boolean isAnEdge(){
            return sumV == edgeV;
        }
    }
}

Leetcode 403 Frog Jump

Kardel Chen — Fri, 14 Jan 2022 02:56:32 +0000

from typing import List


class Solution:
    def canCross(self, stones: List[int]) -> bool:
        N = len(stones)
        d = {}
        if stones[1] != 1: # if we cannot jump at initial place, it definitely False
            return False
        # build value-index mapping
        for i, stone in enumerate(stones):
            d[stone] = i
        # dp is the number of jumps to location i
        # for example, we can only jump to pos 1 with 1 units
        # if we can jump to pos X for {a, b, c} units, it means that we can jump to X for a, b, c units
        # it also means that from pos X, we can jump for <a-1, a, a+1, b-1, b, b+1, c-1, c, c+1> units. 
        dp = [{0}, {1}]
        for i in range(2, N):
            dp.append(set())
        for i in range(1, N):
            s = stones[i]
            for k in dp[i]:
                # do jump
                # if k-1 is ok for position stones[i], jump and add to dp
                if s + k - 1 in d and k - 1 != 0:
                    dp[d[s + k - 1]].add(k - 1)
                # if k is ok for position stones[i], jump and add to dp
                if s + k in d and k != 0:
                    dp[d[s + k]].add(k)
                # if k+1 is ok for position stones[i], jump and add to dp
                if s + k + 1 in d and k + 1 != 0:
                    dp[d[s + k + 1]].add(k + 1)
        return len(dp[-1]) != 0

Leetcode 174 Dungeon Game

Kardel Chen — Fri, 14 Jan 2022 02:55:37 +0000

import queue
from typing import List


class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # M and N are dimensions of the dungeon
        M = len(dungeon)
        N = len(dungeon[0])
        # create a dp matrix for dungeon
        dp = [[0]*N for _ in range(M)]
        # from right-bot to left-top
        for i in range(M-1, -1, -1):
            for j in range(N-1, -1, -1):
                if i == M-1 and j == N-1:
                    # at (M-1, N-1) you at least need 1 hp left
                    dp[M - 1][N - 1] = 1
                elif i == M-1 and j != N-1:
                    # at (M-1, j) you need at least 1 hp to be alive, and you need prepare at least
                    # dp[i][j+1] - dungeon[i][j+1] hp to go right cell
                    dp[M-1][j] = max(1, dp[i][j+1] - dungeon[i][j+1])
                elif i != M-1 and j == N-1:
                    # at (i, N-1) you need at least 1 hp to be alive, and you need prepare at least
                    # dp[i+1][j] - dungeon[i+1][j] hp to go bot cell
                    dp[i][j] = max(1, dp[i+1][j] - dungeon[i+1][j])
                else:
                    # at (i, j) upi need at least dp[i + 1][j] - dungeon[i + 1][j] hp to go bot cell and 
                    # dp[i][j+1] - dungeon[i][j+1] hp to go right cell. Also at cell (i, j) you need at least 1 hp.
                    dp[i][j] = max(1, min(dp[i + 1][j] - dungeon[i + 1][j], dp[i][j+1] - dungeon[i][j+1]))
        # you must go through (0, 0) cell, which is not calculated above.
        return max(1, dp[0][0] - dungeon[0][0])

Leetcode 453 Minimum Moves to Equal Array Elements

Kardel Chen — Fri, 14 Jan 2022 02:54:16 +0000

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        return sum(nums) - len(nums) * min(nums)

To understand this, we just think move is 1. add 1 to every element in the array, 2. minus 1 to a specific element
For example, To remove difference of [99, 98, 97, 96],
we only need to remove difference of [3,2,1,0]
and every move operation is "minus 1 to a specific element"
So to remove the difference, we need 3+2+1 operations

Leetcode 81 Search in Rotated Sorted Array II

Kardel Chen — Fri, 14 Jan 2022 02:53:07 +0000

import java.util.Arrays;

class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, target, 0, nums.length-1);
    }
    private boolean search(int[] nums, int target, int l, int r){
        if( l <= r){
            // here we start as a regular binary search
            int mid = (r-l)/2 + l;
            //if target equals to mid/left/right, return true
            // to avoid collision (e.g. difference of target < nums and target <= nums)
            // we do it for l, mid, and r
            if(target == nums[mid] || target == nums[l] || target == nums[r]){
                return true;
            }
            //here is if there is a rotation in this array/subarray, we call it "twisted" 
            if(nums[r]>nums[l]){ // if nums[r] > nums[l], nums[l:r] is not a twisted array 
                if(nums[l] <= target && target <= nums[r]){ // if target in this array, do normal binary search
                    if(target == nums[mid]){
                        return true;
                    }else if(target < nums[mid]){ 
                        return search(nums, target, l, mid-1);
                    }else{
                        return search(nums, target, mid+1, r);
                    }
                }
            //here are cases for twisted array  
            }else if(nums[mid] == nums[l]){ // if mid and l are the same, we cannot know whether the left is twisted or the right is twisted
                                            // For example, [1,1,1,2,1] has a twisted array at right and [1,2,1,1,1] has a twisted array at left
                                            // But they all satisfy nums[mid] == nums[l]
                                            // Here we can only do O(n) search.
                return search(nums, target, l, mid-1)||search(nums, target, mid+1, r);
            }
            else if(nums[mid] > nums[l]){//if nums[mid] > nums[l], at least left subarray is not twisted array
                if(nums[l]<target && target<nums[mid]){ // if target is at left
                    return search(nums, target, l,mid-1);
                }else{  //else
                    return search(nums, target, mid+1,r);
                }
            }else{//if nums[mid] > nums[l], at least right subarray is not twisted array
                if(nums[mid] < target && target < nums[r]){//if target is at right
                    return search(nums, target, mid+1, r); 
                }else{//else
                    return search(nums, target, l, mid-1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
        System.out.println(new Solution().search(nums, 2));
    }
}

Leetcode 909 Snakes and Ladders

Kardel Chen — Fri, 14 Jan 2022 02:51:22 +0000

import java.util.Arrays;

class Solution {
    public boolean search(int[] nums, int target) {
        return search(nums, target, 0, nums.length-1);
    }
    private boolean search(int[] nums, int target, int l, int r){
        if( l <= r){
            // here we start as a regular binary search
            int mid = (r-l)/2 + l;
            //if target equals to mid/left/right, return true
            // to avoid collision (e.g. difference of target < nums and target <= nums)
            // we do it for l, mid, and r
            if(target == nums[mid] || target == nums[l] || target == nums[r]){
                return true;
            }
            //here is if there is a rotation in this array/subarray, we call it "twisted" 
            if(nums[r]>nums[l]){ // if nums[r] > nums[l], nums[l:r] is not a twisted array 
                if(nums[l] <= target && target <= nums[r]){ // if target in this array, do normal binary search
                    if(target == nums[mid]){
                        return true;
                    }else if(target < nums[mid]){ 
                        return search(nums, target, l, mid-1);
                    }else{
                        return search(nums, target, mid+1, r);
                    }
                }
            //here are cases for twisted array  
            }else if(nums[mid] == nums[l]){ // if mid and l are the same, we cannot know whether the left is twisted or the right is twisted
                                            // For example, [1,1,1,2,1] has a twisted array at right and [1,2,1,1,1] has a twisted array at left
                                            // But they all satisfy nums[mid] == nums[l]
                                            // Here we can only do O(n) search.
                return search(nums, target, l, mid-1)||search(nums, target, mid+1, r);
            }
            else if(nums[mid] > nums[l]){//if nums[mid] > nums[l], at least left subarray is not twisted array
                if(nums[l]<target && target<nums[mid]){ // if target is at left
                    return search(nums, target, l,mid-1);
                }else{  //else
                    return search(nums, target, mid+1,r);
                }
            }else{//if nums[mid] > nums[l], at least right subarray is not twisted array
                if(nums[mid] < target && target < nums[r]){//if target is at right
                    return search(nums, target, mid+1, r); 
                }else{//else
                    return search(nums, target, l, mid-1);
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1};
        System.out.println(new Solution().search(nums, 2));
    }
}

Leetcode 11: Container With Most Water

Kardel Chen — Sun, 06 Jun 2021 04:54:51 +0000

Problem:
Problem Statement

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 the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by >array [1,8,6,2,5,4,8,3,7]. In this case, the max area of >water (blue section) the container can contain is 49.

Example 2:

Input: height = [1, 1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

Thinking and Solutions:
Well, I thought since this is a Dynamic Programming problem, we can create a recursion function.

And matrix is a 2 dimension matrix and matrix[i][j] store the maximal area from the i-th index to j-th index.

Then I want to find the maximal area among matrix[i][j-1], matrix[i+1][j] and matrix[i]j.

public class Solution {
    public static int maxArea(int[] height) {
        // Using Dynamic Programming
        // This is the area matrix. The first index is the start index. The second index is the ending index.
        int[][] matrix = new int[height.length][height.length];
        for (int i = 0; i < height.length; i++) {
            for (int j = 0; j < height.length; j++) {
                matrix[i][j] = -1;
            }
        }
        return maxAreaSub(height, 0, height.length-1, matrix);
    }

    public static int maxAreaSub(int[] height, int starting, int ending, int[][] matrix) {
        if(matrix[starting][ending] != -1){
            return matrix[starting][ending];
        }
        if (ending - starting == 1) {
            return Math.min(height[ending], height[starting]);
        }

        int left = maxAreaSub(height, starting, ending - 1, matrix);
        int right = maxAreaSub(height, starting + 1, ending, matrix);
        int current = (ending - starting) * Math.min(height[ending], height[starting]);
        int maxV = Math.max(Math.max(left, current), right);
        matrix[starting][ending] = maxV;
        return maxV;
    }
}

But a problem was that if the list is very long, like 1000 elements in the list, the matrix is 4M ($4 \time 1000 \time 1000$) for integer matrices.

So I thought building the dynamic programming from bottom to top could be a better way because it is more reasonable. Also, you don't need to store the maximal area matrix. Instead, storing the maximal area list for a certain length could be a good idea to reduce the storage pressure.

public class Solution2 {
    public static int maxArea(int[] height) {
        // Using Dynamic Programming
        // This is the area matrix. The first index is the start index. The second index is the ending index.
        int[] miniArea = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            miniArea[i] = 0;
        }
        return maxAreaSub(height, 1, miniArea);
    }

    public static int maxAreaSub(int[] height, int length, int[] miniArea) {
        int[] areas = new int[height.length - length];
        for (int i = 0; i < height.length - length; i++) {
            int left = miniArea[i];
            int right = miniArea[i + 1];
            int current = length * Math.min(height[i], height[i + length]);
            areas[i] = Math.max(current, Math.max(left, right));
        }
        if (areas.length == 1) {
            return areas[0];
        }
        return maxAreaSub(height, length + 1, areas);
    }
}

The storage problem seems to be solved but actually since the recursion function is still too slow, time limit is still exceeded. So here, I sought for others' solutions. This is much easier solution but it seems to work well.

class Solution {
 public int maxArea(int[] height) {
    int left = 0;
        int right = height.length - 1;
        int maxArea = 0;
        while(left < right) {
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            if(height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

It uses a global maximal area. With 2 pointers right and left, we can find a local area and judge which is the current maximal area.

Also, it has a basic idea that the maximal area is from the maximal length or from shorter length with two higher heights. So just greedy search the longer 2 heights could reduce the running time.

Conclusion

According to the problem, I realize 2 things:

Reasonable greedy search could be a good way to reduce the running time.
Writing a while instead of using a recursion function could be a good way for running dynamic programming.