Problem

You are given two 2D integer arrays nums1 and nums2.

  • nums1[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.
  • nums2[i] = [idi, vali] indicate that the number with the id idi has a value equal to vali.

Each array contains unique ids and is sorted in ascending order by id.

Merge the two arrays into one array that is sorted in ascending order by id, respecting the following conditions:

  • Only ids that appear in at least one of the two arrays should be included in the resulting array.
  • Each id should be included only once and its value should be the sum of the values of this id in the two arrays. If the id does not exist in one of the two arrays, then assume its value in that array to be 0.

Return the resulting array. The returned array must be sorted in ascending order by id.

Examples

Example 1:

Input: nums1 = [[1,2],[2,3],[4,5]], nums2 = [[1,4],[3,2],[4,1]]
Output: [[1,6],[2,3],[3,2],[4,6]]
Explanation: The resulting array contains the following:
- id = 1, the value of this id is 2 + 4 = 6.
- id = 2, the value of this id is 3.
- id = 3, the value of this id is 2.
- id = 4, the value of this id is 5 + 1 = 6.

Example 2:

Input: nums1 = [[2,4],[3,6],[5,5]], nums2 = [[1,3],[4,3]]
Output: [[1,3],[2,4],[3,6],[4,3],[5,5]]
Explanation: There are no common ids, so we just include each id with its value in the resulting list.

Constraints:

  • 1 <= nums1.length, nums2.length <= 200
  • nums1[i].length == nums2[j].length == 2
  • 1 <= idi, vali <= 1000
  • Both arrays contain unique ids.
  • Both arrays are in strictly ascending order by id.

Solution

Method 1 - Two Pointer Technique

This is a typical two-pointer problem due to the sorted nature of the input arrays.

Initial Observation:

  • Both arrays are sorted by id.
  • We are required to merge both arrays such that:
    • For matching ids, their values are summed.
    • For ids existing in only one array, include the id with its respective value in the result.

Algorithm

  • Use two pointers i and j to traverse through nums1 and nums2, respectively.
  • Compare the ids at the current positions of both arrays:
    • If they are equal, sum their values, add to the result, and move both pointers forward.
    • If one id is smaller, add it to the result alone (assuming the other array does not have it), and move the pointer of the smaller array forward.
  • Add any remaining elements from either array to the result after the traversal.

Code

Java
class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        List<int[]> result = new ArrayList<>();
        int i = 0, j = 0;

        // Traverse both arrays
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i][0] == nums2[j][0]) {
                // If ids match, sum their values
                result.add(new int[]{nums1[i][0], nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (nums1[i][0] < nums2[j][0]) {
                // Add the id and value from nums1 if id in nums1 is smaller
                result.add(new int[]{nums1[i][0], nums1[i][1]});
                i++;
            } else {
                // Add the id and value from nums2 if id in nums2 is smaller
                result.add(new int[]{nums2[j][0], nums2[j][1]});
                j++;
            }
        }

        // Add remaining elements from nums1
        while (i < nums1.length) {
            result.add(new int[]{nums1[i][0], nums1[i][1]});
            i++;
        }

        // Add remaining elements from nums2
        while (j < nums2.length) {
            result.add(new int[]{nums2[j][0], nums2[j][1]});
            j++;
        }

        // Convert the result list to a 2D array
        return result.toArray(new int[result.size()][]);
    }
}
Python
class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        ans = []
        i, j = 0, 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i][0] == nums2[j][0]:
                ans.append([nums1[i][0], nums1[i][1] + nums2[j][1]])
                i += 1
                j += 1
            elif nums1[i][0] < nums2[j][0]:
                ans.append([nums1[i][0], nums1[i][1]])
                i += 1
            else:
                ans.append([nums2[j][0], nums2[j][1]])
                j += 1

        # Add remaining elements from nums1 or nums2
        while i < len(nums1):
            ans.append([nums1[i][0], nums1[i][1]])
            i += 1
        while j < len(nums2):
            ans.append([nums2[j][0], nums2[j][1]])
            j += 1
        
        return ans

Complexity

  • ⏰ Time complexity: O(m + n), where m and n are the sizes of nums1 and nums2, respectively. As the algorithm involves a single traversal of both arrays (since they are sorted).
  • 🧺 Space complexity: O(m + n) as we are storing the result.