What is the time complexity of Merge Sorted Array?

The optimal solution has a time complexity of O(m+n).

What data structures are used to solve Merge Sorted Array?

This problem uses Array, Two Pointers, Sorting. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Merge Sorted Array?

**Merge from the Rear to Prevent Overwriting:** The fundamental insight is to perform the merge operation starting from the *end* of the combined logical array and working backward into `nums1`. Since the available empty space in `nums1` is at its tail (indices `m` through `m+n-1`), filling these spots with the largest elements first ensures that `nums1`'s original `m` elements are never overwritten before they've been properly compared and potentially moved. **Three-Pointer Simultaneous Traversal:** Employing three distinct pointers (`p1` for `nums1`'s active elements, `p2` for `nums2`'s elements, and `p` for the current write position in `nums1`) streamlines the logic. In each iteration, we compare `nums1[p1]` and `nums2[p2]`, place the larger element at `nums1[p]`, and then decrement `p` along with the pointer that contributed the element. This systematic decrement ensures all elements are considered and placed in their correct sorted position.

Which companies ask LeetCode 88. Merge Sorted Array in interviews?

This problem is frequently asked at Accenture, Adobe, Agoda, Amazon, Apple and 41 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Merge Sorted Array - LeetCode 88 Solution

Merge Sorted Array - Complete Solution Guide

Merge Sorted Array is LeetCode problem 88, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Merge nums1 and nums2 into a single array sorted in non-decreasing order . The final sorted array should not be returned by the function, but instead be stored inside the array nums1 . To accommodate this, nums1 has a length of m + n , where the first m elements denote the elements that should be merged, and the last n

Detailed Explanation

This problem asks us to merge two already sorted integer arrays, `nums1` and `nums2`, directly into `nums1` itself. The crucial setup details are what make this problem interesting: `nums1` initially contains `m` elements, representing its 'active' data, followed by `n` zero-padded spaces. This means `nums1` has a total length of `m + n`, precisely enough to hold all elements from both arrays. `nums2` contains `n` elements. Both arrays are sorted in non-decreasing order.

Solution Approach

The elegant solution to this problem leverages the fact that `nums1`'s extra space is conveniently located at its *end*, and both input arrays are sorted. Instead of attempting to merge from the beginning, which would necessitate complex shifting of `nums1`'s existing elements to make room (and potential data loss), we approach the problem by merging from the *end* of the combined array backward. We maintain three pointers: `p1` points to the last *actual* element of `nums1` (at index `m-1`), `p2` points to the last element of `nums2` (at index `n-1`), and `p` points to the last available position in `nums1` where a merged element should be placed (at index `m+n-1`). The algorithm proceeds by comparing the elements pointed to by `p1` and `p2`. Whichever element is larger (or equal) is the one that should occupy the current largest available slot `p`. We place that element at `nums1[p]`, and then decrement `p` and the pointer from which we took the element (`p1` or `p2`). This process continues as long as both `p1` and `p2` are valid (non-negative). This backward traversal is key: it ensures we are always writing into empty or already processed space, never overwriting a `nums1` element that we still need to compare. A crucial final step handles the scenario where `nums2` still has elements remaining after `nums1`'s initial `m` elements have all been placed. This happens if `nums2` contains elements that are all smaller than the remaining elements of `nums1` (or `nums1`'s elements are exhausted first). If `p1` reaches `-1` but `p2` is still valid, all remaining elements in `nums2` are simply copied directly into the remaining slots in `nums1` from `p` downwards, as they are already sorted and belong at the front of the merged array.

Step-by-Step Algorithm

Step 1: Initialize three pointers: `p1` to `m - 1`, `p2` to `n - 1`, and `p` to `m + n - 1`. These point to the last elements of the relevant portions of the arrays.
Step 2: Compare `nums1[p1]` and `nums2[p2]`. The larger element is placed at `nums1[p]`, and the corresponding pointer (`p1` or `p2`) is decremented. `p` is also decremented.
Step 3: Repeat Step 2 until either `p1` or `p2` reaches the beginning of its array (i.e., `p1 < 0` or `p2 < 0`).
Step 4: If any elements remain in `nums2` (`p2 >= 0`), copy the remaining elements from `nums2` to the beginning portion of `nums1`.

Key Insights

**Merge from the Rear to Prevent Overwriting:** The fundamental insight is to perform the merge operation starting from the *end* of the combined logical array and working backward into `nums1`. Since the available empty space in `nums1` is at its tail (indices `m` through `m+n-1`), filling these spots with the largest elements first ensures that `nums1`'s original `m` elements are never overwritten before they've been properly compared and potentially moved.
**Three-Pointer Simultaneous Traversal:** Employing three distinct pointers (`p1` for `nums1`'s active elements, `p2` for `nums2`'s elements, and `p` for the current write position in `nums1`) streamlines the logic. In each iteration, we compare `nums1[p1]` and `nums2[p2]`, place the larger element at `nums1[p]`, and then decrement `p` along with the pointer that contributed the element. This systematic decrement ensures all elements are considered and placed in their correct sorted position.
**Special Handling for Remaining `nums2` Elements:** An important edge case arises if `nums1`'s `m` elements are exhausted (i.e., `p1` becomes negative) while `nums2` still has elements remaining (`p2` is non-negative). This implies all remaining `nums2` elements are smaller than any elements already placed from `nums1` and thus belong at the beginning of the merged array. A dedicated loop to copy these remaining `nums2` elements directly into `nums1` is essential. No similar loop is strictly needed for remaining `nums1` elements because they are already *in* `nums1` in their correct relative positions.

