Tagged
• DSA Problems
• Sorting
• Array
• Two Pointer Technique
•

Problem Statement

```1Problem Description : 2Given two integer arrays A and B sorted in increasing order, merge A and B into a single sorted array C in increasing order.3
4Input:  5Two sorted arrays A and B6 7Output: 8Return merged sorted array C.```

Example 1:

Input : A = {1, 3, 5, 6}, B = {2, 4, 7}

Output: C = {1, 2, 3, 4, 5, 6, 7}

Explanation : Merging A and B produces C.

Example 2:

Input : A = {1, 2} and B = {7}

Output: C = {1, 2, 7}

Explanation : Merging A and B produces C.

Naïve Solution

Algorithm

• Create an array C of length m+n where m is length of array A and n is length of array B.
• Copy elements of A and B into Array C.
• Sort the array C.

Complexity Analysis

• Time Complexity : O( (m+n) log (m+n) ) (Sorting Complexity)
• Space Complexity: O(1)

Using Two Pointers

Algorithm

```1Input : Sorted arrays A and B given 2
3Step 1: Initialize m and n to length of the arrays A and B respectively. 4
5Step 2: Create empty array C of length m+n. 6
7Step 3: initialize i, j and k  to index 0 of A, B and C respectively.  8
9Step 4:  if i < m and j < n , compare A[i] and B[j]    10  Step 4.1 : if A[i] is lesser than B[j], copy A[i] into C[k] and increment i and k.  11  Step 4.2 : else copy B[j] into C[k] and increment j and k. 12
13Step 5: else if i < m copy A[i] into C[k] and increment i and k.14
15Step 6: else if j < n copy B[j] into C[k] and increment j and k. 16
17Step 7: Repeat Steps 4 to 6 until we exhaust arrays A and B. ```

Example Dry Run

Input : A[] = {1, 3, 5, 6} , B[] = {2, 4, 7}

```1Step 1 : m = A.length and n = B.length => A = 4 and B = 3 2
3Step 2: initialize result array C of length (m+n) which is  7  4
5Step 3 : initialize i = 0 , j = 0 and k = 0 for arrays A, B and C respectively.  6
7Step 4 to 6  8   Iteration 1 :  i = 0, j = 0 and k = 0  9                  Compare A[0] with B[0]  10                  here A[0] < B[0] => C[0] = A[0] and i ++, k++  11
12   Iteration 2 :  i = 1, j = 0 and k = 1  13                  Compare A[1] with B[0]  14                  here A[1] > B[0] => C[1] = B[0] and j++, k++  15
16   Iteration 3 :  i = 1, j = 1 and k = 2  17                  Compare A[1] with B[1]  18                  here A[1] < B[1] => C[2] = A[1] and i++, k++  19
20   Iteration 4 :  i = 2, j = 1 and k = 3  21                  Compare A[2] with B[1]  22                  here A[2] > B[1] => C[3] = B[1] and j++, k++  23
24   Iteration 5 :  i = 2, j = 2 and k = 4  25                  Compare A[2] with B[2]  26                  here A[2] < B[2] => C[4] = A[2] and i++, k++  27
28   Iteration 6 :  i = 3 and j = 2 and k = 5  29                  Compare A[3] with B[2]  30                  here A[3] < B[2] => C[5] = A[3] and i++, k++  31
32   Iteration 7: i = 4 and j = 2 and k = 6  33      As A elements over C[6] = B[2] and j++  34
35Both A and B elements exhausted and we got the final array C.```

Output : {1, 2, 3, 4, 5, 6, 7}

Java Implementation

```1import java.util.Arrays;2public class MergeTwoSortedArrays {3
4    public int[] merge(int[] A, int[] B) {5        // initialize m and n to length of arrays A and B6        int m = A.length;7        int n = B.length;8
9        // create result array C of length (m+n)10        int[] C = new int[m+n] ;11
12        // initialize i, j and k to 013        // Index i is for array A14        // Index j is for array B15        // Index k is for result array C16        int i=0 , j = 0, k = 0;17
18        //Condition to check any array got exhausted ?19        while(i < m && j < n){20
21            // compare A[i] with B[j]22            if(A[i] < B[j]){23
24                // As A[i] is smaller, copy A[i] into C[k]25                C[k] = A[i];26
27                // as A[i] processed move to next element by incrementing i28                // as C[k] already filled, move to next index by incrementing k29                i++; k++;30            }else{31
32                // As B[j] is smaller, copy B[j] into C[k]33                C[k] = B[j];34
35                // as B[j] processed move to next element by incrementing j36                // as C[k] already filled, move to next index by incrementing k37                j++; k++;38            }39        }40
41        // This is the case when array B all elements processed & 42        // A has still unvisited elements43        while(i < m) {44            C[k++] = A[i++];45        }46
47        // This is the case when array A all elements processed &48        // B has still unvisited elements49        while (j < n) {50            C[k++] = B[j++];51        }52        53        // return the result array54        return C;55    }56
57    // Driver Code to test the code58    public static void main(String[] args) {59        MergeTwoSortedArrays obj = new MergeTwoSortedArrays();60        int[] A = {1, 3, 5, 6};61        int[] B = {2, 4, 7};62        int[] resultArray = obj.merge(A, B);63        System.out.println(Arrays.toString(resultArray));64    }65}```

Complexity Analysis

• Time Complexity : O(m+n) where m and n are length of arrays A and B respectively.
• Space Complexity: O(1) as we are not using any extra space.

Approaches Comparison

ApproachTime ComplexitySpace ComplexityRemarks
Naïve SolutionO( (m+n) log (m+n) )O(1)Complexity of Sorting the array
Using Two Pointer TechniqueO(m+n)O(1)

• DSA Problems
• Sorting
• Array
• Two Pointer Technique
•
...