Popular Song Pairs - codepath/compsci_guides GitHub Wiki

Unit 2 Session 1 (Click for link to problem statements)

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Q: What is the problem asking for?

  • A: The problem asks to return the number of popular song pairs in an array of integers where a pair (i, j) is considered popular if the songs have the same popularity score and i < j.

• Q: What are the inputs?

  • A: An array popularity_scores of integers representing the popularity scores of songs.

• Q: What are the outputs?

  • A: An integer representing the number of popular song pairs.

• Q: Are there any constraints on the values in the array?

  • A: The values can be any integers.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a dictionary to count occurrences of each popularity score and then calculate the number of pairs using combination formula.

1) Initialize an empty dictionary `score_count` to count occurrences of each popularity score.
2) Iterate through the `popularity_scores` array.
   - For each score, update its count in the `score_count` dictionary.
3) Initialize a variable `popular_pairs` to 0.
4) Iterate through the values in the `score_count` dictionary.
   - For each count greater than 1, add the number of pairs `(count * (count - 1)) // 2` to `popular_pairs`.
5) Return the value of `popular_pairs`.

⚠️ Common Mistakes

• Ensure that the counts are correctly calculated.
• Handle cases where no popular pairs exist by returning 0.

I-mplement

def num_popular_pairs(popularity_scores):
    # Step 1: Count occurrences of each score
    score_count = {}
    for score in popularity_scores:
        if score in score_count:
            score_count[score] += 1
        else:
            score_count[score] = 1
    
    # Step 2: Calculate the number of popular pairs
    popular_pairs = 0
    for count in score_count.values():
        if count > 1:
            popular_pairs += (count * (count - 1)) // 2
    
    return popular_pairs