[LeetCode] 2570. Merge Two 2D Arrays by Summing Values

Problem

https://leetcode.com/problems/merge-two-2d-arrays-by-summing-values/

Leetcode - Merge Two 2D Arrays by Summing Values

Type - array, two pointers, greedy

Difficulty - Easy

Approach & Solution

data structures & variables:

• ans: merged array

• n: size of the array nums1.

• m: size of the array nums1.

• i: index for nums1 to be appended.

• j: index for nums2 to be appended.

Follow these steps while i < n || i < m:

1. if i >= n(nums1 is finished), append nums2[j] to ans add j by 1.

2. else if j >= m(nums1 is finished), append nums1[i] to ans add i by 1.

3. else,

   1. if nums1[i][0] (id) is smaller than nums2[j][0], append nums[i] to ans and add i by 1.

   2. else if nums1[i][0] (id) is greater than nums2[j][0], append nums[j] to ans and add j by 1.

   3. else, two ids are same. so, append({id, nums1[i][1] + nums1[j][1])}).

Complexity

Time Complexity: O(n+m) - Iterating num1 and nums2 by once.

Space Complexity: O(n+m) - in worst case, length of ans is n+m.

Code (C++ | Go)

class Solution {
public:
    vector<vector<int>> mergeArrays(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
        int n = nums1.size();
        int m = nums2.size();
        int i = 0;
        int j = 0;

        vector<vector<int>> ans;

        while(i < n || j < m) {
            if(i >= n) {
                ans.push_back(nums2[j]);
                j++;
            } else if(j >= m) {
                ans.push_back(nums1[i]);
                i++;
            } else {
                if(nums1[i][0] < nums2[j][0]) {
                    ans.push_back(nums1[i]);
                    i++;
                } else if(nums1[i][0] > nums2[j][0]) {
                    ans.push_back(nums2[j]);
                    j++;
                } else {
                    ans.push_back({nums1[i][0], nums1[i][1] + nums2[j][1]});
                    i++;
                    j++;
                }
            }
        }

        return ans;
    }
};

func mergeArrays(nums1 [][]int, nums2 [][]int) [][]int {
    n := len(nums1)
    m := len(nums2)
    i := 0
    j := 0

    ans := make([][]int, 0)

    for i < n || j < m {
        if i >= n {
            ans = append(ans, nums2[j])
            j++
        } else if j >= m {
            ans = append(ans, nums1[i])
            i++
        } else {
            if nums1[i][0] < nums2[j][0] {
                ans = append(ans, nums1[i])
                i++
            } else if nums1[i][0] > nums2[j][0] {
                ans = append(ans, nums2[j])
                j++
            } else {
                ans = append(ans, []int{nums1[i][0], nums1[i][1] + nums2[j][1]})
                i++;
                j++;
            }
        }
    }

    return ans
}