Algorithm: Leetcode Contest 403

3195. Find the Minimum Area to Cover All Ones I

Solution

class Solution {
    public int minimumArea(int[][] grid) {
        // find the margin 1s
        
        int left = -1, right = -1, top = -1, bottom = -1;
        
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    if (left == -1 || left > j) {
                        left = j;
                    } 
                    if (right == -1 || right < j) {
                        right = j;
                    } 
                    if (top == -1 || top < i) {
                        top = i;
                    }
                    if (bottom == -1 || bottom > i) {
                        bottom = i;
                    }
                }
            }
        }
        
        return (right - left + 1) * (top - bottom + 1);
    }
}

3196. Maximize Total Cost of Alternating Subarrays

cannot solve this problem by myself, the solution with the most vote mentioned this is a masked house robbery algorithm,

so I want to solve house robbery algorithm first

Sub Problem: house robbery

198. House Robber

the solution with most vote is excellent…

Solution 1: Recursive: my solution

class Solution {
    public int rob(int[] nums) {
        return dfs(0, 0, true, nums);
    }

    private int dfs(int index, int curSum, boolean canTake, int[] nums) {
        if (index == nums.length) {
            return curSum;
        }

        // not take cur
        int noTake = dfs(index + 1, curSum, true, nums);

        // takecur
        int take = 0;
        if (canTake) {
            take = dfs(index + 1, curSum + nums[index], false, nums);
        }

        return Math.max(noTake, take);
    }
}

Solution2: Recursive - top down

rob(n) = Math.max(rob(n - 2) + num[cur], rob(n - 1))

class Solution {
    public int rob(int[] nums) {
        int max = 0;
        for(int i = 0; i < nums.length; i++) {
            max = Math.max(rob(i, nums), max);
        }
        return max;
    }

    private int rob(int i, int[] nums) {
        if (i < 0) {
            return 0;
        }

        return Math.max(rob(i - 1, nums), rob(i - 2, nums) + nums[i]);
    }
}

Solution3: Iterative - Memo

class Solution {
    public int rob(int[] nums) {
        int[] memo = new int[nums.length + 1];
        memo[1] = nums[0];
        int max = memo[1];
        for(int i = 1; i < nums.length; i++) {
            memo[i + 1] = Math.max(memo[i], memo[i - 1] + nums[i]);
            max = Math.max(max, memo[i + 1]);
        }

        return max;
    }
}