Design a Todo List - Solution & Explanation

Q: Is Design a Todo List easy or hard?

Design a Todo List is considered a Medium difficulty problem. The logic is straightforward, but choosing the right combination of data structures to keep tasks ordered while supporting efficient updates requires careful design.

Q: Design a Todo List Python/Java solution

In Python, you can combine dictionaries with a sorted container (like heap or sorted list implementations) to maintain due-date ordering. In Java, a HashMap with TreeSet works well because TreeSet keeps elements sorted with O(log n) insertion and deletion.

Q: How to solve Design a Todo List in O(log n)?

Use a hash table mapping each user to a sorted data structure keyed by due date. When a task is added, insert it into the sorted set so ordering is preserved automatically. During queries, iterate through the sorted tasks and filter by tag and completion status without performing an extra sorting step.

Q: What is the best approach for Design a Todo List?

The most efficient approach uses a hash table combined with a sorted set (such as TreeSet or balanced BST). The hash table stores task metadata while the sorted set keeps tasks ordered by due date. This allows task insertion in O(log n) time and efficient retrieval of pending tasks without running a full sort.

Q: Is Design a Todo List asked at Google/Amazon/Meta?

Design-style data structure questions like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The problem evaluates your ability to design efficient APIs, combine hash tables with ordered structures, and reason about operation complexity.

Q: What data structure is used in Design a Todo List?

The core data structures are a hash table for mapping users and tasks, and a sorted set (TreeSet, balanced BST, or ordered structure) to maintain tasks sorted by due date. Arrays or lists may also be used for storing task metadata like tags.

Q: What is the time complexity of Design a Todo List?

With the optimized design, adding a task takes O(log n) due to insertion into a sorted set. Completing a task is O(1) if you update a status map. Retrieving tasks is typically O(k + log n), where k is the number of tasks returned, because the structure is already ordered.

MediumPremiumFree on FleetCodeArray Hash Table String Design11 min readAsked at: Bloomberg

Practice this problem

Problem Statement

Design a Todo List Where users can add tasks, mark them as complete, or get a list of pending tasks. Users can also add tags to tasks and can filter the tasks by certain tags.

Implement the TodoList class:

TodoList() Initializes the object.
int addTask(int userId, String taskDescription, int dueDate, List<String> tags) Adds a task for the user with the ID userId with a due date equal to dueDate and a list of tags attached to the task. The return value is the ID of the task. This ID starts at 1 and is sequentially increasing. That is, the first task's id should be 1, the second task's id should be 2, and so on.
List<String> getAllTasks(int userId) Returns a list of all the tasks not marked as complete for the user with ID userId, ordered by the due date. You should return an empty list if the user has no uncompleted tasks.
List<String> getTasksForTag(int userId, String tag) Returns a list of all the tasks that are not marked as complete for the user with the ID userId and have tag as one of their tags, ordered by their due date. Return an empty list if no such task exists.
void completeTask(int userId, int taskId) Marks the task with the ID taskId as completed only if the task exists and the user with the ID userId has this task, and it is uncompleted.

Example 1:

Input
["TodoList", "addTask", "addTask", "getAllTasks", "getAllTasks", "addTask", "getTasksForTag", "completeTask", "completeTask", "getTasksForTag", "getAllTasks"]
[[], [1, "Task1", 50, []], [1, "Task2", 100, ["P1"]], [1], [5], [1, "Task3", 30, ["P1"]], [1, "P1"], [5, 1], [1, 2], [1, "P1"], [1]]
Output
[null, 1, 2, ["Task1", "Task2"], [], 3, ["Task3", "Task2"], null, null, ["Task3"], ["Task3", "Task1"]]

Explanation
TodoList todoList = new TodoList();
todoList.addTask(1, "Task1", 50, []); // return 1. This adds a new task for the user with id 1.
todoList.addTask(1, "Task2", 100, ["P1"]); // return 2. This adds another task for the user with id 1.
todoList.getAllTasks(1); // return ["Task1", "Task2"]. User 1 has two uncompleted tasks so far.
todoList.getAllTasks(5); // return []. User 5 does not have any tasks so far.
todoList.addTask(1, "Task3", 30, ["P1"]); // return 3. This adds another task for the user with id 1.
todoList.getTasksForTag(1, "P1"); // return ["Task3", "Task2"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1.
todoList.completeTask(5, 1); // This does nothing, since task 1 does not belong to user 5.
todoList.completeTask(1, 2); // This marks task 2 as completed.
todoList.getTasksForTag(1, "P1"); // return ["Task3"]. This returns the uncompleted tasks that have the tag "P1" for the user with id 1.
                                  // Notice that we did not include "Task2" because it is completed now.
todoList.getAllTasks(1); // return ["Task3", "Task1"]. User 1 now has 2 uncompleted tasks.

Constraints:

1 <= userId, taskId, dueDate <= 100
0 <= tags.length <= 100
1 <= taskDescription.length <= 50
1 <= tags[i].length, tag.length <= 20
All dueDate values are unique.
All the strings consist of lowercase and uppercase English letters and digits.
At most 100 calls will be made for each method.

Approach Overview

