How do you solve Merge Sorted Array on LeetCode?

Merge Sorted Array (LeetCode #88) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m + n) time complexity and O(1) space complexity. Key insight: Both arrays are sorted, allowing for efficient merging without additional sorting.

What is the brute force solution for Merge Sorted Array?

The brute force approach for Merge Sorted Array is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves merging the two arrays by first combining them and then sorting the combined array. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(m + n).

What algorithm or data structure is used to solve Merge Sorted Array?

Merge Sorted Array uses the following concepts: Array, Two Pointers, Sorting. The recommended patterns to study are: Two Pointers, Merging Sorted Arrays.

What are the interview tips for Merge Sorted Array?

Always clarify the constraints and edge cases before diving into coding. Think about the optimal approach first, especially when dealing with sorted arrays. Practice explaining your thought process as you code; it helps in interviews.

What are common mistakes when solving Merge Sorted Array?

Not considering edge cases where one of the arrays is empty. Using extra space unnecessarily when in-place merging is possible.

#88

Merge Sorted Array

Easy

ArrayTwo PointersSortingTwo PointersMerging Sorted Arrays

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m + n)
Space	O(n)	O(1)

💡

Intuition

Time O(m + n)Space O(1)

The optimal approach uses a two-pointer technique to merge the arrays in-place, taking advantage of the fact that both arrays are already sorted. This avoids the need for extra space and sorting.

⚙️

Algorithm

5 steps

1Step 1: Initialize two pointers, one for nums1 (i = m - 1) and one for nums2 (j = n - 1), and a pointer for the end of nums1 (k = m + n - 1).
2Step 2: Compare the elements pointed to by i and j, and place the larger one at position k in nums1.
3Step 3: Move the pointer of the array from which the element was taken, and decrement k.
4Step 4: Repeat until all elements from nums2 are merged.
5Step 5: If any elements remain in nums2, copy them to nums1.

solution.py13 lines

1# Full working Python code
2
3def merge(nums1, m, nums2, n):
4    i, j, k = m - 1, n - 1, m + n - 1
5    while j >= 0:
6        if i >= 0 and nums1[i] > nums2[j]:
7            nums1[k] = nums1[i]
8            i -= 1
9        else:
10            nums1[k] = nums2[j]
11            j -= 1
12        k -= 1
13

ℹ

Complexity note: The time complexity is O(m + n) because we traverse both arrays once. The space complexity is O(1) since we are merging in-place without using additional storage for the merged array.

1Both arrays are sorted, allowing for efficient merging without additional sorting.
2Using two pointers helps in optimizing the merging process by avoiding unnecessary comparisons.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.