mergeSortedArrays.md

Requirements

Given two sorted arrays, nums1 & nums2, merge nums2 into nums1 nums1 will have the indexs for nums2 pre-allocated, with values of 0 and the function arguments will include intgers m and n, where m refers to the total number of intergers in nums1, and n refers to the total number of integers in nums2 for example: nums1 = [1, 2, 3, 0, 0, 0] m = 3 nums2 = [4, 5, 6] n = 3

which should modify nums1 to equal [1, 2, 3, 4, 5, 6]

• input: array of integers: nums1, number of integers in nums1: m, array of integers: nums2, number of integers in nums2: n,
• output: nothing
• constraints: Don't return anything, o(1) space
• edge case: nums1 or nums2 is empty, duplicate integers

Strategy

Loop through nums1 backwards by i if both n and m are greater than or equal 0; compare the value of nums1[m] to nums2[n] set nums1[i] to whichever is greater and decrement it's total intergers value (m or n) else if m is greater than zero, break else set nums1[i] to nums2[n], and decrement n

Justification of strategy

Moving backwards keeps things easy as it ensures integers are only moved once, if we went forwards in scenarios like nums1 = [1, 2, 3, 0, 0, 0] and nums2 = [1, 2, 3], we would have to swap integers between nums1 and nums2 multiple times.

Define test cases

nums1 = [1, 2, 3, 0, 0, 0]; m = 3 nums2 = [4, 5, 6]; n = 3 expected = [1, 2, 3, 4, 5, 6];

nums1 = [1, 2, 3]; m = 3 nums2 = []; n = 0 expected = [1, 2, 3];

nums1 = [0, 0, 0]; m = 0 nums2 = [4, 5, 6]; n = 3 expected = [4, 5, 6];

nums1 = [1, 2, 3, 0, 0, 0]; m = 3 nums2 = [1, 2, 3]; n = 3 expected = [1, 1, 2, 2, 3, 3];

Implementation skeleton

• set m to m - 1;
• set n to n - 1
• for loop with i equal to nums1.length - 1;
  • if n and m are greater than or equal to zero
    • if nums1[m] is greater than nums2[n]
      • set nums1[i] to nums1[m]
      • decrement m
    • else
      • set nums1[i] to nums1[n]
      • decrement n else if m is greater than or equal to 0
    • break out of for loop else
    • set nums1[i] to nums1[n]
    • decrement n

Actual implementation

https://repl.it/@pmillssf/MergeSortedArray

Execute test cases

run https://repl.it/@pmillssf/MergeSortedArray

Big-O Analysis

Time: O(n + m)

Space: O(1)

Optimization (if applicable)