Solution: Merge Sorted Array

Let's solve the Merge Sorted Array problem using the K-way Merge pattern.

We'll cover the following

Statement

Given two sorted integer arrays, nums1nums1 and nums2nums2, and the number of data elements in each array, mm and nn, implement a function that merges the second array into the first one. You have to modify nums1nums1 in place.

Note: Assume that nums1nums1 has a size equal to m+nm + n, meaning it has enough space to hold additional elements from nums2nums2.

Constraints:

  • nums1.length =m+n= m + n
  • nums2.length =n= n
  • 0≤m,n≤2000 \leq m, n \leq 200
  • 1≤m+n≤2001 \leq m + n \leq 200
  • −103≤-10^3 \leq nums1[i], nums2[j] ≤103\leq 10^3

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

The naive approach here is to append the second list to the first—at a cost of O(n)O(n)—and then sort it using quick sort—at a cost of O((m+n)log⁡(m+n))O((m + n) \log(m + n))—for an overall time complexity of O((m+n)log⁡(m+n))O((m + n) \log(m + n)).

Optimized approach using k-way merge

This approach uses backward traversal to merge two sorted arrays into the first array in place. Initially, two pointers are set to point at the last elements of both arrays. A third pointer is also positioned at the end of the first array, pointing to the empty location. It compares the elements at the first and second pointer and checks the larger among them. The larger one is placed at the location pointed by the third pointer. Then pointers are adjusted, decrementing the third one and moving the first or second pointer one step back depending on the larger element. This ensures that the smallest element among the compared elements can be further considered in the merging process. This backward merging continues until all elements of the second array have been placed into the first array, resulting in a fully merged, sorted array.

With the k-way merge approach, we iterate over our given arrays using two pointers and merge them in place. The time complexity for this is O(m+n)O(m + n), which is more efficient than the O((m+n)log⁡(m+n))O((m + n) \log(m + n)) complexity of the naive approach.

The slides below illustrate how we would like the algorithm to run:

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

First, we initialize two pointers, p1 and p2, that point to the last element of each array. p1 is initialized to m - 1, the index of the last data element in nums1, and p2 is initialized to n - 1, the index of the last data element in nums2.

class MergeSorted {
  
