LeetCode 1699 - Number of Calls Between Two Persons

This problem provides a database table named Calls, where each row represents a phone call between two people. The table contains three columns: | Column | Meaning | | --- | --- | | fromid | The caller | | toid | The receiver | | duration | Duration of the call | The important…

leetcodemediumdatabase

LeetCode Problem 1699

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem provides a database table named Calls, where each row represents a phone call between two people. The table contains three columns:

Column Meaning
from_id The caller
to_id The receiver
duration Duration of the call

The important detail is that calls are directional in the raw data, but the final result should treat calls between two people as belonging to the same pair regardless of direction.

For example, these two rows:

(1, 2, 59)
(2, 1, 11)

both describe communication between persons 1 and 2. The problem asks us to combine them into a single aggregated result.

The required output should contain:

Column Meaning
person1 Smaller person id
person2 Larger person id
call_count Total number of calls between them
total_duration Sum of durations of all calls between them

The condition person1 < person2 guarantees that each unordered pair appears exactly once in the result.

The table does not contain a primary key, which means duplicate rows are allowed. We must count every row independently, including duplicates. This is important because repeated records represent multiple calls and should contribute to both the count and the duration total.

The constraints are relatively straightforward because this is a SQL aggregation problem rather than an algorithmic optimization problem. The main challenge is correctly normalizing each pair so that:

(1, 2)
(2, 1)

are grouped together.

A naive implementation might mistakenly treat these as separate groups. Another common mistake is forgetting to enforce the ordering condition person1 < person2.

Important edge cases include:

  • Calls appearing in both directions between the same users
  • Duplicate call records
  • Multiple distinct pairs in the dataset
  • Pairs with only a single call
  • Large durations that must still sum correctly

The problem guarantees that from_id != to_id, so self-calls never occur.

Approaches

Brute Force Approach

A brute-force approach would attempt to compare every row with every other row and manually determine whether they belong to the same unordered pair.

For each call, we could:

  1. Normalize the pair into (min(from_id, to_id), max(from_id, to_id))
  2. Search through previously processed pairs
  3. Update counts and durations if found
  4. Otherwise create a new group

If implemented poorly with repeated scanning through groups, this could become inefficient because each insertion may require a linear search through existing groups.

Although this approach eventually produces the correct answer, it scales poorly as the number of records increases.

Optimal Approach

The key observation is that calls are symmetric with respect to the two participants. The pair:

(from_id, to_id)

should always be converted into:

(LEAST(from_id, to_id), GREATEST(from_id, to_id))

Once every row is normalized into a canonical ordering, standard SQL aggregation becomes very simple.

We can:

  1. Normalize each pair
  2. Group by the normalized pair
  3. Count rows
  4. Sum durations

This transforms the problem into a straightforward GROUP BY query.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly scans existing groups
Optimal O(n) O(n) Uses SQL grouping after pair normalization

Algorithm Walkthrough

  1. For every row in the Calls table, determine the smaller and larger user IDs.

We use:

LEAST(from_id, to_id)
GREATEST(from_id, to_id)

This ensures every unordered pair always has the same representation. 2. Store the smaller ID as person1 and the larger ID as person2.

This satisfies the requirement that:

person1 < person2
  1. Group all rows by (person1, person2).

After normalization, calls in both directions belong to the same group. 4. Count the number of rows in each group.

Each row represents one call, including duplicates. 5. Sum the duration column for each group.

This gives the total communication time between the two users. 6. Return the grouped results.

Why it works

The algorithm works because every unordered pair of users is converted into a unique canonical representation. Both (1,2) and (2,1) become (1,2). Therefore, all calls between the same two people are grouped together correctly. Aggregation functions then compute the required totals over each group.

Python Solution

Although this is a database problem, LeetCode database solutions are written in SQL. The following is the complete SQL solution.

SELECT
    LEAST(from_id, to_id) AS person1,
    GREATEST(from_id, to_id) AS person2,
    COUNT(*) AS call_count,
    SUM(duration) AS total_duration
FROM Calls
GROUP BY
    LEAST(from_id, to_id),
    GREATEST(from_id, to_id);

The query begins by normalizing each pair of users. The LEAST() function always selects the smaller ID, while GREATEST() selects the larger one. This guarantees that calls in opposite directions map to the same pair.

Next, the query groups rows using the normalized pair. Once grouped, COUNT(*) computes the total number of calls, while SUM(duration) computes the combined duration.

Because duplicates are preserved in SQL aggregation, repeated rows are counted correctly.

Go Solution

LeetCode database problems do not require Go implementations because the expected submission language is SQL. However, the equivalent logic in Go can be represented as follows.

package main

import "fmt"

type Call struct {
	FromID  int
	ToID    int
	Duration int
}

type PairStats struct {
	Person1      int
	Person2      int
	CallCount    int
	TotalDuration int
}

func normalize(a, b int) (int, int) {
	if a < b {
		return a, b
	}
	return b, a
}

func aggregateCalls(calls []Call) []PairStats {
	statsMap := make(map[[2]int]*PairStats)

	for _, call := range calls {
		p1, p2 := normalize(call.FromID, call.ToID)

		key := [2]int{p1, p2}

		if _, exists := statsMap[key]; !exists {
			statsMap[key] = &PairStats{
				Person1: p1,
				Person2: p2,
			}
		}

		statsMap[key].CallCount++
		statsMap[key].TotalDuration += call.Duration
	}

	result := []PairStats{}

	for _, stats := range statsMap {
		result = append(result, *stats)
	}

	return result
}

