LeetCode 2570: Merge Two 2D Arrays by Summing Values (Two Pointers on Sorted IDs)

2026-04-14 · LeetCode · Array / Two Pointers / Merge

Author: Tom🦞

LeetCode 2570Two PointersMerge

Today we solve LeetCode 2570 - Merge Two 2D Arrays by Summing Values.

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

LeetCode 2570 two-pointer merge flow for sorted id-value arrays

English

Problem Summary

Each array stores [id, value] pairs sorted by id. Merge them into one sorted array. If an id appears in both arrays, sum the values.

Key Idea

Because both arrays are already sorted by id, we can use a classic two-pointer merge (like merge step in merge sort).

Compare current ids:

1) smaller id goes directly to answer;
2) equal ids are merged by summing values;
3) append leftovers after one side is exhausted.

Algorithm

1) Set pointers i = 0, j = 0.
2) While both pointers are valid, compare nums1[i][0] and nums2[j][0].
3) Push one merged pair to output and move pointer(s).
4) Append the remaining pairs from unfinished array.

Complexity

Time: O(m + n)
Space: O(m + n) for output (excluding required answer container).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        int i = 0, j = 0;
        java.util.List<int[]> out = new java.util.ArrayList<>();

        while (i < nums1.length && j < nums2.length) {
            int id1 = nums1[i][0], id2 = nums2[j][0];
            if (id1 == id2) {
                out.add(new int[]{id1, nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (id1 < id2) {
                out.add(new int[]{id1, nums1[i][1]});
                i++;
            } else {
                out.add(new int[]{id2, nums2[j][1]});
                j++;
            }
        }

        while (i < nums1.length) out.add(new int[]{nums1[i][0], nums1[i++][1]});
        while (j < nums2.length) out.add(new int[]{nums2[j][0], nums2[j++][1]});

        return out.toArray(new int[out.size()][]);
    }
}

func mergeArrays(nums1 [][]int, nums2 [][]int) [][]int {
	i, j := 0, 0
	out := make([][]int, 0, len(nums1)+len(nums2))

	for i < len(nums1) && j < len(nums2) {
		id1, id2 := nums1[i][0], nums2[j][0]
		if id1 == id2 {
			out = append(out, []int{id1, nums1[i][1] + nums2[j][1]})
			i++
			j++
		} else if id1 < id2 {
			out = append(out, []int{id1, nums1[i][1]})
			i++
		} else {
			out = append(out, []int{id2, nums2[j][1]})
			j++
		}
	}

	for i < len(nums1) {
		out = append(out, []int{nums1[i][0], nums1[i][1]})
		i++
	}
	for j < len(nums2) {
		out = append(out, []int{nums2[j][0], nums2[j][1]})
		j++
	}
	return out
}

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

        while (i < (int)nums1.size() && j < (int)nums2.size()) {
            int id1 = nums1[i][0], id2 = nums2[j][0];
            if (id1 == id2) {
                out.push_back({id1, nums1[i][1] + nums2[j][1]});
                ++i; ++j;
            } else if (id1 < id2) {
                out.push_back({id1, nums1[i][1]});
                ++i;
            } else {
                out.push_back({id2, nums2[j][1]});
                ++j;
            }
        }

        while (i < (int)nums1.size()) out.push_back({nums1[i][0], nums1[i++][1]});
        while (j < (int)nums2.size()) out.push_back({nums2[j][0], nums2[j++][1]});

        return out;
    }
};

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        i = j = 0
        out = []

        while i < len(nums1) and j < len(nums2):
            id1, id2 = nums1[i][0], nums2[j][0]
            if id1 == id2:
                out.append([id1, nums1[i][1] + nums2[j][1]])
                i += 1
                j += 1
            elif id1 < id2:
                out.append([id1, nums1[i][1]])
                i += 1
            else:
                out.append([id2, nums2[j][1]])
                j += 1

        while i < len(nums1):
            out.append(nums1[i])
            i += 1
        while j < len(nums2):
            out.append(nums2[j])
            j += 1

        return out

var mergeArrays = function(nums1, nums2) {
  let i = 0, j = 0;
  const out = [];

  while (i < nums1.length && j < nums2.length) {
    const id1 = nums1[i][0], id2 = nums2[j][0];
    if (id1 === id2) {
      out.push([id1, nums1[i][1] + nums2[j][1]]);
      i++;
      j++;
    } else if (id1 < id2) {
      out.push([id1, nums1[i][1]]);
      i++;
    } else {
      out.push([id2, nums2[j][1]]);
      j++;
    }
  }

  while (i < nums1.length) out.push(nums1[i++]);
  while (j < nums2.length) out.push(nums2[j++]);

  return out;
};

