Merge Sorted Array – Leetcode #88

Problem Statement

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

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of 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

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: