Merging Two Sorted Arrays Using Three Pointers in Java

Introduction

Merging two sorted arrays is a fundamental problem in programming, commonly encountered in sorting and searching algorithms. Understanding how to merge sorted arrays efficiently is essential for high school students preparing for coding competitions and technical interviews.

In this article, we’ll discuss an efficient three-pointer technique to merge two sorted arrays into one while maintaining their order. This is an excellent problem to strengthen problem-solving skills, algorithmic thinking, and time complexity analysis.

Problem Statement

Given two sorted integer arrays, nums1 and nums2, merge them into a new sorted array in non-decreasing order.

Approach: Three-Pointer Technique

1. Create a new array result with a size equal to the sum of the lengths of nums1 and nums2.
2. Initialize three pointers:
   • p1 → Tracks position in nums1
   • p2 → Tracks position in nums2
   • p3 → Tracks position in result
3. Compare elements from nums1 and nums2 and insert the smaller one into result.
4. If one array is exhausted, append the remaining elements of the other array to result.

import java.util.Arrays;

public class MergeSortedArrays {
    
    public static int[] mergeSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] result = new int[m + n];

        int p1 = 0, p2 = 0, p3 = 0;

        // Merge both arrays
        while (p1 < m && p2 < n) {
            if (nums1[p1] < nums2[p2]) {
                result[p3++] = nums1[p1++];
            } else {
                result[p3++] = nums2[p2++];
            }
        }

        // Append remaining elements of nums1 (if any)
        while (p1 < m) {
            result[p3++] = nums1[p1++];
        }

        // Append remaining elements of nums2 (if any)
        while (p2 < n) {
            result[p3++] = nums2[p2++];
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 3, 5, 7};
        int[] nums2 = {2, 4, 6, 8};

        int[] mergedArray = mergeSortedArrays(nums1, nums2);
        System.out.println("Merged Sorted Array: " + Arrays.toString(mergedArray));
    }
}

Explanation of Code

1. We initialize three pointers p1, p2, and p3.
2. We iterate through both arrays until one is fully traversed.
3. Comparisons are made between elements pointed to by p1 and p2, and the smaller element is inserted into result.
4. Once either nums1 or nums2 is exhausted, we append the remaining elements of the other array to result.
5. Finally, we return the merged array.

Time Complexity Analysis

• Merging two sorted arrays takes O(m + n) time, where m and n are the sizes of the two arrays.
• Space complexity is O(m + n) as we are using a new array result to store the output.