88. Merge Sorted Array

 

Efficiently Merging Two Sorted Arrays in JavaScript

Introduction

When working with arrays in JavaScript, a common task is to merge two sorted arrays into one sorted array. This challenge is frequently encountered in coding interviews and competitive programming. Today, we'll explore an efficient and elegant solution to this problem using a two-pointer technique.

Problem Statement

You are given two sorted integer arrays nums1 and nums2, where nums1 has a size of m + n to accommodate the elements of nums2 at its end. Our goal is to merge these arrays into a single sorted array in place.

Intuition

The arrays are already sorted, so we can leverage this property to our advantage. By starting from the end of both arrays, we can efficiently place the largest elements at the end of nums1, ensuring the array remains sorted. This approach minimizes the need for additional space and makes the merging process straightforward.

Approach

  1. Initialize Pointers:

    • i points to the last element of the valid entries in nums1 (m - 1).

    • j points to the last element of nums2 (n - 1).

    • k points to the last position of the merged array in nums1 (m + n - 1).

  2. Merge Process:

    • Use a while loop to iterate until all elements in nums2 are processed (j >= 0).

    • Compare elements from the end of both arrays:

      • If nums1[i] is greater than or equal to nums2[j], place nums1[i] at position k and decrement i.

      • Otherwise, place nums2[j] at position k and decrement j.

    • Decrement k after placing each element.

This ensures that the larger elements are placed correctly from the end, thus sorting the merged array in place without needing extra space.

Code Implementation

Here's the JavaScript code to achieve this:

javascript
var merge = function(nums1, m, nums2, n) {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;
    while(j >= 0) {
        if(i >= 0 && nums1[i] >= nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
};

Complexity Analysis

  • Time Complexity: O(m+n)O(m + n)

    • The algorithm makes a single pass through both arrays, ensuring each element is processed exactly once.

  • Space Complexity: O(1)O(1)

    • The merging is done in place within nums1, so no additional space is required.

Conclusion

By leveraging the two-pointer technique, we efficiently merge two sorted arrays in place with optimal time and space complexity. This method ensures that we only make one pass through each array, making it both time-efficient and space-efficient. This approach is not only elegant but also practical for real-world applications where managing memory is crucial.

For more insights and detailed solutions, you can check out this discussion on LeetCode: Merge Sorted Array - LeetCode.

I hope this solution helps you understand how to merge sorted arrays efficiently. Feel free to try this code on your own and tweak it as necessary. Happy coding! šŸ˜Š

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more