Find the integer added to array ii

Array Two Pointers Sorting Enumeration

32.8% acceptance

Feb 23, 2026

178

You are given two integer arrays nums1 and nums2. From nums1 two elements have been removed, and all other elements have been increased (or decreased in the case of negative) by an integer, represented by the variable x. As a result, nums1 becomes equal to nums2. Two arrays are considered equal when they contain the same integers with the same frequencies. Return the minimum possible integer x that achieves this equivalence.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_added_integer(mut nums1: Vec<i32>, mut nums2: Vec<i32>) -> i32 {
    nums1.sort_unstable();
    nums2.sort_unstable();

    let check = |x: i32| -> bool {
      // Check if nums1 with x added (and at most 2 removed) matches nums2
      let mut skipped = 0;
      let mut j = 0;
      for i in 0..nums1.len() {
        if j < nums2.len() && nums1[i] + x == nums2[j] {
          j += 1;
        } else {
          skipped += 1;
          if skipped > 2 {
            return false;
          }
        }
      }
      j == nums2.len()
    };

    // The minimum element of nums2 must equal nums1[k] + x for some k in {0, 1, 2}
    // (we can remove at most 2 elements from nums1)
    // x = nums2[0] - nums1[k] for k in 0..=2
    let candidates: Vec<i32> = (0..=2).map(|k| nums2[0] - nums1[k]).collect();
    let mut result = i32::MIN;
    for &x in &candidates {
      if check(x) {
        if result == i32::MIN || x < result {
          result = x;
        }
      }
    }
    result
  }
}