To merge two sorted arrays of integers, we need to compare the elements of both the arrays and add them to a new array in a sorted manner. The simplest approach to merge sorted arrays is to create a new array, iterate through both arrays with two pointer variables initialized at the beginning of each array, compare the elements of both, add the smaller element to the new array, and move the pointer to the next element of the array with the smaller element. The time complexity of this merge algorithm is O(m+n) because both arrays need to be iterated only once. Here's the implementation of the `merge_sorted_arrays` function having time complexity O(m+n) using the approach mentioned above.
```pythondef merge_sorted_arrays(arr1, arr2): m = len(arr1) n = len(arr2) i, j = 0, 0 merged = [] while i < m and j < n: if arr1[i] <= arr2[j]: merged.append(arr1[i]) i += 1 else: merged.append(arr2[j]) j += 1 while i < m: merged.append(arr1[i]) i += 1 while j < n: merged.append(arr2[j]) j += 1 return merged
```In this implementation, two pointer variables `i` and `j` are initialized at the beginning of each array. Then, the elements of both arrays are compared and the smaller element is appended to the `merged` array. The pointer variable of the array with the smaller element is moved to the next element. If one of the arrays is completely traversed, the remaining elements in the other array are appended to the `merged` array.We have used three loops in the implementation. The first loop iterates over both arrays until they are completely traversed. The other two loops iterate over the elements of only one array. Therefore, this is a sample solution to the Google interview question that requires merging two sorted arrays of integers having time complexity of O(m+n).References:- [Merge Two Sorted Arrays in Python](https://medium.com/@souravdey_87706/merge-two-sorted-arrays-in-python-4e4afd837a60)- [Time Complexity of Algorithms](https://www.geeksforgeeks.org/time-complexity-of-algorithms/)