Home Web Front-end JS Tutorial LeetCode Challenge: Merge Sorted Array - JavaScript Solution

LeetCode Challenge: Merge Sorted Array - JavaScript Solution

Dec 17, 2024 pm 06:01 PM

LeetCode Challenge:  Merge Sorted Array - JavaScript Solution

Top Interview 150

Merging sorted arrays is a classic problem, and understanding how to solve it efficiently is essential for coding interviews. In this post, we'll tackle LeetCode's 88. Merge Sorted Array, part of the Top Interview 150 Questions challenge, using JavaScript. Let's dive into the problem, its nuances, and a clean, optimal solution!


? Problem Description
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order. Your task is to merge nums2 into nums1, such that nums1 remains sorted.

However, there's a twist:

nums1 has enough space (set to 0s) to accommodate the elements of nums2.
The final merged result must be stored in-place in nums1.


? Examples

Example 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Example 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? Key Insights

  • In-place merge: You need to fill nums1 without using extra space. This means directly modifying the array.
  • Back-to-front strategy: Since nums1 has extra space at the end, the most efficient approach is to fill it from the back.

? JavaScript Solution: Two-Pointer Approach

The optimal solution leverages a two-pointer approach, starting from the end of both arrays. This ensures that the largest elements are placed first, avoiding unnecessary shifts of elements.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};


? How It Works

  1. Start from the end:
    Compare the largest elements of nums1 and nums2 (using p1
    and p2 pointers). Place the larger element at the end of
    nums1 (using p pointer).

  2. Decrement pointers:
    Move p1, p2, and p as you process elements.

  3. Handle remaining elements:
    If any elements in nums2 are left, copy them into nums1. (No
    need to copy elements from nums1, as they’re already in place.)


? Complexity Analysis

? Dry Run
Input:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Step p1 p2 p nums1
Init 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
Final Output: [1,2,2,3,5,6]


? Try It Yourself!

Check out the full problem and test cases on LeetCode. Challenge yourself to implement the solution without looking at the code!


✨ Pro Tips for Interviews

  1. Clarify constraints: Ask if you can use extra space or if in- place is mandatory.
  2. Optimize for edge cases: Consider cases where nums2 is empty or nums1 has no initial elements (m = 0).
  3. Walk through your logic: Explain the two-pointer approach clearly to the interviewer.


Got any questions or insights? Share them in the comments below! Let’s learn together. ?

The above is the detailed content of LeetCode Challenge: Merge Sorted Array - JavaScript Solution. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undress AI Tool

Undress AI Tool

Undress images for free

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

PHP Tutorial
1503
276
How to make an HTTP request in Node.js? How to make an HTTP request in Node.js? Jul 13, 2025 am 02:18 AM

There are three common ways to initiate HTTP requests in Node.js: use built-in modules, axios, and node-fetch. 1. Use the built-in http/https module without dependencies, which is suitable for basic scenarios, but requires manual processing of data stitching and error monitoring, such as using https.get() to obtain data or send POST requests through .write(); 2.axios is a third-party library based on Promise. It has concise syntax and powerful functions, supports async/await, automatic JSON conversion, interceptor, etc. It is recommended to simplify asynchronous request operations; 3.node-fetch provides a style similar to browser fetch, based on Promise and simple syntax

JavaScript Data Types: Primitive vs Reference JavaScript Data Types: Primitive vs Reference Jul 13, 2025 am 02:43 AM

JavaScript data types are divided into primitive types and reference types. Primitive types include string, number, boolean, null, undefined, and symbol. The values are immutable and copies are copied when assigning values, so they do not affect each other; reference types such as objects, arrays and functions store memory addresses, and variables pointing to the same object will affect each other. Typeof and instanceof can be used to determine types, but pay attention to the historical issues of typeofnull. Understanding these two types of differences can help write more stable and reliable code.

A JS roundup of higher-order functions beyond map and filter A JS roundup of higher-order functions beyond map and filter Jul 10, 2025 am 11:41 AM

In JavaScript arrays, in addition to map and filter, there are other powerful and infrequently used methods. 1. Reduce can not only sum, but also count, group, flatten arrays, and build new structures; 2. Find and findIndex are used to find individual elements or indexes; 3.some and everything are used to determine whether conditions exist or all meet; 4.sort can be sorted but will change the original array; 5. Pay attention to copying the array when using it to avoid side effects. These methods make the code more concise and efficient.

Comparing Functional Programming and Object-Oriented Programming in JavaScript Comparing Functional Programming and Object-Oriented Programming in JavaScript Jul 09, 2025 am 02:40 AM

Functional programming (FP) is suitable for data immutable scenarios, emphasizing pure functions and no side effects, and is suitable for processing data transformations such as array mapping or filtering; Object-oriented programming (OOP) is suitable for modeling real-world entities, encapsulating data and behaviors through classes and objects, and is suitable for managing objects with state such as bank accounts; JavaScript supports the use of the two, and selecting appropriate paradigms according to needs to improve code quality. 1.FP is suitable for scenarios where data transformation and state remains unchanged, making it easy to test and debug. 2.OOP is suitable for modeling entities with identity and internal state, providing a good organizational structure. 3. JavaScript allows the mixing of FP and OOP, using their respective advantages to improve maintainability.

How to Check if an Array Includes a Value in JavaScript How to Check if an Array Includes a Value in JavaScript Jul 13, 2025 am 02:16 AM

In JavaScript, check whether an array contains a certain value. The most common method is include(), which returns a boolean value and the syntax is array.includes(valueToFind), for example fruits.includes('banana') returns true; if it needs to be compatible with the old environment, use indexOf(), such as numbers.indexOf(20)!==-1 returns true; for objects or complex data, some() method should be used for in-depth comparison, such as users.some(user=>user.id===1) returns true.

What is the difference between == and === in JavaScript? What is the difference between == and === in JavaScript? Jul 09, 2025 am 02:41 AM

Themaindifferencebetween==and===inJavaScriptistypecoercionhandling.1.==performstypecoercion,convertingdatatypestomatchbeforecomparison,whichcanleadtounexpectedresultslike"5"==5returningtrueor[]==![]returningtrue.2.===comparesbothvalueandtyp

Filtering an Array of Objects in JavaScript Filtering an Array of Objects in JavaScript Jul 12, 2025 am 03:14 AM

The filter() method in JavaScript is used to create a new array containing all the passing test elements. 1.filter() does not modify the original array, but returns a new array that meets the conditional elements; 2. The basic syntax is array.filter((element)=>{returncondition;}); 3. The object array can be filtered by attribute value, such as filtering users older than 30; 4. Support multi-condition filtering, such as meeting the age and name length conditions at the same time; 5. Can handle dynamic conditions and pass filter parameters into functions to achieve flexible filtering; 6. When using it, be careful to return boolean values ​​to avoid returning empty arrays, and combine other methods to achieve complex logic such as string matching.

Avoiding Callback Hell Using Promises or Async/Await in Javascript Avoiding Callback Hell Using Promises or Async/Await in Javascript Jul 09, 2025 am 02:04 AM

Callback hell refers to nested callbacks that make the code difficult to maintain. The solution is to use Promise or async/await. 1. Promise replaces nested structures through chain calls, making the logic clear and error handling unified; 2. async/await is based on Promise, writing asynchronous code in a synchronous way to improve readability and debugging experience; 3. In actual applications, you need to pay attention to the single function responsibilities, use Promise.all in parallel tasks, correctly handle errors and avoid abuse of async/await.

See all articles