Skip to content

4001. Aggregate Two Time Series

Description

You are given two 2D integer arrays series1 and series2.

Each element in both series is of the form [timestamp, value], where:

  • timestamp is an integer representing the time.
  • value is an integer representing the value at that timestamp.

Each array is sorted in strictly increasing order of timestamp.

For any timestamp not present in a series, its value is taken from the next available timestamp in the same series if one exists. Otherwise, its value is considered 0.

The aggregated series is formed by summing the corresponding values from both series at every timestamp that appears in either series.

Return the aggregated series as a 2D integer array of [timestamp, summedValue] pairs, sorted in strictly increasing order of timestamp.

Β 

Example 1:

Input: series1 = [[1,3],[4,1]], series2 = [[2,2],[5,2]]

Output: [[1,5],[2,3],[4,3],[5,2]]

Explanation:

Timestamp series1 series2 summedValue
1 3 2 5
2 1 2 3
4 1 2 3
5 0 2 2

Thus, the aggregated series is [[1, 5], [2, 3], [4, 3], [5, 2]].

Example 2:

Input: series1 = [[1,5],[3,1]], series2 = [[2,2]]

Output: [[1,7],[2,3],[3,1]]

Explanation:

Timestamp series1 series2 summedValue
1 5 2 7
2 1 2 3
3 1 0 1

Thus, the aggregated series is [[1, 7], [2, 3], [3, 1]].

Example 3:

Input: series1 = [[1,5]], series2 = [[1000000000,2]]

Output: [[1,7],[1000000000,2]]

Explanation:

At timestamp 1, the next available value in series2 is 2 at timestamp 1000000000. At timestamp 1000000000, there is no later timestamp in series1, so its value is 0. Only timestamps that appear in at least one of the two series are included.

Β 

Constraints:

  • 1 <= series1.length, series2.length <= 105
  • series1[i].length == series2[i].length == 2
  • 1 <= series1[i][0], series2[i][0] <= 109
  • 1 <= series1[i][1], series2[i][1] <= 109
  • Each series is sorted in strictly increasing order of timestamp.

Solutions

Solution 1: Two Pointers

Both series are strictly increasing by timestamp, so they can be merged with two pointers. Taking the value of the next later timestamp for a missing timestamp is equivalent to: the value at the current pointer can be used directly for earlier missing timestamps in that series.

Let pointers \(i\) and \(j\) point to the two series. While both are not exhausted:

  • If \(t_1 = t_2\), output \([t_1, v_1 + v_2]\) and advance both pointers;
  • If \(t_1 < t_2\), output \([t_1, v_1 + v_2]\) (series2 uses the current later \(v_2\)) and advance only \(i\);
  • If \(t_2 < t_1\), handle symmetrically.

After one series is exhausted, append the remaining points of the other series directly (there is no later timestamp on the opposite side, so its value is \(0\)).

The time complexity is \(O(m + n)\), and the space complexity is \(O(m + n)\), where \(m\) and \(n\) are the lengths of the two series.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def aggregateTimeSeries(
        self, series1: list[list[int]], series2: list[list[int]]
    ) -> list[list[int]]:
        m, n = len(series1), len(series2)
        i = j = 0
        ans = []
        while i < m and j < n:
            t1, v1 = series1[i]
            t2, v2 = series2[j]
            if t1 == t2:
                ans.append([t1, v1 + v2])
                i += 1
                j += 1
            elif t1 < t2:
                ans.append([t1, v1 + v2])
                i += 1
            else:
                ans.append([t2, v1 + v2])
                j += 1
        while i < m:
            ans.append(series1[i])
            i += 1
        while j < n:
            ans.append(series2[j])
            j += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> aggregateTimeSeries(int[][] series1, int[][] series2) {
        int m = series1.length, n = series2.length;
        int i = 0, j = 0;
        List<List<Integer>> ans = new ArrayList<>();

        while (i < m && j < n) {
            int t1 = series1[i][0], v1 = series1[i][1];
            int t2 = series2[j][0], v2 = series2[j][1];

            if (t1 == t2) {
                ans.add(List.of(t1, v1 + v2));
                i++;
                j++;
            } else if (t1 < t2) {
                ans.add(List.of(t1, v1 + v2));
                i++;
            } else {
                ans.add(List.of(t2, v1 + v2));
                j++;
            }
        }

        while (i < m) {
            ans.add(List.of(series1[i][0], series1[i][1]));
            i++;
        }

        while (j < n) {
            ans.add(List.of(series2[j][0], series2[j][1]));
            j++;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<vector<int>> aggregateTimeSeries(vector<vector<int>>& series1, vector<vector<int>>& series2) {
        int m = series1.size(), n = series2.size();
        int i = 0, j = 0;
        vector<vector<int>> ans;

        while (i < m && j < n) {
            int t1 = series1[i][0], v1 = series1[i][1];
            int t2 = series2[j][0], v2 = series2[j][1];

            if (t1 == t2) {
                ans.push_back({t1, v1 + v2});
                i++;
                j++;
            } else if (t1 < t2) {
                ans.push_back({t1, v1 + v2});
                i++;
            } else {
                ans.push_back({t2, v1 + v2});
                j++;
            }
        }

        while (i < m) {
            ans.push_back(series1[i]);
            i++;
        }

        while (j < n) {
            ans.push_back(series2[j]);
            j++;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func aggregateTimeSeries(series1 [][]int, series2 [][]int) [][]int {
    m, n := len(series1), len(series2)
    i, j := 0, 0
    ans := make([][]int, 0)

    for i < m && j < n {
        t1, v1 := series1[i][0], series1[i][1]
        t2, v2 := series2[j][0], series2[j][1]

        if t1 == t2 {
            ans = append(ans, []int{t1, v1 + v2})
            i++
            j++
        } else if t1 < t2 {
            ans = append(ans, []int{t1, v1 + v2})
            i++
        } else {
            ans = append(ans, []int{t2, v1 + v2})
            j++
        }
    }

    for i < m {
        ans = append(ans, series1[i])
        i++
    }

    for j < n {
        ans = append(ans, series2[j])
        j++
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function aggregateTimeSeries(series1: number[][], series2: number[][]): number[][] {
    const m = series1.length;
    const n = series2.length;
    let i = 0;
    let j = 0;
    const ans: number[][] = [];

    while (i < m && j < n) {
        const [t1, v1] = series1[i];
        const [t2, v2] = series2[j];

        if (t1 === t2) {
            ans.push([t1, v1 + v2]);
            i++;
            j++;
        } else if (t1 < t2) {
            ans.push([t1, v1 + v2]);
            i++;
        } else {
            ans.push([t2, v1 + v2]);
            j++;
        }
    }

    while (i < m) {
        ans.push(series1[i]);
        i++;
    }

    while (j < n) {
        ans.push(series2[j]);
        j++;
    }

    return ans;
}

Comments