DEV Community: Flame Chan

LeetCode Day37 Dynamic Programming part 11

Flame Chan — Fri, 19 Jul 2024 05:24:34 +0000

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace"
Output: 3

Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.
Original Page

    public int longestCommonSubsequence(String text1, String text2) {

        int[][] dp = new int[text1.length()+1][text2.length()+1];
        int res = 0;
        for(int i=1; i<=text1.length(); i++){

            for(int j=1; j<=text2.length(); j++){
                dp[i][j] = dp[i-1][j];
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    //i-1, j-1 means the previous text1 substring and the previous text2 substring
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[text1.length()][text2.length()];
    }

1035. Uncrossed Lines

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

nums1[i] == nums2[j], and
the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

Example 1:

Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.

Example 2:
Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
Output: 3

Example 3:
Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
Output: 2

Constraints:

1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000
Original Page

This question is similar to the previous question, if the line does not cross, the max subsequence of the two given arrays will work as well.

    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[2][nums1.length+1];

        for(int i=1; i<=nums2.length; i++){
            for(int j=1; j<=nums1.length; j++){
                if(nums1[j-1] == nums2[i-1]){
                    dp[i%2][j] = dp[(i-1)%2][j-1] + 1;
                }else{
                    dp[i%2][j] = Math.max(dp[i%2][j-1], dp[(i-1)%2][j]);
                }
            }

        }
        return dp[nums2.length%2][nums1.length];
    }

53. Maximum Subarray

Given an integer array nums, find the
subarray
with the largest sum, and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

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

    public int maxSubArray(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = dp[0];

        for(int i=1; i<nums.length; i++){

            dp[i] = Math.max(nums[i], dp[i-1]+nums[i]);

            res = Math.max(res, dp[i]);
        }

        // System.out.println(Arrays.toString(dp));
        return res;

    }

LeetCode Day 36 Dynamic Programming Part 10

Flame Chan — Fri, 19 Jul 2024 03:18:27 +0000

300. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing
subsequence
.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:

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

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

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

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?
Original Page

Wrong Code

    public int lengthOfLIS(int[] nums) {
        int start = nums[0];
        int pre = nums[0];
        int preMax = nums[0];
        int cnt = 1;
        int max = 1;

        for(int i=1; i<nums.length; i++){
            if(nums[i] < start){
                max = Math.max(max, cnt);
                start = nums[i];
                cnt = 1;
            } 
            else if(nums[i] > pre){
                cnt ++;
            }
            pre = nums[i];
            System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt);
        }
        return Math.max(max, cnt);
    }

Fix bug

Learn From others treemap

    public int lengthOfLIS(int[] nums) {


        TreeMap<Integer,Integer> map = new TreeMap<>();

        map.put(Integer.MIN_VALUE,0);

       for(int i: nums)
       {
           map.put(i,map.get(map.lowerKey(i))+1);
           while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) 
           {
            map.remove(map.higherKey(i));
           }
       }

       return map.get(map.lastKey());

    }

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

Example 1:

Input: nums = [1,3,5,4,7]
Output: 3
Explanation: The longest continuous increasing subsequence is [1,3,5] with length 3.
Even though [1,3,5,7] is an increasing subsequence, it is not continuous as elements 5 and 7 are separated by element
4.
Example 2:

Input: nums = [2,2,2,2,2]
Output: 1
Explanation: The longest continuous increasing subsequence is [2] with length 1. Note that it must be strictly
increasing.

Constraints:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
Original Page

Greedy Algorithm

    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int res = 1;
        int cnt = 1;
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(nums[i] > pre){
                cnt++;
            }else{
                res = Math.max(res, cnt);
                cnt = 1;
            }
            // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt);
            pre = nums[i];
        }
        return Math.max(res, cnt);
    }

Dynamic Programming

