Algorithm Practice: Merge Sorted Array

Problem

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[i] <= 109

Solutions

Approach 1 : Merge and sort

var merge = function(nums1, m, nums2, n) {

for (let i = 0; i < n; i++) {
nums1[i + m] = nums2[i];
}
nums1.sort((a,b) => a-b);
};
  • Time complexity : O((n+m)log(n+m)).
  • Space complexity : O(n), but it can vary.

Approach 2 : Three Pointers (Start From the Beginning)
Intuition

  • Initialize nums1Copy to be a new array containing the first m values of nums1.
  • Initialize read pointer p1 to the beginning of nums1Copy.
  • Initialize read pointer p2 to the beginning of nums2.
  • Initialize write pointer p to the beginning of nums1.
  • While p is still within nums1:
  • If nums1Copy[p1] exists and is less than or equal to nums2[p2]:
  • Else — Write nums2[p2] into nums1[p], and increment p2 by 1.
  • Increment p by 1.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// Make a copy of the first m elements of nums1.
int[] nums1Copy = new int[m];
for (int i = 0; i < m; i++) {
nums1Copy[i] = nums1[i];
}
// Read pointers for nums1Copy and nums2 respectively.
int p1 = 0;
int p2 = 0;

// Compare elements from nums1Copy and nums2 and write the smallest to nums1.
for (int p = 0; p < m + n; p++) {
// We also need to ensure that p1 and p2 aren't over the boundaries of their respective arrays.
if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
nums1[p] = nums1Copy[p1++];
} else {
nums1[p] = nums2[p2++];
}
}
}
}
  • Time complexity : O(n+m).
  • Space complexity :O(m).

Approach 3 : Three Pointers (Start From the End)

var merge = function(nums1, m, nums2, n) {

let p1 = m-1
let p2 = n-1
for(let p = m + n - 1; p >= 0; p--){
if(p2 < 0){
break
}
if(p1 >= 0 && nums1[p1] > nums2[p2]){
nums1[p] = nums1[p1--]
}else{
nums1[p] = nums2[p2--]
}
}
};
//pointer 1 start at end of m
//pointer 2 start at end of n
//pointer 3 start at total length (minus 1 for index 0) aka end of list, and move left after each iteration
//stop if we complete 2nd pointer values
// if ( we run out of 1st pointer vals and val of nums at p1 is greater than nums2 at p2)
//replace value of nums1 at p(pointer 3) with nums1[p1] then reduce p1 value
// replace value of nums1 at p(pointer 3, end of list) with nums2[p2] then reduce p2 value
  • Time complexity : O(n+m).
  • Space complexity : O(1).

Conclusion

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Crypto Trading Bots and the Emergence of Trading Intelligence

graph of Bitcoin trading that shows Bitcoin’s collapse on March 12th, 2020

Application Tuning in go: Benchmarks

Build a Real-Time Data Dashboard with 9 Lines of Code

All about Anime

Examples of EC2 Instance Metadata results

Let’s Build a Web App! Week 7 out of 30

KAI Software builds amazing apps for its clients & uses Maestro to deploy them to any server

Tutorial Fuzzy Logic Mamdani for Arduino

Tutorial Fuzzy Logic Mamdani for Arduino

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
SunJet Liu

SunJet Liu

More from Medium

Memory Management in Computer System

Difference Between Compiler, Interpreter and Assembler

Problem with Anemic Domain Models

Software Learning Approach : Reference to Finite Element Analysis Software Packages