Problem Statement:

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.

Test Cases:

Example 1:

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.
Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Approach

From the given constraints, we can say one thing which is length of nums1 is greater than length of nums2.
So one of the straight forward approach will be to store all the elements to an extra space like ArrayList, sort that ArrayList and then put back all the elements to nums1. In this case, we are actually applying sorting which makes **NlogN **complexity where N = m + n.
But let us again recheck, do we actually need an extra space and do additional sorting as we already have 2 sorted array.
More optimised way will be to use 3 variables say i, j, k where

i = m - 1
j = n - 1
k = m + n - 1

Now just have a traversal until i greater than or equal to 0 and j greater than or equal to 0 and do a check for the following :

-> if nums1[i] is greater than nums2[j], store nums1[i] to nums1[k] and decrease i and k.
-> else store nums2[j] to nums1[k] and decrease j and k.

There can be cases where there are some left out elements in nums2. So just make sure we cover all elements with an extra while loop until j ≥ 0 and store those elements to nums[k] as those will be the largest numbers that are remaining with us to be merged.

Time and Space Complexity

Here we are traversing through the arrays of length m and n. So our time complexity will be O(m + n).

We are not making use of any extra space. So our space complexity will be O(1).

Please correct me if I made any mistake.

Code