Different from the previous question, in this question we could only consider continuously increasing subsequences, which simplifies the process.

    public int findLengthOfLCIS(int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int res = 1;
        int[] dp = new int[nums.length];
        dp[0] = 1;

        for(int i=1; i<nums.length; i++){
            dp[i] = 1;
            if(nums[i] > nums[i-1]){
                dp[i] = dp[i-1] + 1;
                res = Math.max(res, dp[i]);
            }

        }
        // System.out.println(Arrays.toString(dp));
        return res;
    }

LeetCode Day 35 Dynamic Programming Part 9

Flame Chan — Thu, 18 Jul 2024 02:19:36 +0000

188. Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Constraints:

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000
Original Page

    public int maxProfit(int k, int[] prices) {
        /**[0][0] do nothing in day 0
           [0][1] own the stock for 1st time in day 0
           [0][2] not own the stock for 1st time in day 0
           [0][3] own the stock for 2nd time in day 0
           [0][4] not own the stock for 2nd time in day 0
           ....
           [0][k*2-1] own the stock for kth time in day 0
           [0][k*2] not own the stock for kth time in day 0

           [1][1] = max([0][1],[0][0]-prices[1])
           [1][2] = max([0][2],[0][1]+prices[1])
           [1][3] = max([0][3],[0][2]-prices[1])

           [i][j] if j is odd means we need to pay for the stock or keep the own status
                  if j is even means we can sell the stock or keep the non-stock status

        */    
        int[][] dp = new int[prices.length+1][k*2+1];
        for(int i=1; i<=k*2; i+=2){
            dp[0][i] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){
            for(int j=1; j<=k*2; j++){
                dp[i][j] = Math.max(
                    dp[i-1][j],
                    dp[i-1][j-1] + ((j % 2 == 0) ? 1 : -1) * prices[i]
                );
            }
        }
        return dp[prices.length-1][k*2];  
    }

309. Best Time to Buy and Sell Stock with Cooldown

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions:

After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:

Input: prices = [1]
Output: 0

Constraints:

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

    public int maxProfit(int[] prices) {

        /**
        [0] own the stock
        [1] colldown 
        [2] not own the stock 

         */

         int[][] dp = new int[prices.length][3];

         dp[0][0] = -prices[0];

         for(int i=1; i<prices.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]-prices[i]);
            dp[i][1] = dp[i-1][0] + prices[i];
            dp[i][2] = Math.max(dp[i-1][1], dp[i-1][2]);
         }

        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

         return Math.max(dp[prices.length-1][2],dp[prices.length-1][1]);

    }

Be careful, that when it is cooldown, we cannot buy a new stock.

in this regression relation, it shows dp[2] is the last one we update so that we can keep covering cooldown condition.

714. Best Time to Buy and Sell Stock with Transaction Fee

You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee.

Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction.

Note:

You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
The transaction fee is only charged once for each stock purchase and sale.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:

Buying at prices[0] = 1
Selling at prices[3] = 8
Buying at prices[4] = 4
Selling at prices[5] = 9 The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8. Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Constraints:

1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4
Original Page

the only thing we should consider is to add the transaction fee, but the fee will not change our previous logic

    public int maxProfit(int[] prices, int fee) {
        int[] dp = new int[2];
        int temp = 0;

        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            temp = dp[1];
            dp[1] = Math.max(dp[1], dp[0] + prices[i] -fee);
            dp[0] = Math.max(dp[0], temp-prices[i]);

        }

        return dp[1]; 
    }

LeetCode Day34 Dynamic Programming part8

Flame Chan — Tue, 16 Jul 2024 04:37:48 +0000

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
Original Page

Method 1, Greedy Algorithms

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        int profit = 0;
        int buy = prices[0];
        for(int i=1; i<prices.length; i++ ){
            if(buy>=prices[i]){
                buy = prices[i];
            }else{
                profit = Math.max(profit, prices[i]-buy);
            }
        }
        return profit;
    }

time O(n) space O(1)

Method 2 Dynamic Programming

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[][] dp = new int[prices.length][2];

        // if we want to own the stock we should pay for the specific price
        dp[0][0] = -prices[0];
        for(int i=1; i<dp.length; i++){
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[dp.length-1][1];
    }

time O(n) space O(n)
Dynamic Programming is more general than greedy algorithms because it will not only work for the specific problem.

Method 2.1 (improve the space complexity)

    public int maxProfit(int[] prices) {
        if(prices.length == 0){
            return 0;
        }

        // 2 means we have 2 different status (have owned stock or not )
        int[] dp = new int[2];

        // if we want to own the stock we should pay for the specific price
        dp[0] = -prices[0];
        for(int i=1; i<prices.length; i++){
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }
        // 
        return dp[1];
    }

Be careful here we should process dp[1] first because it will use the previous dp[0] instead of the updated dp[0].

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10……4
0 <= prices[i] <= 10……4

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[i][0] = Math.max(dp[i-1][1]-prices[i], dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i], dp[i-1][1]);
        }

        return dp[prices.length-1][1];
    }

The rolling array method

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }

        int[] dp = new int[2];
        dp[0] = -prices[0];

        for(int i=1; i<prices.length; i++){
            //only when we do not own the stack we can buy a new stock
            dp[1] = Math.max(dp[0]+prices[i], dp[1]);
            dp[0] = Math.max(dp[1]-prices[i], dp[0]);

        }

        return dp[1];
    }

123. Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

    public int maxProfit(int[] prices) {
        int transactions = 2;
        int[][] dp = new int[prices.length][transactions*2+1];
        for(int i=1; i<=transactions; i++){
            dp[0][i*2-1] = -prices[0];
        }

        for(int i=1; i<prices.length; i++){

            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1]+prices[i], dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2]-prices[i], dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3]+prices[i], dp[i-1][4]);
        }
        Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);

        return dp[prices.length-1][4];
    }

LeetCode Day33 Dynamic Programming

Flame Chan — Mon, 15 Jul 2024 11:49:21 +0000

198. House Robber

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400
Original Page

    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];
        dp[1] = nums[0];

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.max(dp[i-2]+nums[i-1], dp[i-1]);
        }
        // System.out.println(Arrays.toString(dp));
        return dp[dp.length-1];

    }

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000
Original Page

Wrong Code

    public int rob(int[] nums) {
        int[] dp = new int[nums.length+1];

        boolean findFirst = false;

        dp[1] = nums[0];

        if(nums.length>2){
            if(nums[0]+nums[2] > nums[1]){
                dp[2] = Math.max(dp[1], nums[1]);
                dp[3] = nums[0] + nums[2];
                findFirst = true;
            }else{
                dp[2] = Math.max(dp[1], nums[1]);
                dp[3] = dp[2];
            }
        }

        for(int i=4; i<dp.length; i++){
            if(i == dp.length-1){
                if(findFirst){
                    dp[i] = dp[i-1];
                    break;
                }
            }
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i-1]);
        }
        System.out.println(Arrays.toString(dp));
        return dp[dp.length-1];

in this case, we cannot cover the whole possibility.

    public int rob(int[] nums) {

        return Math.max(robber(nums, 0,nums.length-1), robber(nums,1,nums.length));


    }
    //dp[0] = 0 dp[1] = nums[1], dp[2] = max
    // begin 0, begin 1
        // [0,size-1] or [1, size]z
    public int robber(int[] nums, int beg, int end){
        int[] dp = new int[nums.length];
        if(beg == end){
            return nums[0];
        }
        dp[1] = nums[beg];

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[beg + i - 1]);
        }
        // System.out.println(Arrays.toString(dp));
        return dp[dp.length-1];
    }

LeetCode Day32 Dynamic Programming Part 5

Flame Chan — Fri, 12 Jul 2024 04:56:13 +0000

518. Coin Change II

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

The answer is guaranteed to fit into a signed 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:

Input: amount = 10, coins = [10]
Output: 1

