Algorithm: Leetcode Contest 395

3132. Find the Integer Added to Array II

Solution

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int x = 0, min = Integer.MAX_VALUE;
        
        for(int num : nums1) {
            x = nums2[0] - num;
            if (isValid(nums1, nums2, x)) {
                min = Math.min(min, x);
            }
        }

        return min;
    }
    
    private boolean isValid(int[] nums1, int[] nums2, int x) {
        int count = 0;
        int nums2Index = 0;
        for(int i = 0; i < nums1.length && nums2Index < nums2.length; i++) {
            if (nums1[i] + x != nums2[nums2Index]) {
                count++;
            } else {
                nums2Index++;
            }
        }

        return count <= 2;
    }

    
}

Retro

totally don’t know how to solve this problem at first place.

was thinking using DFS to resolve the issue while find the factor is too many to consider.

the core or essential part of solution is isValid.

it uses an aggregator way to determine if the x is valid, which is totally missed in my mind.