Merge Two Sorted Arrays Without Extra Space in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted arrays without extra space

What is the output of the following C++ code that merges two sorted arrays without using extra space?

DSA C++

void merge(int arr1[], int arr2[], int n, int m) {
    int i = n - 1, j = 0;
    while (i >= 0 && j < m) {
        if (arr1[i] > arr2[j]) {
            std::swap(arr1[i], arr2[j]);
            i--;
            j++;
        } else {
            break;
        }
    }
    std::sort(arr1, arr1 + n);
    std::sort(arr2, arr2 + m);
}

int main() {
    int arr1[] = {1, 5, 9, 10, 15, 20};
    int arr2[] = {2, 3, 8, 13};
    int n = 6, m = 4;
    merge(arr1, arr2, n, m);
    for (int i = 0; i < n; i++) std::cout << arr1[i] << " ";
    std::cout << "| ";
    for (int i = 0; i < m; i++) std::cout << arr2[i] << " ";
    return 0;
}

A 1 3 5 8 9 10 | 2 13 15 20

B 1 2 3 5 8 9 | 10 13 15 20

C 1 2 3 5 8 10 | 9 13 15 20

D 1 2 3 5 9 10 | 8 13 15 20

💡 Hint

Focus on how the elements are swapped and then both arrays are sorted separately.

The code swaps elements from the end of the first array with the start of the second array if the first array's element is greater. After swapping, both arrays are sorted individually, resulting in the merged sorted arrays without extra space.

❓ Predict Output

intermediate

Resulting arrays after merging with gap method

What will be the content of the two arrays after applying the gap method to merge them without extra space?

DSA C++

void merge(int arr1[], int arr2[], int n, int m) {
    int gap = (n + m + 1) / 2;
    while (gap > 0) {
        int i = 0, j = gap;
        while (j < n + m) {
            int a = (i < n) ? arr1[i] : arr2[i - n];
            int b = (j < n) ? arr1[j] : arr2[j - n];
            if (a > b) {
                if (i < n && j < n) std::swap(arr1[i], arr1[j]);
                else if (i < n && j >= n) std::swap(arr1[i], arr2[j - n]);
                else std::swap(arr2[i - n], arr2[j - n]);
            }
            i++;
            j++;
        }
        if (gap == 1) gap = 0;
        else gap = (gap + 1) / 2;
    }
}

int main() {
    int arr1[] = {10, 27, 38, 43};
    int arr2[] = {3, 9, 82, 10, 15};
    int n = 4, m = 5;
    merge(arr1, arr2, n, m);
    for (int i = 0; i < n; i++) std::cout << arr1[i] << " ";
    std::cout << "| ";
    for (int i = 0; i < m; i++) std::cout << arr2[i] << " ";
    return 0;
}

A 3 9 10 10 | 15 27 38 43 82

B 3 9 10 15 | 10 27 38 43 82

C 3 9 10 27 | 10 15 38 43 82

D 3 9 15 27 | 10 10 38 43 82

💡 Hint

Remember the gap reduces each iteration and elements are swapped if out of order.

The gap method compares elements at a distance 'gap' and swaps if needed, reducing the gap until zero. This results in both arrays merged in sorted order without extra space.

🔧 Debug

advanced

Identify the error in this merge function

What error will this code produce when merging two sorted arrays without extra space?

DSA C++

void merge(int arr1[], int arr2[], int n, int m) {
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (arr1[i] > arr2[j]) {
            std::swap(arr1[i], arr2[j]);
            i++;
            j++;
        } else {
            i++;
        }
    }
    std::sort(arr1, arr1 + n);
    std::sort(arr2, arr2 + m);
}

int main() {
    int arr1[] = {1, 4, 7, 8, 10};
    int arr2[] = {2, 3, 9};
    int n = 5, m = 3;
    merge(arr1, arr2, n, m);
    for (int i = 0; i < n; i++) std::cout << arr1[i] << " ";
    std::cout << "| ";
    for (int i = 0; i < m; i++) std::cout << arr2[i] << " ";
    return 0;
}

A Runtime error due to out-of-bounds access in the while loop.