Constraints:

1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000
Original Page

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length+1][amount+1];
        for(int i=0; i<=coins.length; i++){
            dp[i][0] = 1;
        }
        for(int i=1; i<= coins.length; i++){
            for(int j=1; j<=amount; j++){
                if(j<coins[i-1]){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
                }

            }
        }
                    // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[coins.length][amount];
    }

    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int i=0; i< coins.length; i++){
            for(int j=coins[i]; j<=amount; j++){
                dp[j] = dp[j] + dp[j-coins[i]];
            }
            System.out.println(Arrays.toString(dp));
        }
        return dp[amount];
    }

377. Combination Sum IV

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of nums are unique.
1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int i=1; i<=target; i++){
            for(int j=0; j<nums.length; j++){
                if(nums[j] <= i){
                    dp[i] = dp[i] + dp[i-nums[j]];
                }
            }
            // System.out.println(Arrays.toString(dp));
        }
        return dp[target];
    }

LeetCode Day31 Dynamic Programming Part 4

Flame Chan — Thu, 11 Jul 2024 10:22:51 +0000

494. Target Sum

You are given an integer array nums and an integer target.

You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.

For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
Original Page

Even though the backtracking is useful here we can use dynamic programming to solve this problem to achieve less time complexity.

    public int findTargetSumWays(int[] nums, int target) {
        /**
        sum(neg) + sum(pos) = sum(nums);
        sum(pos) - sum(neg) = target;
        sum(pos) = (sum(nums) + target) / 2 
         */
        int sum = Arrays.stream(nums).sum();
        // that means the sum of the positive number is invalid, because the nums do not conclude float
        if((sum+target)%2 != 0|| Math.abs(target) > sum){
            return 0;
        }

        // here we find the summary of the positive numbers
        int pos = (sum + target) >>1;

        // dp[i][j] array means for each index element `i` (nums[i]), if we want to reach the sum of the positive number `j`, we will have how many methods   
        int[][] dp = new int[nums.length+1][pos+1];

        // if we want to reach 0 we will have 1 ways that means we choose nothing and there is nothing.
        dp[0][0] = 1;

        // if(nums[0] <= pos){
        //     dp[0][nums[0]] = 1;
        // }

        for(int i = 1; i <= nums.length; i++){
            for(int j=0; j<=pos; j++){
                if(nums[i-1] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                }
            }
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[nums.length][pos];       

    }

Note

1, init the dp array is important especially here it is important to find out that the meaning of 0

LeetCode Day30 Dynamic Programming Part 3

Flame Chan — Wed, 10 Jul 2024 05:28:05 +0000

0-1 Bag Problem

Description of the topic

Ming is a scientist who needs to attend an important international scientific conference to present his latest research. He needs to bring some research materials with him, but he has limited space in his suitcase. These research materials include experimental equipment, literature, experimental samples, etc., each of which occupies a different space and has a different value.

Ming's luggage space is N. Ask Ming how he should choose to carry the research materials with the greatest value. Each research material can only be chosen once, and there are only two choices: choose or don't choose, and no cutting can be done.

Input Description
The first line contains two positive integers, the first integer M represents the type of research materials, and the second positive integer N represents Ming's luggage space.

The second line contains M positive integers representing the space occupied by each type of research material.

The third row contains M positive integers representing the value of each research material.

Output Description
Output an integer representing the maximum value of research materials that Ming can carry.

Input Example
6 1
2 2 3 1 5 2
2 3 1 5 4 3

Output example
5

Hints
Ming is able to carry 6 research materials, but the luggage space is only 1, and the research material that occupies 1 space is worth 5, so the final answer is output 5.

Data range:
1 <= N <= 5000
1 <= M <= 5000
The space occupied by the research materials and the value of the research materials are both less than or equal to 1000.

public class Main{
    public static void main (String[] args) {
    /* code */
    Scanner s = new Scanner(System.in);

        int M = s.nextInt();
        int N = s.nextInt();
        // clear buffer symbol /n
        s.nextLine();

    String w = s.nextLine();
    String v = s.nextLine();

    int[] weight = Arrays.stream(w.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();
    int[] value = Arrays.stream(v.split(" "))
                        .mapToInt(Integer::valueOf)
                        .toArray();

    int[][] dp = new int[M][N+1];


    for(int i=weight[0]; i<=N; i++){
        dp[0][i] = value[0];
    }

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

        }
    }

    System.out.println(dp[M-1][N]);
    }
}