  public static String printArraywithMarkers(int[] arr, int pValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == pValue) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (pValue == arr.length - 1) {
      out += "«" + arr[arr.length - 1];
      out += "»]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static void mergeSorted(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1; // set p1 to the last initialised element of nums1
    int p2 = n - 1; // set p2 to the last element of nums2
    System.out.println("\n\t\tInitialising p1 to the last data element of nums1:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums1, p1));
    System.out.println("\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
    System.out.println("\n\t\tInitialising p2 to the last data element of nums2:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
    System.out.println("\t\t\tp1: " + p2 + ", value: " + nums2[p2]);
  }
  public static void main(String args[]) {
    int[] m = {9, 2, 3, 1, 8};
    int[] n = {6, 1, 4, 2, 1};
    int[][] nums1 = {
      {23, 33, 35, 41, 44, 47, 56, 91, 105, 0, 0, 0, 0, 0, 0},
      {1, 2, 0},
      {1, 1, 1, 0, 0, 0, 0},
      {6, 0, 0},
      {12, 34, 45, 56, 67, 78, 89, 99, 0}
    };
    int[][] nums2 = {
      {32, 49, 50, 51, 61, 99},
      {7},
      {1, 2, 3, 4},
      {- 45, -99},
      {100}
      };
    int k = 1;
    for (int i = 0; i < m.length; i++) {
      System.out.print(k + ".\tnums1: [");
      for (int j = 0; j < nums1[i].length - 1; j++) {
        System.out.print(nums1[i][j] + ", ");
      }
      System.out.println(nums1[i][nums1[i].length - 1] + "], m: " + m[i]);
      System.out.print("\tnums2: [");
      for (int j = 0; j < nums2[i].length - 1; j++) {
        System.out.print(nums2[i][j] + ", ");
      }
      System.out.println(nums2[i][nums2[i].length - 1] + "], n: " + n[i]);
      mergeSorted(nums1[i], m[i], nums2[i], n[i]);
      System.out.println("\tMerged list: None");
      System.out.println(PrintHyphens.repeat("-", 100));
      k += 1;
    }
  }
}
Initializing the pointers

Next, we initialize another pointer called p, which points to the m + n - 1 index of nums1. We use the pointer p to traverse the nums1 array from the end. If the value at p1 is greater than the value at p2, the result at p is equal to the value at p1. We then decrement p1 to move it one element back.

class MergeSorted {
  
  public static String printArraywithMarkers(int[] arr, int pValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == pValue) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (pValue == arr.length - 1) {
      out += "«" + arr[arr.length - 1];
      out += "»]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static String printArraywithMarkers(int[] arr, int iValue, int jValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == iValue || i == jValue) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (iValue == arr.length - 1 || jValue == arr.length - 1) {
      out += "«" + arr[arr.length - 1];
      out += "»]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static int[] mergeSorted(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1; // set p1 to the last initialised element of nums1
    int p2 = n - 1; // set p2 to the last element of nums2
    System.out.println("\n\t\tInitialising p1 to the last data element of nums1:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums1, p1));
    System.out.println("\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
    System.out.println("\n\t\t Initialising p2 to the last data element of nums2:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
    System.out.println("\t\t\tp1: " + p2 + ", value: " + nums2[p2]);
    // traverse backwards over the nums1 array
    System.out.println("\n\tTraversing the nums1 array using pointer p:");
    int x = 0;
    for (int p = m + n - 1; p >= 0; p--) {
      System.out.println("\t\tLoop iteration: " + x);
      x += 1;
      System.out.println("\t\t\t" + printArraywithMarkers(nums1, p1));
      System.out.print("\t\t\tp1: " + p1 + ", value: ");
      if (p1 < 0) System.out.println(nums1[p1 + 1]);
      else System.out.println(nums1[p1]);
      System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
      System.out.print("\t\t\tp2: " + p2 + ", value: ");
      if (p2 < 0) System.out.println(nums2[p2 + 1]);
      else System.out.println(nums2[p2]);
      // if p1 is not on the first element and the nums1 element is greater than nums2 element
      if (p1 >= 0 && nums1[p1] > nums2[p2]) {
        System.out.println("\t\t\tThe value at p1(" + nums1[p1] + ") > the value at p2(" + nums2[p2] + ")");
        // set the element at index p = the element on index p1 in nums1
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums1, p1, p));
        System.out.println("\t\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
        System.out.println("\t\t\t\tp: " + p + ", value: " + nums1[p]);
        nums1[p] = nums1[p1];
        System.out.println("\t\t\t\tChanging the value at p to the value at p1:");
        System.out.println("\t\t\t\t\t" + printArraywithMarkers(nums1, p));
        // move the p1 pointer one element back
        System.out.println("\t\t\t\tDecrementing p1: " + p1 + " ⟶ " + (p1 - 1) + "\n");
        p1 -= 1;
      }
    }
    return nums1;
  }
  public static void main(String args[]) {
    int[] m = {9, 2, 3, 1, 8};
    int[] n = {6, 1, 4, 2, 1};
    int[][] nums1 = {
      {23, 33, 35, 41, 44, 47, 56, 91, 105, 0, 0, 0, 0, 0, 0},
      {1, 2, 0},
      {1, 1, 1, 0, 0, 0, 0},
      {6, 0, 0},
      {12, 34, 45, 56, 67, 78, 89, 99, 0}
    };
    int[][] nums2 = {
      {32, 49, 50, 51, 61, 99},
      {7},
      {1, 2, 3, 4},
      {- 45, -99},
      {100}
      };
    int k = 1;
    for (int i = 0; i < m.length; i++) {
      System.out.print(k + ".\tnums1: [");
      for (int j = 0; j < nums1[i].length - 1; j++) {
        System.out.print(nums1[i][j] + ", ");
      }
      System.out.println(nums1[i][nums1[i].length - 1] + "], m: " + m[i]);
      System.out.print("\tnums2: [");
      for (int j = 0; j < nums2[i].length - 1; j++) {
        System.out.print(nums2[i][j] + ", ");
      }
      System.out.println(nums2[i][nums2[i].length - 1] + "], n: " + n[i]);
      mergeSorted(nums1[i], m[i], nums2[i], n[i]);
      System.out.println("\tMerged list: None");
      System.out.println(PrintHyphens.repeat("-", 100));
      k += 1;
    }
  }
}
Traversing the array

If the value at p1 is less than the value at p2, the result at p is set equal to the value at p2. We decrement the pointer for the list that the entry was copied from.

The traversal continues until nums2 is merged with nums1.

class MergeSorted {
  
  public static String printArraywithMarkers(int[] arr, int pValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == pValue) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (pValue == arr.length - 1) {
      out += "«" + arr[arr.length - 1];
      out += "»]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static String printArraywithMarkers(int[] arr, int iValue, int jValue) {
    String out = "[";
    for (int i = 0; i < arr.length - 1; i++) {
      if (i == iValue || i == jValue) {
        out += "«";
        out += String.valueOf(arr[i]) + "»" + ", ";
      }
      else {
        out += String.valueOf(arr[i]) + ", ";
      }
    }
    if (iValue == arr.length - 1 || jValue == arr.length - 1) {
      out += "«" + arr[arr.length - 1];
      out += "»]";
    }
    else {
      out += arr[arr.length - 1];
      out += "]";
    }
    return out;
  }
  public static int[] mergeSorted(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1; // set p1 to the last initialised element of nums1
    int p2 = n - 1; // set p2 to the last element of nums2
    System.out.println("\n\t\tInitialising p1 to the last data element of nums1:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums1, p1));
    System.out.println("\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
    System.out.println("\n\t\t Initialising p2 to the last data element of nums2:");
    System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
    System.out.println("\t\t\tp1: " + p2 + ", value: " + nums2[p2]);
    // traverse backwards over the nums1 array
    System.out.println("\n\tTraversing the nums1 array using pointer p:");
    int x = 0;
    for (int p = m + n - 1; p >= 0; p--) {
      System.out.println("\t\tLoop iteration: " + x);
      if (p2 < 0) {
        System.out.println("\t\t\tBreaking the loop since p2(" + p2 + ") < 0");
        break;
      }
      else if (p1 < 0) {
        System.out.println("\t\t\tp1: " + p1 + " as we've traversed the entire nums1 array");
        System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
        System.out.println("\t\t\tp2: " + p2 + ", value: " + nums2[p2]);
      }
      else {
        System.out.println("\t\t\t" + printArraywithMarkers(nums1, p1));
        System.out.println("\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
        System.out.println("\t\t\t" + printArraywithMarkers(nums2, p2));
        System.out.println("\t\t\tp2: " + p2 + ", value: " + nums2[p2]);
      }
      x += 1;
      // if p1 is not on the first element and the nums1 element is greater than nums2 element
      if (p1 >= 0 && nums1[p1] > nums2[p2]) {
        System.out.println("\t\t\tThe value at p1(" + nums1[p1] + ") > the value at p2(" + nums2[p2] + ")");
        // set the element at index p = the element on index p1 in nums1
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums1, p1, p));
        System.out.println("\t\t\t\tp1: " + p1 + ", value: " + nums1[p1]);
        System.out.println("\t\t\t\tp: " + p + ", value: " + nums1[p]);
        nums1[p] = nums1[p1];
        System.out.println("\t\t\t\tChanging the value at p to the value at p1:");
        System.out.println("\t\t\t\t\t" + printArraywithMarkers(nums1, p));
        // move the p1 pointer one element back
        System.out.println("\t\t\t\tDecrementing p1: " + p1 + " ⟶ " + (p1 - 1) + "\n");
        p1 -= 1;
      }
      else {
        if (p1 > 0) System.out.println("\t\t\tThe value at p1(" + nums1[p1] + ")  <=  the value at p2(" + nums2[p2] + ")");
        else System.out.println("\t\t\tMerging nums2 with nums1");
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums2, p2));
        System.out.println("\t\t\t\tp2: " + p2 + ", value: " + nums2[p2]);
        System.out.println("\t\t\t\t" + printArraywithMarkers(nums1, p));
        System.out.println("\t\t\t\tp: " + p + ", value: " + nums1[p]);
        // set the nums1 element at index p = nums2 element at index p2
        nums1[p] = nums2[p2];
        System.out.println("\t\t\t\tChanging the value at p to the value at p2:");
        System.out.println("\t\t\t\t\t" + printArraywithMarkers(nums1, p));
        // move the p2 pointer one element back
        System.out.println("\t\t\t\tDecrementing p2: " + p2 + " ⟶ " + (p2 - 1) + "\n");
        p2 -= 1;
      }
    }
    return nums1;
  }
  public static void main(String args[]) {
    int[] m = {9, 2, 3, 1, 8};
    int[] n = {6, 1, 4, 2, 1};
    int[][] nums1 = {
      {23, 33, 35, 41, 44, 47, 56, 91, 105, 0, 0, 0, 0, 0, 0},
      {1, 2, 0},
      {1, 1, 1, 0, 0, 0, 0},
      {6, 0, 0},
      {12, 34, 45, 56, 67, 78, 89, 99, 0}
    };
    int[][] nums2 = {
      {32, 49, 50, 51, 61, 99},
      {7},
      {1, 2, 3, 4},
      {- 45, -99},
      {100}
      };
    int k = 1;
    for (int i = 0; i < m.length; i++) {
      System.out.print(k + ".\tnums1: [");
      for (int j = 0; j < nums1[i].length - 1; j++) {
        System.out.print(nums1[i][j] + ", ");
      }
      System.out.println(nums1[i][nums1[i].length - 1] + "], m: " + m[i]);
      System.out.print("\tnums2: [");
      for (int j = 0; j < nums2[i].length - 1; j++) {
        System.out.print(nums2[i][j] + ", ");
      }
      System.out.println(nums2[i][nums2[i].length - 1] + "], n: " + n[i]);
      System.out.println("\tMerged list:" + Arrays.toString(mergeSorted(nums1[i], m[i], nums2[i], n[i])));
      System.out.println(PrintHyphens.repeat("-", 100));
      k += 1;
    }
  }
}
Merging the Array

Just the code

Here’s the complete solution to this problem:

class MergeSorted {
  
  public static int[] mergeSorted(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    for (int p = m + n - 1; p >= 0; p--) {
      if (p2 < 0) {
        break;
      }
      if (p1 >= 0 && nums1[p1] > nums2[p2]) {
        nums1[p] = nums1[p1];
        p1 -= 1;
      }
      else {
        nums1[p] = nums2[p2];
        p2 -= 1;
      }
    }
    return nums1;
  }
  // Driver code
  public static void main(String args[]) {
    int[] m = {9, 2, 3, 1, 8};
    int[] n = {6, 1, 4, 2, 1};
    int[][] nums1 = {
      {23, 33, 35, 41, 44, 47, 56, 91, 105, 0, 0, 0, 0, 0, 0},
      {1, 2, 0},
      {1, 1, 1, 0, 0, 0, 0},
      {6, 0, 0},
      {12, 34, 45, 56, 67, 78, 89, 99, 0}
    };
    int[][] nums2 = {
      {32, 49, 50, 51, 61, 99},
      {7},
      {1, 2, 3, 4},
      {- 45, -99},
      {100}
      };
    int k = 1;
    for (int i = 0; i < m.length; i++) {
      System.out.print(k + ".\tnums1: [");
      for (int j = 0; j < nums1[i].length - 1; j++) {
        System.out.print(nums1[i][j] + ", ");
      }
      System.out.println(nums1[i][nums1[i].length - 1] + "], m: " + m[i]);
      System.out.print("\tnums2: [");
      for (int j = 0; j < nums2[i].length - 1; j++) {
        System.out.print(nums2[i][j] + ", ");
      }
      System.out.println(nums2[i][nums2[i].length - 1] + "], n: " + n[i]);
      System.out.println("\tMerged list:" + Arrays.toString(mergeSorted(nums1[i], m[i], nums2[i], n[i])));
      System.out.println(PrintHyphens.repeat("-", 100));
      k += 1;
    }
  }
}
Merging the Array

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Initialize two pointers that point to the last data elements in both arrays.
  2. Initialize a third pointer that points to the last index of nums1nums1.
  3. Traverse nums1nums1 from the end using the third pointer and compare the values corresponding to the first two pointers.
  4. Place the larger of the two values at the third pointer’s index.
  5. Repeat the process until the two arrays are merged.

Time complexity

The time complexity is O(n+m)O(n + m), where nn and mm are the counts of initialized elements in the two arrays.

Space complexity

The space complexity is O(1)O(1) because we only use the space required for three indices.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.