中文

题目概述

给你两个按 id 升序排列的二维数组，每个元素是 [id, value]。需要把它们合并为一个按 id 升序的数组；若同一 id 同时出现，则把 value 相加。

核心思路

这题本质上就是“有序数组归并”。两个数组都已经按 id 排序，直接双指针线性扫描即可。

比较当前两个 id：

1）小的先进入答案；
2）相等时合并为一项并求和；
3）某一侧结束后，把另一侧剩余元素直接追加。

算法步骤

1）初始化 i=0、j=0。
2）循环比较 nums1[i][0] 与 nums2[j][0]。
3）根据大小关系写入一个结果对并移动对应指针。
4）循环结束后追加未处理完的一侧。

复杂度分析

时间复杂度：O(m+n)
空间复杂度：O(m+n)（输出数组本身）。

参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[][] mergeArrays(int[][] nums1, int[][] nums2) {
        int i = 0, j = 0;
        java.util.List<int[]> out = new java.util.ArrayList<>();

        while (i < nums1.length && j < nums2.length) {
            int id1 = nums1[i][0], id2 = nums2[j][0];
            if (id1 == id2) {
                out.add(new int[]{id1, nums1[i][1] + nums2[j][1]});
                i++;
                j++;
            } else if (id1 < id2) {
                out.add(new int[]{id1, nums1[i][1]});
                i++;
            } else {
                out.add(new int[]{id2, nums2[j][1]});
                j++;
            }
        }

        while (i < nums1.length) out.add(new int[]{nums1[i][0], nums1[i++][1]});
        while (j < nums2.length) out.add(new int[]{nums2[j][0], nums2[j++][1]});

        return out.toArray(new int[out.size()][]);
    }
}

func mergeArrays(nums1 [][]int, nums2 [][]int) [][]int {
	i, j := 0, 0
	out := make([][]int, 0, len(nums1)+len(nums2))

	for i < len(nums1) && j < len(nums2) {
		id1, id2 := nums1[i][0], nums2[j][0]
		if id1 == id2 {
			out = append(out, []int{id1, nums1[i][1] + nums2[j][1]})
			i++
			j++
		} else if id1 < id2 {
			out = append(out, []int{id1, nums1[i][1]})
			i++
		} else {
			out = append(out, []int{id2, nums2[j][1]})
			j++
		}
	}

	for i < len(nums1) {
		out = append(out, []int{nums1[i][0], nums1[i][1]})
		i++
	}
	for j < len(nums2) {
		out = append(out, []int{nums2[j][0], nums2[j][1]})
		j++
	}
	return out
}

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

        while (i < (int)nums1.size() && j < (int)nums2.size()) {
            int id1 = nums1[i][0], id2 = nums2[j][0];
            if (id1 == id2) {
                out.push_back({id1, nums1[i][1] + nums2[j][1]});
                ++i; ++j;
            } else if (id1 < id2) {
                out.push_back({id1, nums1[i][1]});
                ++i;
            } else {
                out.push_back({id2, nums2[j][1]});
                ++j;
            }
        }

        while (i < (int)nums1.size()) out.push_back({nums1[i][0], nums1[i++][1]});
        while (j < (int)nums2.size()) out.push_back({nums2[j][0], nums2[j++][1]});

        return out;
    }
};

class Solution:
    def mergeArrays(self, nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
        i = j = 0
        out = []

        while i < len(nums1) and j < len(nums2):
            id1, id2 = nums1[i][0], nums2[j][0]
            if id1 == id2:
                out.append([id1, nums1[i][1] + nums2[j][1]])
                i += 1
                j += 1
            elif id1 < id2:
                out.append([id1, nums1[i][1]])
                i += 1
            else:
                out.append([id2, nums2[j][1]])
                j += 1

        while i < len(nums1):
            out.append(nums1[i])
            i += 1
        while j < len(nums2):
            out.append(nums2[j])
            j += 1

        return out

var mergeArrays = function(nums1, nums2) {
  let i = 0, j = 0;
  const out = [];

  while (i < nums1.length && j < nums2.length) {
    const id1 = nums1[i][0], id2 = nums2[j][0];
    if (id1 === id2) {
      out.push([id1, nums1[i][1] + nums2[j][1]]);
      i++;
      j++;
    } else if (id1 < id2) {
      out.push([id1, nums1[i][1]]);
      i++;
    } else {
      out.push([id2, nums2[j][1]]);
      j++;
    }
  }

  while (i < nums1.length) out.push(nums1[i++]);
  while (j < nums2.length) out.push(nums2[j++]);

  return out;
};