func main() {
	calls := []Call{
		{1, 2, 59},
		{2, 1, 11},
		{1, 3, 20},
		{3, 4, 100},
		{3, 4, 200},
		{3, 4, 200},
		{4, 3, 499},
	}

	result := aggregateCalls(calls)

	for _, r := range result {
		fmt.Println(r)
	}
}

The Go implementation uses a hash map keyed by a normalized pair of IDs. This mirrors the SQL grouping behavior. Arrays are used as map keys because fixed-size arrays in Go are comparable and hashable.

Unlike Python dictionaries, Go maps require explicit existence checks before updating values.

Worked Examples

Example 1

Input:

+---------+-------+----------+
| from_id | to_id | duration |
+---------+-------+----------+
| 1       | 2     | 59       |
| 2       | 1     | 11       |
| 1       | 3     | 20       |
| 3       | 4     | 100      |
| 3       | 4     | 200      |
| 3       | 4     | 200      |
| 4       | 3     | 499      |
+---------+-------+----------+

Step 1, Normalize Pairs

Original Pair Normalized Pair Duration
(1,2) (1,2) 59
(2,1) (1,2) 11
(1,3) (1,3) 20
(3,4) (3,4) 100
(3,4) (3,4) 200
(3,4) (3,4) 200
(4,3) (3,4) 499

Step 2, Group and Aggregate

Pair (1,2)

Metric Value
Call Count 2
Total Duration 59 + 11 = 70

Pair (1,3)

Metric Value
Call Count 1
Total Duration 20

Pair (3,4)

Metric Value
Call Count 4
Total Duration 100 + 200 + 200 + 499 = 999

Final Output

person1 person2 call_count total_duration
1 2 2 70
1 3 1 20
3 4 4 999

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed once
Space O(n) Grouping may store all unique pairs

The solution scans the table exactly one time. Each row performs constant-time normalization and aggregation operations. The number of groups can grow up to the number of unique unordered pairs, which gives linear auxiliary storage in the worst case.

Test Cases

def normalize(a, b):
    return (min(a, b), max(a, b))

def aggregate(calls):
    result = {}

    for from_id, to_id, duration in calls:
        pair = normalize(from_id, to_id)

        if pair not in result:
            result[pair] = [0, 0]

        result[pair][0] += 1
        result[pair][1] += duration

    return result

# Provided example
calls = [
    (1, 2, 59),
    (2, 1, 11),
    (1, 3, 20),
    (3, 4, 100),
    (3, 4, 200),
    (3, 4, 200),
    (4, 3, 499),
]

expected = {
    (1, 2): [2, 70],
    (1, 3): [1, 20],
    (3, 4): [4, 999],
}

assert aggregate(calls) == expected  # standard mixed example

# Single call
calls = [
    (5, 7, 30),
]

expected = {
    (5, 7): [1, 30],
}

assert aggregate(calls) == expected  # single pair single call

# Opposite directions
calls = [
    (1, 2, 10),
    (2, 1, 15),
]

expected = {
    (1, 2): [2, 25],
}

assert aggregate(calls) == expected  # bidirectional normalization

# Duplicate rows
calls = [
    (3, 4, 100),
    (3, 4, 100),
    (4, 3, 100),
]

expected = {
    (3, 4): [3, 300],
}

assert aggregate(calls) == expected  # duplicates counted independently

# Multiple independent groups
calls = [
    (1, 2, 10),
    (3, 4, 20),
    (5, 6, 30),
]

expected = {
    (1, 2): [1, 10],
    (3, 4): [1, 20],
    (5, 6): [1, 30],
}

assert aggregate(calls) == expected  # separate groups

# Large durations
calls = [
    (1, 2, 1000000),
    (2, 1, 2000000),
]

expected = {
    (1, 2): [2, 3000000],
}

assert aggregate(calls) == expected  # large sum handling

Test Case Summary

Test Why
Provided example Verifies normal aggregation behavior
Single call Tests minimal valid input
Opposite directions Ensures pair normalization works
Duplicate rows Confirms duplicates are counted
Multiple independent groups Verifies separate grouping
Large durations Tests large aggregation sums

Edge Cases

One important edge case is bidirectional calls. A naive implementation might treat (1,2) and (2,1) as different groups. This would incorrectly split the aggregation into two rows. The implementation avoids this by always normalizing pairs using LEAST() and GREATEST().

Another important edge case is duplicate records. Since the table does not have a primary key, identical rows may appear multiple times. Some implementations mistakenly remove duplicates before aggregation. This would undercount both the number of calls and the total duration. The correct implementation counts every row independently using COUNT(*).

A third important edge case is pairs with only one call. Aggregation logic must still produce a valid row even when only one record exists for a pair. The grouping operation naturally handles this because a group with one row still produces correct count and duration values.

A final edge case involves large duration values. If many calls exist between the same pair, the total duration may become large. SQL aggregate functions handle this safely, and the Go implementation uses integer accumulation directly without truncation or floating-point conversion.