LeetCode Challenge: Merge Sorted Array - JavaScript Solution
Dec 17, 2024 pm 06:01 PMTop 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
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).Decrement pointers:
Move p1, p2, and p as you process elements.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
- Clarify constraints: Ask if you can use extra space or if in- place is mandatory.
- Optimize for edge cases: Consider cases where nums2 is empty or nums1 has no initial elements (m = 0).
- 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!

Hot AI Tools

Undress AI Tool
Undress images for free

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Clothoff.io
AI clothes remover

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

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

JavaScript's garbage collection mechanism automatically manages memory through a tag-clearing algorithm to reduce the risk of memory leakage. The engine traverses and marks the active object from the root object, and unmarked is treated as garbage and cleared. For example, when the object is no longer referenced (such as setting the variable to null), it will be released in the next round of recycling. Common causes of memory leaks include: ① Uncleared timers or event listeners; ② References to external variables in closures; ③ Global variables continue to hold a large amount of data. The V8 engine optimizes recycling efficiency through strategies such as generational recycling, incremental marking, parallel/concurrent recycling, and reduces the main thread blocking time. During development, unnecessary global references should be avoided and object associations should be promptly decorated to improve performance and stability.

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 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.

Hello, JavaScript developers! Welcome to this week's JavaScript news! This week we will focus on: Oracle's trademark dispute with Deno, new JavaScript time objects are supported by browsers, Google Chrome updates, and some powerful developer tools. Let's get started! Oracle's trademark dispute with Deno Oracle's attempt to register a "JavaScript" trademark has caused controversy. Ryan Dahl, the creator of Node.js and Deno, has filed a petition to cancel the trademark, and he believes that JavaScript is an open standard and should not be used by Oracle

Which JavaScript framework is the best choice? The answer is to choose the most suitable one according to your needs. 1.React is flexible and free, suitable for medium and large projects that require high customization and team architecture capabilities; 2. Angular provides complete solutions, suitable for enterprise-level applications and long-term maintenance; 3. Vue is easy to use, suitable for small and medium-sized projects or rapid development. In addition, whether there is an existing technology stack, team size, project life cycle and whether SSR is needed are also important factors in choosing a framework. In short, there is no absolutely the best framework, the best choice is the one that suits your needs.

CacheAPI is a tool provided by the browser to cache network requests, which is often used in conjunction with ServiceWorker to improve website performance and offline experience. 1. It allows developers to manually store resources such as scripts, style sheets, pictures, etc.; 2. It can match cache responses according to requests; 3. It supports deleting specific caches or clearing the entire cache; 4. It can implement cache priority or network priority strategies through ServiceWorker listening to fetch events; 5. It is often used for offline support, speed up repeated access speed, preloading key resources and background update content; 6. When using it, you need to pay attention to cache version control, storage restrictions and the difference from HTTP caching mechanism.

IIFE (ImmediatelyInvokedFunctionExpression) is a function expression executed immediately after definition, used to isolate variables and avoid contaminating global scope. It is called by wrapping the function in parentheses to make it an expression and a pair of brackets immediately followed by it, such as (function(){/code/})();. Its core uses include: 1. Avoid variable conflicts and prevent duplication of naming between multiple scripts; 2. Create a private scope to make the internal variables invisible; 3. Modular code to facilitate initialization without exposing too many variables. Common writing methods include versions passed with parameters and versions of ES6 arrow function, but note that expressions and ties must be used.

Promise is the core mechanism for handling asynchronous operations in JavaScript. Understanding chain calls, error handling and combiners is the key to mastering their applications. 1. The chain call returns a new Promise through .then() to realize asynchronous process concatenation. Each .then() receives the previous result and can return a value or a Promise; 2. Error handling should use .catch() to catch exceptions to avoid silent failures, and can return the default value in catch to continue the process; 3. Combinators such as Promise.all() (successfully successful only after all success), Promise.race() (the first completion is returned) and Promise.allSettled() (waiting for all completions)
