# Exercise: Build a Growing Array

The music app crashes on the 9th song of an 8-slot playlist: build a playlist that takes any number of songs, adds a million in under 2 seconds and opens any song at once, with tests on every edge, and name each method's Big-O.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

Here's the ticket from the music app's product lead:

> Our playlists live in a plain array of 8 slots, and the 9th song crashes the app. People have playlists of thousands of songs, so the new playlist has to grow.
>
> 1. **No limit.** A playlist takes as many songs as people add: 9, 10,000 or a million.
> 2. **Adding stays quick.** A million songs, added one after another, in under 2 seconds.
> 3. **Any song opens at once** by its number, however long the playlist is: Shuffle jumps straight to song 500,000.
> 4. **Songs go in and come out anywhere,** at the top, in the middle or at the end, and the others keep their order.
> 5. **Phones are short of memory.** Start with 2 slots. When every slot is full, the platform team's rule is to move to an array twice the size; removing songs never shrinks it.

You've met every piece of this in the chapter, and now you build the whole playlist, without your language's list doing the growing for you. The tests check every edge (the front, the end, a full array, an index with no song), then add a million songs against the clock.

## 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-ds-growing-array](https://github.com/ask-codey/exercise-ds-growing-array), 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-ds-growing-array.git
```

Git makes a folder, `exercise-ds-growing-array`, 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 a `Playlist` class and four methods to finish (the repository's `README.md` names the file for each language);
- **the tests** that check your methods. You don't need to change them;
- **a demo program** that tries your playlist with five songs.

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

## What to do

The `Playlist` class already has an array of 2 slots, a count of songs, and `count` and `capacity` to read them. Its four methods are there with their parameters, and do nothing or return an empty string for now. The comment above each one says what it should do, with examples, and ends with a **Big-O:** line. Here is `get` in Python, as the starter has it (the other languages say the same in their own syntax):

```python
class Playlist:
    def __init__(self):
        self._slots = [None] * 2
        self._count = 0

    def get(self, index):
        """
        Return the song at this index, counting from 0. An index below 0, or
        at or past the count, has no song: raise an IndexError.
        A spare slot isn't a song, even though the slot exists.

        With Midnight Bus, Lemon Skies, Slow Rain: get(1) -> "Lemon Skies"
        get(3) -> IndexError

        Big-O: (write it here)
        """
        return ""
```

1. **Add at the end.** Finish `add` (`Add` in C#). Put the song in the next free slot. When every slot is full, make a new array twice the size, copy every song across in order, and use it from then on.
2. **Read by index.** Finish `get`. Return the song at the index, and throw your language's index error (`ArgumentOutOfRangeException` in C#, `IndexOutOfBoundsException` in Java, `IndexError` in Python, `RangeError` in JavaScript and TypeScript) for an index with no song.
3. **Insert at an index.** Finish `insertAt` (`insert_at` in Python). Move the songs from that index onward one slot right, then put the new song in. An index equal to the count adds at the end.
4. **Remove at an index.** Finish `removeAt` (`remove_at`). Return the song you took out, and move the songs after it one slot left.
5. **Name the costs.** On each method's **Big-O:** line, write its Big-O and a few words on why.

Keep the songs in the class's own array. Your language's list would do the growing for you, and doing it yourself is the point.

## 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 GrowingArray` |
| 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 9 tests fail. That's expected: each method you finish turns its tests green. A failing test's message starts with **Not yet:** and says what it expected, for example *Not yet: the third song finds the array full, so the capacity doubles to 4.* The last test adds a million songs and stops once it passes 2 seconds, saying how many songs it got through.

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

- **Start with `add` and `get`.** Most tests use them to fill and read the playlist, so they unlock the others.
- **Moving day is its own small job.** Write a private helper that makes the bigger array and copies the songs across; `add` and `insertAt` both call it when the array is full.
- **When inserting, move songs from the far end first.** Start at the last song and work back toward the index, as in *Jump to Song 500: Arrays*, or each song overwrites the next before it has moved.
- **A spare slot isn't a song.** Check an index against the count, not the capacity. For inserting, the count itself is allowed (that's the end); one past it isn't.
- **Removing doesn't shrink the array.** The capacity stays the same, as in your language's list.
- **The million songs ran out of time?** Count your moving days. *Is Adding a Song Slow? Amortized Cost* shows why their size matters.

&lt;/details>

## When you're done

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

```text
Added: Midnight Bus, Lemon Skies, Slow Rain, Paper Boats, Neon Garden
Count: 5, capacity: 8
Inserted Golden Hour at 0: Golden Hour, Midnight Bus, Lemon Skies, Slow Rain, Paper Boats, Neon Garden
Removed index 2: Lemon Skies
Now: Golden Hour, Midnight Bus, Slow Rain, Paper Boats, Neon Garden
Index 3: Paper Boats
```

Now look back at your four methods. Which ones would you call happily on a playlist of a million songs, and which ones would you avoid calling in a loop? Compare your **Big-O:** lines with the cost card in *Why Does This Loop Take Seconds? Your Language's List*.

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

The test adds a million songs, one after another. Here's what the other plans would have cost:

- **One fixed array, made huge:** every add is instant until the cap, then the app crashes again, and a 3-song playlist still holds a million slots of memory.
- **Grow by one slot each time:** every add copies every song so far, about 500 billion copies for a million songs. O(n²): it never finishes.
- **Grow by 100 slots each time:** still O(n²), about 5 billion copies. On the test's clock it was stopped at 2 seconds after 110,000 songs in Python and 520,000 in Java.
- **Double:** 19 moving days and 1,048,574 copies for the million songs, about one copy per song. Each add is O(1) on average, and the test takes a fraction of a second.

What it gives up: right after a move, up to half the slots stand empty, and adding at the top still moves every song. That last one is the next chapter's problem.

&lt;/details>

## Where else does this shape show up?

You've built "keep things side by side, rent more room than you need, and move rarely". Before you open the answers, think of three other places, in apps or in daily life, where a collection starts small, keeps growing, and is read by its position.

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

- **A chat's message history** grows all day and scrolls to message 1,000 at once.
- **A shopping cart** takes one more item at a time, and shows item 3 without searching.
- **A text editor's line of characters** grows as you type; jumping to character 5,000 is one step.
- **A hash table** moves to an array twice the size when it gets crowded: you'll build that in Module 5, *Exercise: Build a Coat Check*.
- **A family that keeps outgrowing its apartment** and rents one twice the size, so moving day stays rare.

&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-ds-growing-array`), 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-ds-growing-array.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-ds-growing-array`, 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've built the structure behind every `List`, `ArrayList`, `list` and `Array` you'll ever use, edges and all, and you've seen with a stopwatch why it doubles. The next time a list is slow, you'll know whether it's scooting songs over or quietly moving apartments, and which call to change.

## Key terms

- [Dynamic Array](https://www.ask-codey.com/glossary/dynamic-array)
- [Capacity](https://www.ask-codey.com/glossary/capacity)
- [Amortized Cost](https://www.ask-codey.com/glossary/amortized-cost)
- [Array](https://www.ask-codey.com/glossary/array-data-structures)

## Related

- [Jump to Song 500: Arrays](https://www.ask-codey.com/lessons/ds-arrays)
- [The Ninth Song Won't Fit: Growing Arrays](https://www.ask-codey.com/lessons/ds-dynamic-arrays)
- [Is Adding a Song Slow? Amortized Cost](https://www.ask-codey.com/lessons/ds-amortized-cost)

Source: https://www.ask-codey.com/lessons/exercise-ds-growing-array
