# Exercise: Find the Duplicate Songs

Users with big libraries say the "find duplicate songs" button never finishes: write a new one with the same answers that handles 200,000 songs in under 2 seconds, count what today's button costs, and name each one's growth rate.

Apprentice · Software Development · Updated November 17, 2026

By Gregor Dzierzon

Here's the ticket from the music app's support team:

> Users with big libraries say the "find duplicate songs" button never finishes. One user with 50,000 songs waited half a minute and gave up; a DJ with 200,000 songs can't use it at all. Small libraries are fine.
>
> 1. **The same answers as today:** every title that appears more than once, listed once, in A to Z order. Capital letters count: "Slow Rain" and "slow rain" are different titles.
> 2. **A library of 200,000 songs takes under 2 seconds.**
> 3. **The user's playlist keeps its own order.** The button may not rearrange it.

It's the friend from *Twice the Stuff, How Much More Work?* again, and the button from *Why the Duplicates Button Crawls: O(n²)*. Today's button is in the code you start from, and it's right; it's only too slow. You write a new one with the same answers, and the tests time it on 200,000 songs.

## Before you start

You need one language set up, as in *Setup: VS Code and Your Language*. The exercise is written in all five of the course's languages; pick the one you use.

## Get the exercise code

Open this lesson's GitHub repository, [github.com/ask-codey/exercise-big-o-duplicate-songs](https://github.com/ask-codey/exercise-big-o-duplicate-songs), also linked from the **Exercise** box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

```bash
git clone https://github.com/ask-codey/exercise-big-o-duplicate-songs.git
```

Git makes a folder, `exercise-big-o-duplicate-songs`, with the exercise code inside.

The repository has a folder for each language: `csharp`, `java`, `python`, `javascript` and `typescript`. Each folder holds:

- **your code:** one file with today's button and two functions to finish (the repository's `README.md` names the file for each language);
- **the tests** that check your functions. You don't need to change them;
- **a demo program** that tries both buttons on an eight-song playlist.

In VS Code, choose **File > Open Folder** and open **your language's folder**, not the whole repository.

## What's already there

Today's button is `findDuplicatesByPairs` (`FindDuplicatesByPairs` in C#, `find_duplicates_by_pairs` in Python). Here it is in Python, as the starter has it (the other languages say the same in their own syntax):

```python
def find_duplicates_by_pairs(songs):
    duplicates = []
    for first in range(len(songs)):
        for second in range(first + 1, len(songs)):
            if songs[first] == songs[second] and songs[first] not in duplicates:
                duplicates.append(songs[first])
    duplicates.sort()
    return duplicates
```

Leave it as it is: the tests compare your new button's answers with it.

## What to do

1. **Count what today's button costs.** Finish `pairChecks` (`pair_checks` in Python, `PairChecks` in C#): how many comparisons a playlist of a given size needs when every song is compared with every other song once.
2. **Write the new button.** Finish `findDuplicates` (`FindDuplicates` in C#, `find_duplicates` in Python): the same answers as today's button, each duplicated title once, in A to Z order, for 200,000 songs in under 2 seconds, without rearranging the playlist it's given.
3. **Name the growth rates.** On each function's **Growth rate:** line, today's button included, write its Big-O and a few words on why.

## Check your work

Each language has its own command, run in the terminal in your language's folder (**Terminal > New Terminal** in VS Code). The repository's `README.md` has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (`npm install`).

| Language | Run the tests | Run the demo |
|---|---|---|
| C# | `dotnet test` | `dotnet run --project DuplicateSongs` |
| Java | `./mvnw test` (`.\mvnw test` in PowerShell) | `java src/main/java/Demo.java` |
| Python | `python -m pytest` | `python demo.py` |
| JavaScript | `npm test` | `node demo.js` |
| TypeScript | `npm test` | `node demo.ts` |

At first all 7 tests fail. That's expected: each function you finish turns its tests green. A failing test's message starts with **Not yet:** and says what it expected, for example *Not yet: Slow Rain appears three times but is listed once, after Lemon Skies.* If your new button gives the right answers but takes too long, the last test says how long, for example *Not yet: 20000 songs took 5125 ms. The button has 2000 ms, even for 200000 songs.*

&lt;details>
&lt;summary>Stuck?&lt;/summary>

- **`pairChecks` is the comparison count** from *Why the Duplicates Button Crawls: O(n²)*: two loops, one inside the other, and a counter.
- **Why today's button is slow:** it compares every pair, so twice the songs is about four times the work. Any new button that compares every pair, in any order, has the same problem.
- **Where to look:** sort a **copy** of the playlist. After sorting, equal titles sit side by side, so you only ever compare a title with the one right before it. *Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ)* says why a good sort is fast.
- **A copy, not the playlist.** A new list made from the old one is a copy: `new List<string>(songs)` in C#, `new ArrayList<>(songs)` in Java, `sorted(songs)` or `list(songs)` in Python, `[...songs]` in JavaScript and TypeScript.
- **A title that appears three times is still one duplicate.** Before you add a title, check whether it's the last one you added. Checking the whole answer list is a search, and it makes the button slow again.
- **Stuck on a growth rate?** Count the loops, and use *Are Two Loops Twice as Slow? Why O(2n) Is Still O(n)* to decide which part counts.

