Algorithm: Leetcode Contest 398

3152. Special Array II

solution

solution 1 - my solution - not passed

using DP, not passed due to Memory Limit Exceeded.

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        boolean[] ans = new boolean[queries.length];
        
        boolean[][] dp = new boolean[nums.length][nums.length];
        
        dp[0][0] = true;
        
        // fill diagonal line
        for(int i = 0; i < dp[0].length; i++) {
            dp[i][i] = true;
        }
        
        // fill normal position
        for(int row = 0; row < dp.length; row++) {
            for(int col = row + 1; col < dp[0].length; col++) {
                dp[row][col] = dp[row][col - 1] && (nums[col] % 2 != nums[col - 1] % 2);
            }
        }
        
        for(int i = 0; i < ans.length; i++) {
            ans[i] = dp[queries[i][0]][queries[i][1]];
        }
        
        return ans;
    }
}

solution 2: Accumulate Array

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        boolean[] res = new boolean[queries.length];
        int[] acc = new int[nums.length];
        for(int i = 1; i < nums.length; i++) {
            acc[i] = acc[i - 1] + (nums[i] % 2 == nums[i - 1] % 2 ? 1 : 0);
        }

        for(int i = 0; i < queries.length; i++) {
            res[i] = acc[queries[i][1]] - acc[queries[i][0]] == 0;
            
        }

        return res;
    }
}

Retro

when it comes to an array, always think if it’s possible to resolve it through accumulative array…

Actually there is a signal when I wrote DP solution, the position dependency is only 1 axis, instead of 2, I should figure out this is an 1d DP, or just accumulative array solution.