The “Merge Sorted Array” problem is a key exercise that evaluates your ability to manipulate and merge sorted arrays. Frequently asked in technical interviews, particularly at top tech companies, this problem demonstrates your efficiency in handling sorted data.

Problem Statement

Given two sorted integer arrays, A and B, your task is to merge B into A as one sorted array. Assume that A has sufficient space (size = m + n) to accommodate all elements from B. Here, m is the number of initialized elements in A, and n is the number of elements in B.

Example:

• Input:
• A = [1, 2, 3, 0, 0, 0] (m = 3)
• B = [2, 5, 6] (n = 3)
• Output:
• A = [1, 2, 2, 3, 5, 6]

Java Solution

public class MergeSortedArray {

    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1; // Pointer for the last initialized element in A
        int j = n - 1; // Pointer for the last element in B
        int k = m + n - 1; // Pointer for the last position of the merged array

        // Merge in reverse order
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[k--] = A[i--];
            } else {
                A[k--] = B[j--];
            }
        }

        // Copy remaining elements from B
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }

    public static void main(String[] args) {
        MergeSortedArray solution = new MergeSortedArray();
        int[] A = {1, 2, 3, 0, 0, 0}; // m = 3
        int[] B = {2, 5, 6};           // n = 3
        solution.merge(A, 3, B, 3);

        System.out.print("Merged array: ");
        for (int num : A) {
            System.out.print(num + " "); // Output: 1 2 2 3 5 6
        }
    }
}

Code Breakdown

1. Class Declaration

   public class MergeSortedArray {

This line declares a public class named MergeSortedArray.

2. Merge Method

   public void merge(int[] A, int m, int[] B, int n) {

This method merges the contents of B into A. The method takes two arrays and their respective sizes as parameters.

3. Pointer Initialization

   int i = m - 1; // Pointer for last initialized element in A
   int j = n - 1; // Pointer for last element in B
   int k = m + n - 1; // Pointer for last position of merged array

Three pointers are initialized: i points to the last initialized element in A, j points to the last element in B, and k points to the last position in the merged array.

4. Reverse Merging

   while (i >= 0 && j >= 0) {
       if (A[i] > B[j]) {
           A[k--] = A[i--];
       } else {
           A[k--] = B[j--];
       }
   }

This loop merges the arrays by comparing elements from the end. The larger of the two elements (A[i] or B[j]) is placed at the end of A, and the respective pointer is decremented.

5. Copy Remaining Elements

   while (j >= 0) {
       A[k--] = B[j--];
   }

If there are any remaining elements in B after the main merging loop, they are copied into A. Since A already contains the initialized elements, any remaining elements from B will fill in from the start.

Time and Space Complexity

• Time Complexity: (O(m + n))
  The algorithm processes each element of both arrays exactly once.
• Space Complexity: (O(1))
  The space complexity is constant as it only uses a few additional variables.

Example Output

For the given input:

Input: A = [1, 2, 3, 0, 0, 0], B = [2, 5, 6]
Output: Merged array: 1 2 2 3 5 6

This output indicates that the two arrays have been successfully merged into a single sorted array.

Conclusion

The Merge Sorted Array problem is an essential exercise in understanding how to efficiently combine sorted data structures. Mastering this problem can enhance your problem-solving skills and prepare you for more complex algorithmic challenges in coding interviews.

For any questions or modifications, feel free to reach out to Divi Tech HR Solutions at info@divisolutions.in.

If you found this blog helpful, please leave a comment and like the post!