BruteForce.
Straight forward solution.
Time complexity O(nlogn).
Space complexity O(n).
Where n is total numbers from arr1 and arr2.
Idea: Combine both arrays and sort them.
- Create a new array(mergedArray) with size of arr1.length + arr2.length
- Add all numbers from arr1 and arr2 into mergedArray.
- Use library Arrays.sort(mergedArray) to sort the array.
- Return the mergedArray.
/**
* Merge two sorted array
* BruteForce Time Complexity O(nlogn) Space Complexity O(n) where n is the sum of the arr1 and arr2 size
* @param arr1 the first sorted array
* @param arr2 the second sorted array
* @return int[] merged sorted array from arr1 and arr2
*/
public static int[] mergeArraysUsingSort(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
int writer = 0;
int[] mergedArray = new int[n + m];
// Add all nums from arr1 to mergedArray
for(int num : arr1) {
mergedArray[writer++] = num;
}
// Add all nums from arr2 to mergedArray
for(int num : arr2) {
mergedArray[writer++] = num;
}
Arrays.sort(mergedArray);
return mergedArray;
}
Optimal solution.
Time complexity O(n).
Space complexity O(n).
Where n is total numbers from arr1 and arr2.
Since the given arr1 and arr2 were already sorted, we can take advantage of it.
Idea: Create an empty array with the combined length of both arrays. Loop from left to right compare value and store the minimum to the new array.
- Create a new array(mergedArray) with size of arr1.length + arr2.length
- Create three variables with index 0: writer, readerOne, and readerTwo. Writer is for writing value to mergedArray. ReaderOne and ReaderTwo both getting values from their respective array.
-
While there is value to read we are writing the value to mergedArray. There are 2 scenarios to handle.
First: readerOne and readerTwo both have values to read.
* Compare both values. Store the minimum value into the mergedArray. * Increment both minimum reader and writer index by 1Second: either readerOne or readerTwo has a value to read.
* Store the available value to mergedArray * Increment both available reader and writer index by 1 Return the mergedArray
/**
* Merge two sorted array
* Time Complexity O(n + m) Space Complexity O(n + m) where n
is the size of arr1 and m is the size of arr2
* @param arr1 the first sorted array
* @param arr2 the second sorted array
* @return int[] merged sorted array from arr1 and arr2
*/
public static int[] mergeArrays(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
int[] mergedArray = new int[n + m];
int readerOne = 0;
int readerTwo = 0;
int writer = 0;
while(readerOne < n || readerTwo < m) {
// Scenario 2
// Handle Scenario 2 first because Scenario 1 might be out of index.
if(readerOne >= n) {
mergedArray[writer++] = arr2[readerTwo++];
} else if (readerTwo >= m) {
mergedArray[writer++] = arr1[readerOne++];
} else {
// Scenario 1
if(arr1[readerOne] < arr2[readerTwo]) {
mergedArray[writer++] = arr1[readerOne++];
} else {
mergedArray[writer++] = arr2[readerTwo++];
}
}
}
return mergedArray;
}
LEETCODE
Given two sorted array nums1 and nums2. Merge the nums2 into nums1. Nums1 will have enough space to store nums2.
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
The idea is similar as above, but we are doing opposite. Instead of storing minimum value to the left side we are storing the maximum value to the right side of nums1 until either readerOne or readerTwo reaches out of index.
- Note: If readerTwo is not out index means these remaining values are the smallest, therefore just write them directly to nums1.
- Since we are directly modifying the array nums1, so space complexity is O(1).
/**
* Merge two sorted array LeetCode Problem
* Link: https://leetcode.com/problems/merge-sorted-array
* Time Complexity O(n + m) Space Complexity O(1) where n is the size of nums1 and m is the size of nums2
* @param nums1 sorted array with enough space to fill nums2
* @param m original size of the nums1
* @param nums2 sorted array that needs to be combined to nums1
* @param n the size of the nums2
*/
public void mergeArraysLeetCode(int[] nums1, int m, int[] nums2, int n) {
int writer = nums1.length - 1;
int readerOne = m - 1;
int readerTwo = n - 1;
while(readerOne >= 0 && readerTwo >= 0){
if(nums1[readerOne] < nums2[readerTwo]){
nums1[writer] = nums2[readerTwo--];
} else {
nums1[writer] = nums1[readerOne--];
}
writer--;
}
// Add remaning nums from nums2 to nums1. These values are smallest.
while(readerTwo >= 0){
nums1[writer--] = nums2[readerTwo--];
}
}
Top comments (0)