Abstract / Summary

Find how many pairs of songs have combined durations divisible by 60 using their remainders when divided by 60.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 54% (600k+ submissions).

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of counting unordered pairs of song durations whose total length is a multiple of 60 seconds. It builds a frequency map of the input values, then iterates over possible total sums that are multiples of 60, pairing values that complement each other to reach each target sum. The algorithm carefully avoids double-counting and correctly handles cases where both elements of a pair have the same duration.

Key Steps

Building the frequency dictionary

freq = defaultdict(int)
for t in time:
    freq[t] += 1

A defaultdict of integers records how many times each distinct song length appears. This structure enables O(1) look-ups for any duration and eliminates the need for explicit existence checks before incrementing a count.

Enumerating candidate total sums

for total in range(60, 1000, 60):

The outer loop walks through all multiples of 60 that could be formed by adding two song lengths. The lower bound of 60 excludes the trivial zero-sum case, while the upper bound of 1000 (exclusive) covers the maximum possible sum given the problem constraints (each duration is at most 500, so the largest sum is 1000). By restricting the iteration to these specific totals, the code avoids examining irrelevant combinations, which reduces the number of inner-loop checks dramatically.

Pairing complementary durations

j = total - i
if i <= j and j in freq:

For each distinct duration i present in the frequency map, the algorithm computes the complementary value j that would complete the current target sum. The condition i <= j guarantees that each unordered pair is considered only once, preventing double counting. The membership test j in freq ensures that only existing durations are paired, avoiding unnecessary arithmetic with absent keys.

Counting pairs without self-match

if i == j:
    result += sum(range(freq[i]))
else:
    result += freq[i] * freq[j]

When the two durations are identical (i == j), the number of valid pairs equals the triangular number of the frequency, i.e., the count of ways to choose two distinct indices from freq[i] items. The expression sum(range(freq[i])) computes this value without invoking a separate combinatorial function. For distinct durations, the product freq[i] * freq[j] directly yields the number of cross-pairs, because each occurrence of i can be paired with each occurrence of j.

Returning the final count

return result

After all relevant totals have been processed, the accumulated result holds the total number of unordered pairs whose sum is divisible by 60.

Edge Cases Handled

The algorithm explicitly addresses the scenario where both songs in a pair have the same length. By using the triangular number calculation, it correctly counts combinations such as two songs of length 30 seconds (which sum to 60) without mistakenly counting a song paired with itself.

It also gracefully handles inputs containing duplicate durations of any value, because the frequency map aggregates all occurrences before any pairing logic is applied.

When the input list is empty or contains a single element, the frequency map will have at most one key, and the inner loops will never satisfy the i <= j and j in freq condition for a distinct partner, resulting in a final count of zero, which is the correct outcome.

If the list includes durations that are themselves multiples of 60, the algorithm still processes them correctly: for a duration i that is a multiple of 60, the complementary value j for a target sum equal to i will be zero, which is not present in the frequency map, so no invalid pair is counted. For larger target sums, the complementary value will be another multiple of 60, and the same pairing logic applies.

Performance Optimizations

The use of a defaultdict eliminates the overhead of conditional key existence checks during frequency construction, allowing a single pass over the input list.

Limiting the outer loop to multiples of 60 up to the maximum possible sum reduces the search space from a naïve O(N²) enumeration to a bounded number of iterations (specifically, 16 iterations for the range 60-960). This bound is independent of the input size, making the algorithm scale linearly with the number of distinct durations rather than with the total number of elements.

The i <= j guard removes the need for a separate visited-set or post-processing step to eliminate duplicate pair counts.

Computing the triangular number via sum(range(freq[i])) leverages Python’s built-in arithmetic on small integer ranges, which is efficient for the typical frequency values encountered in this problem.

Overall, the combination of frequency aggregation, constrained total-sum enumeration, and careful pair counting yields a solution that runs quickly even for large input arrays while keeping memory usage modest, limited primarily to the frequency dictionary.

Imagine a big toy box filled with building blocks. Each block has a number on it representing how long a song lasts. The goal is to find pairs of these song blocks that can be linked together to make a group that adds up to exactly sixty seconds long.

First, the code look at all the blocks and counts how many of each size are in the box. This makes it easy to know if there are three blocks of the same size or maybe five blocks of another size.

Then, the code starts looking for pairs. It picks a song size and figures out what other number it needs to reach sixty. If a song is ten seconds long, it looks for another song that is fifty seconds long to make that perfect sixty-second group. It keeps track of these numbers so it can count how many special pairs exist.

If it finds two different sizes that add up to sixty, it multiplies the number of blocks of each size together to see how many total pairs can be made. If it is looking at a special size that is exactly thirty seconds, it needs to find other thirty-second blocks. Because it cannot use the same block twice, it carefully calculates how many ways to pair those thirty-second blocks without ever using the same one twice. As it goes through all the possibilities, it keeps a running tally of every pair found until it has checked every single option.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java		Go	Rust	TS
	LeetcodeHelp	C++	Python		Java
	Progiez	C++	Python		Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai				Java
	fpdjsns	C++
	Garvit244		Python
	halfrost						Go
	JoshCrozier					JS
	keineahnung2345	C++
	lkwq007		Python
	MacJim	C++
	shreymehul			C#
	suxrobGM			C#
	trung-hn		Python
	varunu28				Java
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
fpdjsns	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
MacJim	C++
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality