Merge Arrays II - C++ Solution

1. Introduction

"Merging Arrays II" is an interesting variant of array merging problems. It involves merging two sorted arrays when one array, X[], has vacant cells (represented by 0s) and is large enough to hold all elements from the second array, Y[]. The challenge lies in merging them into X[] while maintaining sorted order and utilizing vacant cells.

Problem

Given two sorted integer arrays X[] and Y[], where X[] has a size m (including n vacant cells represented by 0s) and Y[] has a size n, merge Y[] into X[] in a sorted manner. The resulting array X[] should contain all elements from both arrays, sorted in ascending order.

2. Solution Steps

1. Move all non-zero elements of X[] to the end of the array.

2. Use two pointers: one for the non-zero elements of X[] and one for Y[].

3. Compare elements from the end of the non-zero section of X[] and from Y[].

4. Place the larger element at the end of X[] and move the pointers accordingly.

5. Continue this process until all elements from Y[] are merged into X[].

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to merge Y[] into X[]
void merge(int X[], int Y[], int m, int n) {
    // Move non-zero elements of X[] to the end
    int k = m - 1;
    for (int i = m - 1; i >= 0; i--) {
        if (X[i] != 0) {
            X[k--] = X[i];
        }
    }

    // Merge elements of Y[] and X[]
    int i = n; // Index of the non-zero start of X[]
    int j = 0; // Index of Y[]
    k = 0; // Index for the resultant X[]

    // Merge until Y[] is exhausted
    while (j < n) {
        if (i < m && X[i] <= Y[j]) {
            X[k++] = X[i++];
        } else {
            X[k++] = Y[j++];
        }
    }
}

int main() {
    int X[] = {0, 2, 0, 3, 0, 5, 6, 0, 0};
    int Y[] = {1, 8, 9, 10, 15};
    int m = sizeof(X) / sizeof(X[0]);
    int n = sizeof(Y) / sizeof(Y[0]);

    merge(X, Y, m, n);

    // Print merged array
    for (int i = 0; i < m; i++) {
        cout << X[i] << " ";
    }
    cout << endl;

    return 0;
}

Output:

1 2 3 5 6 8 9 10 15

Explanation:

The program starts by moving all non-zero elements of X[] to its end. This creates space at the beginning of X[] to merge elements from Y[]. 

Using two pointers, it compares elements from Y[] and the non-zero section of X[], placing the smaller of the two elements into the correct position in X[]. 

This process continues until all elements of Y[] are merged into X[], resulting in a sorted merged array. 

The approach efficiently utilizes the available space in X[] and merges the arrays in place.