2570. Merge Two 2D Arrays by Summing Values

MediumView on LeetCode

Array Hash Table Two Pointers

Time: O(n + m)

Space: O(n + m)

Intuition

Merge two sorted lists, removing elements in both. Subtract list2 from list1, combine, sort.

Algorithm

1Convert list2 to set. Remove from list1 any in set. Remove from list2 any in list1-set. Merge remaining.

Common Pitfalls

•Remove elements appearing in BOTH lists. Merge and sort the remainders.

2570.cs

// Approach: Two-pointer merge of sorted arrays; sum values with matching ids.
// Time: O(n + m) Space: O(n + m)

public class Solution
{
    public int[][] MergeArrays(int[][] nums1, int[][] nums2)
    {
        const int kMax = 1000;
        List<int[]> ans = new List<int[]>();
        int[] count = new int[kMax + 1];

        AddCount(nums1, count);
        AddCount(nums2, count);

        for (int i = 1; i <= kMax; ++i)
        {
            if (count[i] > 0)
                ans.Add(new int[] { i, count[i] });
        }

        return ans.ToArray();
    }

    private void AddCount(int[][] nums, int[] count)
    {
        foreach (int[] idAndVal in nums)
        {
            int id = idAndVal[0];
            int val = idAndVal[1];
            count[id] += val;
        }
    }
}

Was this solution helpful?