Merge Sorted Array – Leetcode #88

Problem Statement

This problem is from Leetcode – Merge Sorted Array. The problem statement in short is as below:

Merge two sorted arrays nums1 and nums2 into nums1 in-place. nums1 has length m + n with the first m elements valid; nums2 has length n.

Solution

Approach-1

1. Add elements of second array in the first array.
2. Sort the first array.

See the code sample below:

   /*
 		Input Data:
  		int nums1[] = {1,2,3,0,0,0};
		int m = 3;
		int nums2[] = {2,5,6};
		int n = 3;
    */
public void merge(int[] nums1, int m, int[] nums2, int n) {
		
		// add elements of second array into first array
		for(int i=0; i<n; i++) {

			nums1[m] = nums2[i];
			m++;
		}
		
		// sort first array
		Arrays.sort(nums1);
	}

You can check out the code from Github here: Merge Sorted Arrays – First Approach

PERFORMANCE ANALYSIS

RUNTIME	1 ms | Beats 28.62 %
MEMORY	42.28 MB | Beats 60.17 %
TIME COMPLEXITY	O (N)

Approach-2

1. Add elements of first array in an ArrayList.
2. Add elements of second array in same ArrayList.
3. Sort the ArrayList.
4. Now iterate over the ArrayList and overwrite the first array.

See the code snippet below:

      /*
		Input Data:
		int nums1[] = {1,2,3,0,0,0};
		int m = 3;
		int nums2[] = {2,5,6};
		int n = 3;
	 */
	public void merge(int[] nums1, int m, int[] nums2, int n) {

  // Create an arraylist. We'll push all numbers from both given arrays into this arrayList
		List numList = new ArrayList<>();
		
		// Push all numbers from first array into the arrayList
		for(int i=0; i<m; i++ ) {

			numList.add(nums1[i]);
		}

		// Push all numbers from second array into the arrayList
		for(int i=0; i<n; i++ ) {

			numList.add(nums2[i]);
		}
		
		// Now sort this arrayList
		Collections.sort(numList);
		
		// Finally iterate the arraylist and populate the first array
		m=0;
		Iterator iter = numList.iterator();
		while(iter.hasNext()) {

			int num = (int) iter.next();
			//System.out.println(num);

			nums1[m] = num;
			m++;
		}

	}

You can checkout the code from Github here: Merge Sorted Arrays – Second Approach

See the outcome of this approach in terms of memory usage below:

PERFORMANCE ANALYSIS

RUNTIME	1 ms | Beats 33.61 %
MEMORY	41.86 MB | Beats 81.00 %
TIME COMPLEXITY	O (N)