1, the dp array means that we can obtain the maximum value for item i and target bag size j. The row indicates the item, and the column represents the size of the bag.

2, for init, we init the 1st row and 1st col( but actually we init the col by default 0, that mean )

3, the regression relation is that: for each item:
a, if the weight of the item is heavier than the bag's size, we cannot choose the item and the current size is the size of the collection of the previously chosen items.
b, if the weight of the item is ok, we have to compare the size of the collection of the previously chosen items minus the size of the current item (if we do not do it, the total size will be the size + the size of the current item, it will break the logic of our dp array).

Here, is the order of the double loop, because we can use a 2-D array to record all results and search for the current row from the previous row.

Also, we can use a 1-D array to realize it.

    for(int i=1; i<M; i++){
        for(int j=1; j<=N; j++){
            if(weight[i] > j){
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
            }

change to

        int[] dp = new int[target+1];

        for(int i=1; i<nums.length; i++){
            for(int j=target; j>=1; j--){
                if(nums[i] > j){
                    continue;
                }
                dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i]);    
            }
        }

416. Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100
Original Page

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2==1){
            return false;
        }
        int target = sum>>1;
        int[][] dp = new int[nums.length][target+1];

        for(int i=nums[0]; i<=target; i++){
            dp[0][i] = nums[0];
        }

        for(int i=1; i<nums.length; i++){
            for(int j=1; j<=target; j++){
                if(nums[i] > j){
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i]] + nums[i]);
                }     
            }
        }

        return dp[nums.length-1][target] == target;  
    }

LeetCode Day29 Dynamic Programming Part 2

Flame Chan — Tue, 09 Jul 2024 11:32:29 +0000

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28
Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

Right -> Down -> Down
Down -> Down -> Right
Down -> Right -> Down

Constraints:

1 <= m, n <= 100
Original Page

