Find the Integer Added to Array II - Practice Coding Problems

Find the Integer Added to Array II - Problem

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) by an integer 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.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [4,6,4,1,2], nums2 = [5,3,1]

› Output: -1

💡 Note: Remove elements 4 and 2 from nums1 to get [6,4,1]. Then add x = -1 to each element: [6-1, 4-1, 1-1] = [5,3,0]. Wait, let me recalculate. Remove 4 and 6: [4,1,2]. Add x=1: [5,2,3]. Actually, remove the first 4 and the 2: [6,4,1]. Add x=-1: [5,3,0]. Let me try remove 6 and 2: [4,4,1]. This needs to match [5,3,1], so x=1 gives [5,5,2]. Remove 4 and 1: [4,6,2], add x=-1 gives [3,5,1]. Remove elements at indices that make [6,4,1] → add x=-1 → [5,3,0]. Actually remove elements 4,6 to get remaining [4,1,2] which with x=1 becomes [5,2,3]. The answer should be calculated by trying different removal combinations.

Example 2 — Remove Different Elements

$ Input: nums1 = [3,5,1,3], nums2 = [2,4]

› Output: -1

💡 Note: Remove 2 elements from [3,5,1,3] to get an array of size 2. Remove 3 and 1: remaining [5,3], add x=-1: [4,2]. Sort both: [2,4] = [2,4] ✓

Example 3 — Minimum Removal

$ Input: nums1 = [1,2], nums2 = []

› Output: 0

💡 Note: Remove both elements from nums1 to get empty array, which matches empty nums2. No transformation needed, so x = 0

Constraints

3 ≤ nums1.length ≤ 200
nums1.length - 2 = nums2.length
-1000 ≤ nums1[i], nums2[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

nums1 = [4,6,4,1,2], nums2 = [5,3,1] (target)

Process

Remove 2 elements from nums1, then add x to each remaining element

Output

Find minimum x that makes transformation work

Key Takeaway

🎯 Key Insight: After sorting, we only need to check 3 strategic removal patterns instead of all possible combinations

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that after sorting both arrays, we only need to try three strategic removal combinations: removing the first two elements, the first and last elements, or the last two elements from nums1. This reduces the problem from O(n³) brute force to O(n log n) optimal solution. Best approach is Three-Case Enumeration. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort First Optimization	O(n log n)	O(1)	Sort both arrays first, then try removing elements systematically from the beginning
Brute Force - Try All Combinations	O(n³)	O(n)	Try removing every possible pair of elements and check all possible values of x
Three-Case Enumeration	O(n log n)	O(1)	Enumerate only three possible cases: remove (smallest, 2nd smallest), (smallest, largest), or (2nd smallest, largest)

Sort First Optimization — Algorithm Steps

Step 1: Sort both nums1 and nums2 arrays
Step 2: Try removing 0, 1, or 2 elements from start of sorted nums1
Step 3: Calculate x and verify if transformation works

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Sort both input arrays to enable systematic comparison

Try Removals

Remove 0, 1, or 2 elements from start of sorted nums1

Check Match

Calculate x and verify if transformation creates nums2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    qsort(nums1, nums1Size, sizeof(int), compare);
    qsort(nums2, nums2Size, sizeof(int), compare);
    
    int minX = INT_MAX;
    
    // Try removing 0, 1, or 2 elements from start of nums1
    for (int removeCount = 0; removeCount <= 2; removeCount++) {
        if (nums1Size - removeCount == nums2Size) {
            if (removeCount < nums1Size) {
                int x = nums2[0] - nums1[removeCount];
                // Check if all elements match after transformation
                int valid = 1;
                for (int i = 0; i < nums2Size; i++) {
                    if (nums1[removeCount + i] + x != nums2[i]) {
                        valid = 0;
                        break;
                    }
                }
                if (valid && x < minX) {
                    minX = x;
                }
            }
        }
    }
    
    return minX == INT_MAX ? 0 : minX;
}

int main() {
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0;
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing for [1,2,3] format
    char* p = strchr(line, '[');
    if (p) {
        p++;
        char* token = strtok(p, ",]");
        while (token && nums1Size < 1000) {
            nums1[nums1Size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    fgets(line, sizeof(line), stdin);
    p = strchr(line, '[');
    if (p) {
        p++;
        char* token = strtok(p, ",]");
        while (token && nums2Size < 1000) {
            nums2[nums2Size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(nums1, nums1Size, nums2, nums2Size);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting both arrays takes O(n log n), checking 3 cases takes O(n) each

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables (sorting is in-place)

✓ Linear Space

8.4K Views

Medium Frequency

~18 min Avg. Time

156 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort First Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler