LeetCode 1010 - Pairs of Songs With Total Durations Divisible by 60

LeetCode Problem 1010

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to find pairs of songs whose total duration is divisible by 60. Specifically, we are given an array time where each element represents the length of a song in seconds. We need to count all unique pairs (i, j) where i < j and (time[i] + time[j]) % 60 == 0.

The input array has a length of up to 60,000, and each song's duration is between 1 and 500 seconds. This implies that a naive brute-force approach that checks every pair would require up to roughly 1.8 billion operations in the worst case (n*(n-1)/2), which is too slow.

Edge cases include situations where all durations are multiples of 60, all durations are the same but not divisible by 60, or the array has only one element. The problem guarantees at least one element, so we do not need to handle an empty array.

Approaches

The brute-force approach involves iterating over all pairs (i, j) and checking if their sum is divisible by 60. This guarantees correctness because it literally checks every possible pair. However, its time complexity is O(n²), which is infeasible for n up to 60,000.

The optimal approach uses modular arithmetic and a hash map (or array of size 60) to count remainders. The key insight is that for any two numbers a and b, (a + b) % 60 == 0 if and only if (a % 60 + b % 60) % 60 == 0. Therefore, for each song, we can compute its remainder modulo 60 and check how many previously seen songs have a complementary remainder (60 - remainder) % 60. This allows us to count valid pairs in a single pass, reducing the complexity to O(n).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair explicitly
Optimal	O(n)	O(60) = O(1)	Uses modulo and frequency counts to find complementary pairs

Algorithm Walkthrough

1. Initialize an array remainders of size 60 to store the count of songs for each possible remainder modulo 60. Also initialize a variable count to zero for the total number of valid pairs.
2. Iterate through each song duration in time.
3. For each duration, compute remainder = duration % 60.
4. Compute the complementary remainder needed to form a sum divisible by 60: complement = (60 - remainder) % 60.
5. Add the count of previously seen songs with the complementary remainder to count.
6. Increment the count for the current remainder in the remainders array.
7. After iterating through all songs, return the total count.

Why it works: The algorithm works because for each song, we are directly counting all valid pairs that can be formed with songs already seen. Using modular arithmetic ensures we only check sums divisible by 60, and the hash array keeps track of all previous remainders efficiently.

Python Solution

from typing import List

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainders = [0] * 60
        count = 0
        for t in time:
            remainder = t % 60
            complement = (60 - remainder) % 60
            count += remainders[complement]
            remainders[remainder] += 1
        return count

The Python implementation uses a fixed-size array remainders to count the occurrences of each remainder modulo 60. For each song, it calculates the complement needed to reach a multiple of 60 and immediately adds the number of such previous songs to the total count. This ensures every pair is counted exactly once, and the array update ensures future songs can form valid pairs with it.

Go Solution

func numPairsDivisibleBy60(time []int) int {
    remainders := make([]int, 60)
    count := 0
    for _, t := range time {
        remainder := t % 60
        complement := (60 - remainder) % 60
        count += remainders[complement]
        remainders[remainder]++
    }
    return count
}

The Go implementation mirrors the Python version. Go slices handle indexing and dynamic updates efficiently. The main difference is that Go requires explicit slice initialization with make. The algorithmic logic remains identical.

Worked Examples

Example 1: time = [30, 20, 150, 100, 40]

Step	Song Duration	Remainder	Complement	Remainders Array (partial)	Count
1	30	30	30	[0,...,0,30:0,...]	0
2	20	20	40	[0,...,20:1,...]	0
3	150	30	30	[0,...,30:1,...]	1
4	100	40	20	[0,...,40:1,...]	2
5	40	40	20	[0,...,40:2,...]	3

Result: 3

Example 2: time = [60, 60, 60]

Step	Song Duration	Remainder	Complement	Remainders Array	Count
1	60	0	0	[1,...]	0
2	60	0	0	[2,...]	1
3	60	0	0	[3,...]	3

Result: 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each song is processed exactly once
Space	O(1)	Remainders array has fixed size 60

The time complexity is linear in the number of songs since we perform constant-time operations per song. The space complexity is constant because the remainder array size does not scale with input size.

Test Cases

# Provided examples
assert Solution().numPairsDivisibleBy60([30,20,150,100,40]) == 3  # mix of divisible and non-divisible
assert Solution().numPairsDivisibleBy60([60,60,60]) == 3          # all multiples of 60

# Edge and boundary cases
assert Solution().numPairsDivisibleBy60([1]) == 0                  # single element
assert Solution().numPairsDivisibleBy60([1,59]) == 1               # sums exactly 60
assert Solution().numPairsDivisibleBy60([1,2,3,4,5,6]) == 0        # no divisible sums
assert Solution().numPairsDivisibleBy60([60]*1000) == 499500       # all multiples of 60, large input
assert Solution().numPairsDivisibleBy60([30,30,30,30]) == 6        # multiple identical remainders

Test	Why
[30,20,150,100,40]	Validates general case with mixed durations
[60,60,60]	Tests all multiples of 60
[1]	Single element edge case
[1,59]	Minimal pair summing to 60
[1,2,3,4,5,6]	No pairs sum divisible by 60
[60]*1000	Large input stress test
[30,30,30,30]	Multiple identical remainders

Edge Cases

One important edge case is when all durations are multiples of 60. Each pair of songs forms a valid combination, and the algorithm handles this because the complement of remainder 0 is 0 itself, and the array count correctly accumulates prior songs.

Another edge case occurs when a pair sums to exactly 60 but the numbers themselves are not multiples of 60. For instance, [1, 59] forms a valid pair. The modulo arithmetic ensures that such complements are correctly calculated.

A third edge case is the minimum input size, where the array has only one song. Since there cannot be a pair, the function correctly returns 0. This is important to prevent indexing or counting errors.

These edge cases demonstrate the robustness of the remainder-based counting approach.