Domain 2MediumMEDIUM

Pairs of Songs With Total Durations Divisible by 60

Count pairs of songs where sum is divisible by 60 using a frequency map to track remainders modulo 60, achieving O(N) time complexity.

Domain: medium•Updated: 2026-09-06
#hash map#modular arithmetic#O(N)#constant space

Problem Breakdown

We need to count the number of index pairs (i, j) such that i < j and (time[i] + time[j]) % 60 == 0. The core challenge is doing this efficiently given NN up to 6×1046 \times 10^4, which rules out an O(N2)O(N^2) brute-force approach. Key observations:

  • Modular Arithmetic: (a + b) % k == 0 implies b % k = (k - a % k) % k. We only care about the remainder of each song duration when divided by 60.
  • Frequency Counting: Instead of checking every future element for every current element, we can maintain how many times each remainder has appeared so far.

Intuition

A brute-force solution checks all pairs (i,j)(i, j) which takes O(N2)O(N^2). To optimize to O(N)O(N):

  1. We iterate through the list once.
  2. For each song t, we calculate its remainder r = t % 60.
  3. The required complement remainder is (60 - r) % 60.
  4. If a previous song had this complement remainder, it forms valid pairs with the current song. We add the count of such songs to our total.
  5. Then we increment the frequency map for r so future songs can pair with it.

This transforms the problem into counting compatible remainders encountered previously in a single pass. The space complexity is effectively constant because there are only 60 possible remainder values (0-59).

Approach

  1. Initialize a counter total_pairs = 0.
  2. Use a hash map (remainder_counts) to store the frequency of each remainder encountered so far.
  3. Iterate through each duration t in time:
    • Compute rem = t % 60.
    • Calculate target complement: target = (60 - rem) % 60.
      • Note: If rem == 0, (60-0)%60 results in 0, correctly pairing multiples of 60 with each other.
    • Add the count of songs seen so far that have remainder equal to target into total_pairs.
    • Increment the frequency map for the current song’s remainder (rem).
  4. Return total_pairs.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the number of songs in the input list. We iterate through the array exactly once with constant-time dictionary operations (hashing).
  • Space Complexity: O(K)O(K) or effectively O(1)O(1). The hash map stores counts for remainders 0-59. Since there are only 60 possible distinct values, the space usage is bounded by a small constant regardless of input size NN (K=60K=60).

Solution

from typing import List
from collections import defaultdict

class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        # Frequency map to store count of remainders encountered so far. 
        # Using defaultdict(int) simplifies incrementing counts without checking existence first.
        remainder_counts = defaultdict(int)
        total_pairs = 0
        
        for t in time:
            rem = t % 60
            
            # Calculate the complement needed to sum up to a multiple of 60.
            # If rem is 0, target becomes (60-0)%60 -> 0. 
            # This correctly handles cases where we need another multiple of 60.
            target = (60 - rem) % 60
            
            # Add existing compatible pairs found before this song to the total count
            ans += remainder_counts[target]
            
            # Record current remainder for future songs to pair with
            counts[rem] += 1
            
        return ans

# Alternative concise implementation using standard dict if defaultdict is not preferred:
class Solution2:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        remainder_counts = {} 
        total_pairs = 0
        
        for t in time:
            rem = t % 60
            
            target = (60 - rem) % 60
            
            if target in remainder_counts:
                total_pairs += remainder_counts[target]
            
            # Update frequency map using .get() to handle initialization implicitly or explicit check
            remainder_counts[rem] = remainder_counts.get(rem, 0) + 1
            
        return total_pairs

# Final optimized version for submission (using defaultdict is cleaner):
class Solution:
    def numPairsDivisibleBy60(self, time: List[int]) -> int:
        counts = defaultdict(int)
        ans = 0
        
        for t in time:
            rem = t % 60
            target = (60 - rem) % 60
            
            # Add existing compatible pairs found before this song
            ans += counts[target]
            
            # Record current remainder for future songs to pair with
            counts[rem] += 1
            
        return ans

Edge Cases Handled

  • **Remainder Zero