Problem Overview: Design a Todo List system that supports adding tasks, marking tasks as completed, and retrieving a user’s pending tasks filtered by tags. Returned tasks must be ordered by due date. The challenge is maintaining fast updates while keeping tasks sorted.

Approach 1: Hash Table + On-Demand Sorting (Add O(1), Query O(n log n))

Store all tasks in a hash table keyed by userId. Each user maps to a list or array of tasks containing taskId, dueDate, tags, and completion status. Adding a task is constant time since you simply append to the user’s list. When fetching tasks, iterate through the list, filter out completed tasks and tasks without the requested tag, then sort the remaining tasks by dueDate using a sorting algorithm.

This approach is simple and easy to implement, but retrieval becomes expensive as the number of tasks grows. Every query requires scanning all tasks and performing a sort. For large task lists or frequent queries, the O(n log n) query cost becomes the bottleneck.

Approach 2: Hash Table + Sorted Set (Add O(log n), Query O(k + log n))

Maintain a hash table mapping each userId to a sorted structure keyed by dueDate. A sorted set (or TreeSet / balanced BST) keeps tasks ordered automatically. Each entry stores dueDate and taskId so ordering is preserved without running a full sort. Another hash table tracks task metadata (tags and completion state) for quick lookup.

When you add a task, insert it into the user’s sorted set. The structure ensures tasks remain ordered by dueDate in O(log n) time. Completing a task simply updates its status in the metadata table. When retrieving tasks, iterate through the sorted set from earliest dueDate, skip completed tasks, and filter by tag. Since the structure is already sorted, no additional sorting step is required.

This design separates ordering from metadata storage. The sorted set handles ordering efficiently, while the hash map provides constant-time lookups for task details. The result is predictable performance even with many tasks.

Recommended for interviews: The Hash Table + Sorted Set design is the expected solution. It demonstrates understanding of system design tradeoffs and efficient data structures. A brute-force list with sorting shows baseline reasoning, but the sorted structure proves you can optimize repeated queries.

Solution

We use a hash table tasks to record the set of tasks for each user, where the key is the user ID and the value is a sorted set sorted by the deadline of the task. In addition, we use a variable i to record the current task ID.

When calling the addTask method, we add the task to the task set of the corresponding user and return the task ID. The time complexity of this operation is O(log n).

When calling the getAllTasks method, we traverse the task set of the corresponding user and add the description of the unfinished task to the result list, and then return the result list. The time complexity of this operation is O(n).

When calling the getTasksForTag method, we traverse the task set of the corresponding user and add the description of the unfinished task to the result list, and then return the result list. The time complexity of this operation is O(n).

When calling the completeTask method, we traverse the task set of the corresponding user and mark the task whose task ID is taskId as completed. The time complexity of this operation is (n).

The space complexity is O(n). Where n is the number of all tasks.

Code

Python Java Rust

Python

Java

Rust

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Hash Table + On-Demand Sorting	Add: O(1), Query: O(n log n)	O(n)	Small datasets or when queries are rare
Hash Table + Sorted Set	Add: O(log n), Query: O(k + log n)	O(n)	Frequent queries where tasks must stay ordered by due date

Video Solution

How to Start Leetcode (as a beginner) • Ashish Pratap Singh • 1,177,663 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design a Todo List easy or hard?

Design a Todo List is considered a Medium difficulty problem. The logic is straightforward, but choosing the right combination of data structures to keep tasks ordered while supporting efficient updates requires careful design.

Design a Todo List Python/Java solution

In Python, you can combine dictionaries with a sorted container (like heap or sorted list implementations) to maintain due-date ordering. In Java, a HashMap with TreeSet works well because TreeSet keeps elements sorted with O(log n) insertion and deletion.

How to solve Design a Todo List in O(log n)?

Use a hash table mapping each user to a sorted data structure keyed by due date. When a task is added, insert it into the sorted set so ordering is preserved automatically. During queries, iterate through the sorted tasks and filter by tag and completion status without performing an extra sorting step.

What is the best approach for Design a Todo List?

The most efficient approach uses a hash table combined with a sorted set (such as TreeSet or balanced BST). The hash table stores task metadata while the sorted set keeps tasks ordered by due date. This allows task insertion in O(log n) time and efficient retrieval of pending tasks without running a full sort.

Is Design a Todo List asked at Google/Amazon/Meta?

Design-style data structure questions like this commonly appear in interviews at companies such as Google, Amazon, and Meta. The problem evaluates your ability to design efficient APIs, combine hash tables with ordered structures, and reason about operation complexity.

What data structure is used in Design a Todo List?

The core data structures are a hash table for mapping users and tasks, and a sorted set (TreeSet, balanced BST, or ordered structure) to maintain tasks sorted by due date. Arrays or lists may also be used for storing task metadata like tags.

What is the time complexity of Design a Todo List?

With the optimized design, adding a task takes O(log n) due to insertion into a sorted set. Completing a task is O(1) if you update a status map. Retrieving tasks is typically O(k + log n), where k is the number of tasks returned, because the structure is already ordered.

Ready to solve this problem?

Practice Design a Todo List with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance59.8%

Approaches1

Reading time11 min

Asked at

Bloomberg