B Compilation error due to missing header for std::swap.

C The code runs but does not correctly merge arrays; some elements remain unsorted.

D The code runs and merges arrays correctly without errors.

💡 Hint

Check how the indices i and j are incremented inside the loop.

The code increments both i and j only when a swap happens, but if arr1[i] <= arr2[j], only i is incremented. This causes j to stay at 0, potentially missing elements in arr2, so the merge is incomplete.

🧠 Conceptual

advanced

Why is extra space not needed in some merge algorithms?

Why can two sorted arrays be merged without extra space using the gap method or swapping approach?

A Because the arrays are stored contiguously in memory, merging can be done in place.

B Because the arrays are small, extra space is not necessary for merging.

C Because the arrays contain only integers, which are easy to swap.

D Because the arrays are sorted, we can rearrange elements by swapping and sorting parts without needing extra memory.

💡 Hint

Think about how sorting and swapping help avoid extra memory.

The key is that the arrays are sorted, so by swapping out-of-place elements and then sorting each array, the merge can be done without extra space.

❓ Predict Output

expert

Final arrays after complex merge without extra space

Given the following arrays and merge code, what is the final printed output?

DSA C++

void merge(int arr1[], int arr2[], int n, int m) {
    int gap = n + m;
    for (gap = (gap + 1) / 2; gap > 0; gap = (gap == 1) ? 0 : (gap + 1) / 2) {
        int i = 0, j = gap;
        while (j < n + m) {
            int a = (i < n) ? arr1[i] : arr2[i - n];
            int b = (j < n) ? arr1[j] : arr2[j - n];
            if (a > b) {
                if (i < n && j < n) std::swap(arr1[i], arr1[j]);
                else if (i < n && j >= n) std::swap(arr1[i], arr2[j - n]);
                else std::swap(arr2[i - n], arr2[j - n]);
            }
            i++;
            j++;
        }
    }
}

int main() {
    int arr1[] = {1, 4, 7, 8, 10};
    int arr2[] = {2, 3, 9, 15, 16, 20};
    int n = 5, m = 6;
    merge(arr1, arr2, n, m);
    for (int i = 0; i < n; i++) std::cout << arr1[i] << " ";
    std::cout << "| ";
    for (int i = 0; i < m; i++) std::cout << arr2[i] << " ";
    return 0;
}

A 1 2 3 4 7 | 8 9 10 15 16 20

B 1 2 3 4 7 | 8 9 15 16 20 10

C 1 2 3 4 8 | 7 9 10 15 16 20

D 1 3 4 7 8 | 2 9 10 15 16 20

💡 Hint

Trace the gap reduction and swapping carefully for all elements.

The gap method reduces gap size each iteration, swapping out-of-order elements across both arrays. The final arrays are fully sorted and merged without extra space.

Practice

1. What is the main goal when merging two sorted arrays without extra space?

easy

A. Copy elements from one array to another without sorting

B. Sort each array separately using extra space

C. Create a new array to hold merged elements

D. Combine both arrays into one sorted array without using extra memory

Solution

1. Step 1: Understand the problem requirement

   The problem asks to merge two sorted arrays into a single sorted sequence without using extra space, meaning no additional arrays or large buffers.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays to maintain sorted order combined, without allocating new memory.

3. Final Answer:

   Combine both arrays into one sorted array without using extra memory -> Option D

4. Quick Check:

   Merge without extra space = Combine in-place [OK]

Hint: Think in-place rearrangement, no new arrays needed [OK]

Common Mistakes:

• Assuming extra space is allowed
• Trying to merge by creating a new array
• Sorting arrays separately without merging

2. Which of the following C++ code snippets correctly swaps two elements without using extra space?

easy

A. a = a + b; b = a - b; a = a - b;

B. temp = a; a = b; b = temp;

C. a = b; b = a;

D. a = a * b; b = a / b; a = a / b;

Solution

1. Step 1: Analyze swapping without extra variable

   a = a + b; b = a - b; a = a - b; uses arithmetic operations to swap values without a temporary variable.