We can use this handwritten array simulation to explore the pattern (by the way, forgive my terrible handwriting).

    public int uniquePaths(int m, int n) {
        if(n<=1 || m<=1){
            return 1;
        }
        int dp[][] = new int[m+1][n+1];
        dp[0][1] = 1;
        for(int i=1; i<m+1; i++){
            for(int j=1; j<n+1; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];

    }

dp[0][1] = 1; for this code, actually it does not matter whether we use dp[1][0] = 1 or dp[0][1] = 1, because we want to match the index to m and n, we extend one more row and column when we init the array see: int dp[][] = new int[m+1][n+1];

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;

        int[][] dp = new int[row][col];

        boolean isBlocked = false;
        for(int i=0; i<row; i++){
            if(obstacleGrid[i][0]==1){
                isBlocked = true;
            }
                dp[i][0] = isBlocked ? 0 : 1;
        }

        isBlocked = false;
        for(int i=0; i<col; i++){

            if(obstacleGrid[0][i]==1){
                isBlocked = true;
            }
                dp[0][i] = isBlocked ? 0 : 1;
        }

        for(int i=1; i<row; i++){
            for(int j=1; j<col; j++){
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                }else{
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        // Arrays.stream(dp).map(Arrays::toString).forEach(System.out::println);
        return dp[row-1][col-1];  
    }

There is nothing especially hard to realize, we only need to consider the blocked thing but it is easy to think, which implies that when there is a blocked one, the grid that is left or down to the blocked one can not be reached through this direction. (the A grid's left grid is a blocked one, we can not from A's left moving to A, we can only find the up route, and this logic work for up as well)

343. Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.

Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints:

2 <= n <= 58
Original Page

    public int integerBreak(int n) {
        if(n<=2){
            return 1;
        }
        //init
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 1;
        //logic
        for(int i=3; i<=n; i++){
            for(int num=1; num<i; num++){
                dp[i] = Math.max(
                    Math.max(num * (i - num), dp[i]),
                    num * dp[i - num]);

            }
        }

        // Arrays.stream(dp).forEach(System.out::println);
        return dp[dp.length-1];
    }

LeetCode Day28 Dynamic Programming Part1

Flame Chan — Mon, 08 Jul 2024 10:24:25 +0000

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.
Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:

0 <= n <= 30
Original Page

Recursion Method

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

The Recursion Method is like DFS to go deep and then do the backtracking to get the final answer.
time: O(2^n)
space: O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }

we can use a global array to save the result to avoid re-recursion of the same elements. e.g. the figure below displays that f(17) and f(18) are two different recursion routes and if we use the normal recursion method we have to calculate them more than once.

time: O(n), space: O(n)

Dynamic Programming

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

The recursion works from top to bottom and then backtracking, the memory recursion will save the recursion results to avoid double calculation. Now the dynamic programming works from the bottom to the top and saves each step's result to the dp array.
time: O(n)
space: O(n)

Also we can dynamically update the limit num instead of an array. This will save space complexity, especially for a huge number of elements.

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1 step + 1 step
2 steps Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

1 step + 1 step
2 steps Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints:

1 <= n <= 45
Original Page

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        } 
        return dp[n];       
    }

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.

Pay 15 and climb two steps to reach the top. The total cost is 15. Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.

Pay 1 and climb two steps to reach index 2.
Pay 1 and climb two steps to reach index 4.
Pay 1 and climb two steps to reach index 6.
Pay 1 and climb one step to reach index 7.
Pay 1 and climb two steps to reach index 9.
Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

2 <= cost.length <= 1000
0 <= cost[i] <= 999
Original Page

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

Be Careful that we should the question has told us that we can start from index 0 and index 1, which implies if the number of stairs is less than 2, we will cost 0 because we can start at that point and the behaviour of start will cost 0, only the behaviour of move cost.

LeetCode Day27 Greedy Algorithms Part 5

Flame Chan — Sat, 06 Jul 2024 11:48:14 +0000

56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4
Original Page

    public int[][] merge(int[][] intervals) {
        if(intervals.length <= 1){
            return intervals;
        }
        Arrays.sort(intervals, (a,b)->{
            return Integer.compare(a[0], b[0]);
        });

        List<int[]> list = new ArrayList();
        for(int i=1; i<intervals.length; i++){
            if(intervals[i-1][1] >= intervals[i][0]){
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = Math.max(intervals[i-1][1], intervals[i][1]);

            } else{
                list.add(intervals[i-1]);
            }
        }
        list.add(intervals[intervals.length-1]);
        return list.toArray(new int[list.size()][]);
    }

738. Monotone Increasing Digits

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

Example 1:

Input: n = 10
Output: 9
Example 2:

Input: n = 1234
Output: 1234
Example 3:

Input: n = 332
Output: 299

Constraints:

0 <= n <= 10^9

    public int monotoneIncreasingDigits(int n) {
        if(n<10){
            return n;
        }
        String str = Integer.toString(n);
        char[] arr = new char[str.length()];
        arr[0] = str.charAt(0);

        int pos = -1;
        for(int i=1; i<str.length(); i++){
            char num = str.charAt(i);
            if(num < arr[i-1]){
                int j;
                if(pos == -1){
                    j = 0;
                }else{
                    j = pos;
                }
                for(;j<arr.length; j++){
                    if(j==0||j==pos){
                        arr[j] = (char) (arr[j]-1);
                    }else{
                        arr[j] = '9';
                    }
                }
                break;
            }
            else if(num > arr[i-1]){
                pos = i;
            }
            arr[i] = str.charAt(i);
        }
        if(arr[0] <=0){
            // cost space by using String
            str = new String(arr, 1,arr.length);
        }else{
            str = new String(arr);
        }
        return Integer.valueOf(str);
    }

LeetCode Day26 Greedy Algorithms Part 4

Flame Chan — Fri, 05 Jul 2024 13:15:40 +0000

452. Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:

Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12]. Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:

Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 105
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1
Original Page

    public int findMinArrowShots(int[][] points) {
        if(points.length == 0){
            return 0;
        }

        Arrays.sort(points, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        int arrow = 1;
        int start = points[0][0];
        int end = points[0][1];

        for(int i=0; i<points.length; i++){

            if((points[i][0] >= start && points[i][0]<= end) ||
            (end >=points[i][0] && end <= points[i][1])){

//Narrow the arrow point down 

                if(points[i][0] > start && points[i][0] <= end){
                    start = points[i][0];
                }
                if(points[i][1]>start && points[i][1] < end){
                    end = points[i][1];
                }
                continue;
            }else{

// current arrow point is not satisfied with balloons 

                start = points[i][0];
                end = points[i][1];
                arrow ++;   
            }
        }
        return arrow; 
    }

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.
Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 10^5
intervals[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4
Original Page

Wrong Code

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            if(a[0] == b[0]){
                return a[1] - b[1];
            }
            return a[0] - b[0];
        });

        Arrays.stream(intervals)
                .map(Arrays::toString)
                .forEach(System.out::println);

        int count = 0;

        // List<int[]> list = new LinkedList<>();
        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            //if the left edge is not included in the previous interval the right will definitely not be in it.
            if(intervals[i][0] >=start && intervals[i][0] <end){
                count++;
                continue;
            }
            start = intervals[i][0];
            end = intervals[i][1];
            // list.add(intervals[i]);
        }
        return count;
    }

Fix it

    public int eraseOverlapIntervals(int[][] intervals) {
        if(intervals.length == 0){
            return 0;
        }

        Arrays.sort(intervals, (a,b) ->{
            return a[0] - b[0];
        });

        int count = 0;

        int start = intervals[0][0];
        int end = intervals[0][1];

        for(int i=1; i<intervals.length; i++){
            if(intervals[i][0] < intervals[i-1][1]){
                count++;
                // here we need to find the maximum overlap, the means whether the next element  overlap to above groups of overlaps 
                // if only find overlap from the previous interval, it may cause miss calculation over-add 1 count
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);  
            }
        }
        return count;
    }

763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.
Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

1 <= s.length <= 500
s consists of lowercase English letters.
Original Page

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);
                int j = s.length()-1;
                for(;j>i;j--){
                    if(s.charAt(j) == target){
                        break;
                    }
                }
                end = Math.max(end, j);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        Set<Character> set = new HashSet<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            if(!set.contains(target)){
                set.add(target);

                end = Math.max(end, pos[target-'a']);
            }
            if(i == end){
                list.add(end-start+1);
                start = i+1;
                set.clear();
            } 
        }
        return list;
    }

    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();

        int[] pos = new int[27];

        for(int i=s.length()-1; i>0;i--){
            if(pos[s.charAt(i)-'a'] == 0){
                pos[s.charAt(i)-'a'] = i;
            }
        }

        if(s.length() == 0){
            return list;
        }

        int start = 0;
        int end = 0;
        for(int i=0; i<s.length(); i++){
            Character target = s.charAt(i);

            end = Math.max(end, pos[target-'a']);

            if(i == end){
                list.add(end-start+1);
                start = i+1;
            } 
        }
        return list;
    }

Because it is not important for evaluating whether the element has been in the set, we only focus on whether the end is reached or not, and if the same elements happen, the end will not change and if the different elements merge, it seems like end may change but all of them will not impact the if evaluation so we can remove them.