88. Merge Sorted Array

How to solve Merge Sorted Array (LeetCode 88): the approach in brief

The problem

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Pattern

Merge Sorted Array is a Array/Matrix Manipulation Patterns problem, in the Merge Sorted Array (In-place from End) subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Learn the merge sorted array technique starting from the end. Essential for space-efficient array merging in coding interviews.

Approach outline

1. You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?
2. If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.

Complexity

The reference solution runs in O(m + n) time and O(1) space.

Asked at

Merge Sorted Array has been reported in interviews at Facebook, Microsoft, Amazon, Bloomberg, Walmart Labs, IBM, Oracle, Apple.