2. Step 2: Check correctness of each option

   temp = a; a = b; b = temp; uses a temporary variable, so it uses extra space. a = b; b = a; assigns a to b and then b to a, which loses original value. a = a * b; b = a / b; a = a / b; uses multiplication/division which can cause overflow or errors if b is zero.

3. Final Answer:

   a = a + b; b = a - b; a = a - b; -> Option A

4. Quick Check:

   Swap without temp = arithmetic trick [OK]

Hint: Use arithmetic swap to avoid extra variable [OK]

Common Mistakes:

• Using a temporary variable (extra space)
• Overwriting values without saving
• Using multiplication/division causing errors

3. What will be the content of arrays arr1 and arr2 after merging without extra space using the gap method?

arr1 = {1, 5, 9, 10}
arr2 = {2, 3, 8, 13}

medium

A. arr1 = {1, 2, 3, 5}, arr2 = {8, 9, 10, 13}

B. arr1 = {1, 3, 5, 8}, arr2 = {2, 9, 10, 13}

C. arr1 = {1, 2, 5, 8}, arr2 = {3, 9, 10, 13}

D. arr1 = {1, 2, 3, 8}, arr2 = {5, 9, 10, 13}

Solution

1. Step 1: Apply gap method to merge arrays

   Start with gap = ceil((4+4)/2) = 4. Compare elements at gap distance and swap if needed, then reduce gap until 0.

2. Step 2: Final sorted arrays after gap method

   After applying the method, arr1 becomes {1, 2, 3, 5} and arr2 becomes {8, 9, 10, 13}.

3. Final Answer:

   arr1 = {1, 2, 3, 5}, arr2 = {8, 9, 10, 13} -> Option A

4. Quick Check:

   Gap method merges arrays in-place correctly [OK]

Hint: Use gap method: reduce gap, swap if needed [OK]

Common Mistakes:

• Not reducing gap properly
• Swapping wrong elements
• Confusing array indices across two arrays

4. Identify the error in the following code snippet that attempts to merge two sorted arrays without extra space:

for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    swap(arr1[i], arr2[0]);
    sort(arr2, arr2 + m);
  }
}

medium

A. Swapping elements without checking bounds causes runtime error

B. Loop should run till m instead of n

C. Sorting arr2 inside the loop causes high time complexity

D. No error, code is optimal

Solution

1. Step 1: Analyze the loop and sorting inside it

   The code sorts arr2 inside the loop for every swap, which is inefficient and increases time complexity to O(n*m*log m).

2. Step 2: Identify the performance issue

   Sorting arr2 repeatedly is costly; better methods avoid sorting inside the loop.

3. Final Answer:

   Sorting arr2 inside the loop causes high time complexity -> Option C

4. Quick Check:

   Sorting inside loop = inefficient [OK]

Hint: Avoid sorting inside loops for better performance [OK]

Common Mistakes:

• Ignoring time complexity impact
• Assuming swap causes runtime error
• Confusing loop bounds

5. Given two sorted arrays arr1 = {10, 12, 15, 18} and arr2 = {2, 5, 20, 25}, how can you merge them without extra space so that after merging, arr1 contains the first four smallest elements and arr2 contains the remaining elements sorted?

hard

A. Swap elements only if arr1[i] is greater than arr2[j] without sorting arr2

B. Use the gap method to compare and swap elements across arrays until fully merged

C. Sort both arrays separately and then concatenate

D. Copy all elements to a new array, sort it, then copy back

Solution

1. Step 1: Understand the gap method for merging

   The gap method reduces the gap between compared elements and swaps if needed, working across both arrays without extra space.

2. Step 2: Apply gap method to given arrays

   By repeatedly comparing and swapping elements at the gap distance, arr1 will hold the smallest elements and arr2 the larger ones, both sorted.

3. Final Answer:

   Use the gap method to compare and swap elements across arrays until fully merged -> Option B

4. Quick Check:

   Gap method merges sorted arrays in-place [OK]

Hint: Use gap method for in-place merge without extra space [OK]

Common Mistakes:

• Using extra arrays violating constraints
• Sorting arrays separately without merging
• Swapping without sorting arr2 leads to wrong order