&lt;/details>

## When you're done

Every test is green, and the demo prints the same four lines in every language:

```text
Playlist: Midnight Bus, Lemon Skies, Slow Rain, Lemon Skies, Paper Boats, Slow Rain, Neon Garden, Slow Rain
Pair checks for 8 songs: 28
Duplicates, today's code: Lemon Skies, Slow Rain
Duplicates, the new button: Lemon Skies, Slow Rain
```

&lt;details>
&lt;summary>Why Should I Choose This?&lt;/summary>

- **Today's button, every song against every other:** about 20 billion comparisons for 200,000 songs, O(n²). Measured on a laptop, it already takes about 5 seconds at 20,000 songs in Python, and 4 to 5 seconds at 60,000 in C#, Java and JavaScript.
- **Sort a copy, then compare neighbors:** the sort is O(n log n), about 3.6 million comparisons for 200,000 songs, and the walk along the sorted copy is O(n). Measured on the same laptop, 200,000 songs take 28 ms in Python and under 100 ms in every language.
- **What it costs:** a copy of the playlist, as much memory again as the playlist itself.
- **What would beat it:** a structure that remembers every title it has seen and answers "seen it before?" in one step, without sorting. That's a hash set, in Module 5, and it finds duplicates in a single pass, O(n).

&lt;/details>

## Where else does this shape show up?

You've replaced "compare every pair" with "sort first, then look at neighbors". Before you open the answers, think of three other places, at work or in daily life, where a job that seems to need every pair compared can be done by sorting first.

&lt;details>
&lt;summary>Some answers&lt;/summary>

- **Two students with the same birthday** in a school of 2,000: sort the birthdays, and any match sits side by side.
- **Duplicate customer emails** in a shop's mailing list: sort the emails, then walk the list once.
- **Two runners with the same finishing time:** sort the times, and ties are neighbors.
- **Merging two class rosters** to see who's on both: sort each, then walk them side by side.
- **Spotting a repeated ticket number** at an event: sort the numbers, and a repeat is right next to its twin.

&lt;/details>

## Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

1. On GitHub, click **+**, then **New repository**. Name it (for example `exercise-big-o-duplicate-songs`), choose **Public**, and click **Create repository**. Leave out the README: your folder already has one.
2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

   ```bash
   git remote set-url origin https://github.com/your-name/exercise-big-o-duplicate-songs.git
   git add .
   git commit -m "My solution"
   git push -u origin main
   ```

3. Paste your repo's address, such as `https://github.com/your-name/exercise-big-o-duplicate-songs`, into **Submit your exercise** on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

## So what

You kept the answers and changed the growth rate: from O(n²), which gave up at 50,000 songs, to O(n log n), which handles 200,000 in a blink. That's the everyday work of Big-O: not memorizing symbols, but noticing the nested loop and knowing there's a faster way. Module 5 shows a third way, with a hash set, that finds duplicates in a single pass.

## Key terms

- [Big-O Notation](https://www.ask-codey.com/glossary/big-o-notation)
- [Quadratic Time](https://www.ask-codey.com/glossary/quadratic-time)
- [Linearithmic Time](https://www.ask-codey.com/glossary/linearithmic-time)
- [Nested Loop](https://www.ask-codey.com/glossary/nested-loop-software-development)

## Related

- [Why the Duplicates Button Crawls: O(n²)](https://www.ask-codey.com/lessons/big-o-quadratic)
- [Sorting a Million Songs, and the Playlist You Can't Compute: O(n log n) and O(2ⁿ)](https://www.ask-codey.com/lessons/big-o-n-log-n-and-exponential)
- [Are Two Loops Twice as Slow? Why O(2n) Is Still O(n)](https://www.ask-codey.com/lessons/big-o-dropping-constants)

Source: https://www.ask-codey.com/lessons/exercise-big-o-duplicate-songs
