This is our solution and implementation to problem #1010: Pairs of Songs With Total Durations Divisible by 60 on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Pairs of Songs With Total Durations Divisible by 60 on LeetCode.
Problem Analysis
We need to find all pairs of numbers that are divisible by 60. We could easily solve this using two loops: for each number, check every other number and see if it forms a pair, but this solution is inefficient. To make it more efficient, we can use an object to map a song duration, or its pair's duration, to the number of times it occurs.
However, we need to account for the fact that the pair's sum duration is divisible by 60, which means the duration itself can be 60, 120, 180, or any other multiple. Note that if two numbers x and y equal 60, then for any multiple m, m(x * y)=m * 60. Therefore, we can modulo each input number in time by 60 and check if subsequent duration pairs equal 60.
Implementation Strategy
We'll record the number of pairs numPairs and create a map partialPairs (though our implementation uses an array to map values). For each timeItem in time:
- Modulo timeItem by 60.
- Update numPairs by adding partialPairs[timeItem] to it.
- Set new variable pairPartner to (60 - timeItem) % 60 to calcualte the current item's required pair value. Modulo by 60 in case timeItem == 0 to account for that edge case.
- Increment partialPairs[pairPartner] so we can increment numPairs properly if we find it's pair partner in the future.
At the end, return numPairs.
Space and Time Complexity
The time complexity is O(n) where n is the number of items in time. This algorithm iterates through each item exactly once and partialPair lookups are in O(1) time. The space complexity is O(1) because the amount of space we use is bounded by the 60 seconds rule.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.