Complexity Analysis

Time Complexity: O(m+n)

Space Complexity: O(1)

Topics

This problem involves: Array, Two Pointers, Sorting.

Companies

Asked at: Accenture, Adobe, Agoda, Amazon, Apple, Atlassian, Avito, Barclays, Bloomberg, ByteDance, Canonical, Cisco, Cognizant, Criteo, EPAM Systems, Expedia, Goldman Sachs, HCL, Hubspot, IBM, Infosys, Intel, LinkedIn, Meta, Microsoft, Netflix, Nvidia, Oracle, Palo Alto Networks, PayPal, Qualcomm, ServiceNow, Squarespace, Swiggy, TikTok, Uber, VK, Virtusa, Walmart Labs, Wipro, Yahoo, Yandex, Zoho, athenahealth, persistent systems, tcs.

Merge Sorted Array | LeetCode 88

Easy

Array Two Pointers Sorting

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

Solution Code

Available in:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 88: Merge Sorted Array - Detailed explanation and solution approaches.

Topics

Array Two Pointers Sorting

Companies

AccentureAdobeAgodaAmazonAppleAtlassianAvitoBarclays

Stats

Difficulty:Easy

Languages:4

Companies:46

Problem #:88

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Step 1: Initialize three pointers: `p1` to `m - 1`, `p2` to `n - 1`, and `p` to `m + n - 1`. These point to the last elements of the relevant portions of the arrays.
2
Step 2: Compare `nums1[p1]` and `nums2[p2]`. The larger element is placed at `nums1[p]`, and the corresponding pointer (`p1` or `p2`) is decremented. `p` is also decremented.
3
Step 3: Repeat Step 2 until either `p1` or `p2` reaches the beginning of its array (i.e., `p1 < 0` or `p2 < 0`).
4
Step 4: If any elements remain in `nums2` (`p2 >= 0`), copy the remaining elements from `nums2` to the beginning portion of `nums1`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m+n)

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The while loops iterate at most `m + n` times (the combined length of the arrays). No additional data structures are used beyond the input arrays, resulting in constant extra space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Merge Sort

Sort the entire `nums1` array after copying the `nums2` array to the end of `nums1`. This approach is simpler to understand but less efficient.

Time: O((m+n)log(m+n))Space: O(log(m+n)) or O(m+n) depending on the implementation of the merge sort

Trade-offs: Simpler to implement but significantly slower for larger arrays than the three-pointer approach. Use this only when the simplicity outweighs the performance cost.

✨

Key Insights

1**Merge from the Rear to Prevent Overwriting:** The fundamental insight is to perform the merge operation starting from the *end* of the combined logical array and working backward into `nums1`. Since the available empty space in `nums1` is at its tail (indices `m` through `m+n-1`), filling these spots with the largest elements first ensures that `nums1`'s original `m` elements are never overwritten before they've been properly compared and potentially moved.
2**Three-Pointer Simultaneous Traversal:** Employing three distinct pointers (`p1` for `nums1`'s active elements, `p2` for `nums2`'s elements, and `p` for the current write position in `nums1`) streamlines the logic. In each iteration, we compare `nums1[p1]` and `nums2[p2]`, place the larger element at `nums1[p]`, and then decrement `p` along with the pointer that contributed the element. This systematic decrement ensures all elements are considered and placed in their correct sorted position.
3**Special Handling for Remaining `nums2` Elements:** An important edge case arises if `nums1`'s `m` elements are exhausted (i.e., `p1` becomes negative) while `nums2` still has elements remaining (`p2` is non-negative). This implies all remaining `nums2` elements are smaller than any elements already placed from `nums1` and thus belong at the beginning of the merged array. A dedicated loop to copy these remaining `nums2` elements directly into `nums1` is essential. No similar loop is strictly needed for remaining `nums1` elements because they are already *in* `nums1` in their correct relative positions.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Edge case 1: `nums2` is empty. The algorithm correctly handles this by skipping the loop that processes `nums2` and leaving `nums1` unchanged.
Edge case 2: `nums1` is empty (m=0). The algorithm gracefully copies all elements from `nums2` into `nums1`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrect pointer management. Off-by-one errors or improper decrementing of pointers are very common.

✗Common mistake 2: Forgetting to handle the case where one array is exhausted before the other, leading to incorrect results. The second while loop is crucial for this.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Database merging – Combining data from two sorted tables (e.g., merging user lists based on ID).

🏦Real-world scenario 2: Data stream processing – Efficiently integrating data from two incoming sorted streams (e.g., financial data feeds).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 28, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 11

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 4

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Merge Sorted Array"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?