Skip to content

3132. Find the Integer Added to Array II 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
    // After removing two elements from nums1, either nums1[0], nums1[1], or
    // nums1[2] will persist. Therefore, the difference between nums1 (with two
    // elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    // 0 <= i <= 2.
    int ans = INT_MAX;

    ranges::sort(nums1);
    ranges::sort(nums2);

    for (int i = 0; i < 3; ++i) {
      const int inc = nums2[0] - nums1[i];
      if (isValidDiff(nums1, nums2, inc))
        ans = min(ans, inc);
    }

    return ans;
  }

 private:
  // Returns true if it's possible to increase nums1 (with two elements removed)
  // by `inc` to nums2.
  bool isValidDiff(const vector<int>& nums1, const vector<int>& nums2,
                   int inc) {
    int removed = 0;
    int i = 0;  // nums2's index

    for (const int num : nums1)
      if (num + inc == nums2[i]) {
        if (++i == nums2.size())
          break;
      } else {
        ++removed;
      }

    return removed <= 2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public int minimumAddedInteger(int[] nums1, int[] nums2) {
    // After removing two elements from nums1, either nums1[0], nums1[1], or
    // nums1[2] will persist. Therefore, the difference between nums1 (with two
    // elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    // 0 <= i <= 2.
    int ans = Integer.MAX_VALUE;

    Arrays.sort(nums1);
    Arrays.sort(nums2);

    for (int i = 0; i < 3; ++i) {
      final int inc = nums2[0] - nums1[i];
      if (isValidDiff(nums1, nums2, inc))
        ans = Math.min(ans, inc);
    }

    return ans;
  }

  // Returns true if it's possible to increase nums1 (with two elements removed)
  // by `inc` to nums2.
  private boolean isValidDiff(int[] nums1, int[] nums2, int inc) {
    int removed = 0;
    int i = 0; // nums2's index

    for (final int num : nums1)
      if (num + inc == nums2[i]) {
        if (++i == nums2.length)
          break;
      } else {
        ++removed;
      }

    return removed <= 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def minimumAddedInteger(self, nums1: list[int], nums2: list[int]) -> int:
    # After removing two elements from nums1, either nums1[0], nums1[1], or
    # nums1[2] will persist. Therefore, the difference between nums1 (with two
    # elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    # 0 <= i <= 2.
    ans = math.inf

    nums1.sort()
    nums2.sort()

    for i in range(3):
      inc = nums2[0] - nums1[i]
      if self._isValidDiff(nums1, nums2, inc):
        ans = min(ans, inc)

    return ans

  def _isValidDiff(self, nums1: list[int], nums2: list[int], inc: int) -> bool:
    """
    Returns True if it's possible to increase nums1 (with two elements removed)
    by `inc` to nums2.
    """
    removed = 0
    i = 0  # nums2's index

    for num in nums1:
      if num + inc == nums2[i]:
        i += 1
        if i == len(nums2):
          break
      else:
        removed += 1

    return removed <= 2