LeetCode 2590 - Design a Todo List

This problem asks us to design a small task management system, similar to a lightweight todo application. We need to implement a TodoList class that supports adding tasks, marking tasks as completed, retrieving all pending tasks for a user, and filtering pending tasks by tag.

leetcodemediumarrayhash-tablestringdesignsorting

LeetCode Problem 2590

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Design, Sorting

Solution

Problem Understanding

This problem asks us to design a small task management system, similar to a lightweight todo application. We need to implement a TodoList class that supports adding tasks, marking tasks as completed, retrieving all pending tasks for a user, and filtering pending tasks by tag.

Each task belongs to a specific user and contains four important pieces of information:

  • A unique sequential taskId
  • A textual description
  • A dueDate
  • A list of tags

The system must also track whether a task has been completed.

The key operations involve retrieving tasks in sorted order. Specifically, when we fetch tasks, they must be ordered by dueDate, and only uncompleted tasks should appear. Additionally, filtering by tag should only return uncompleted tasks containing that specific tag.

Let us restate the operations in simpler terms:

The addTask method creates a new task for a user and assigns it an automatically increasing ID. The first task gets ID 1, the second gets ID 2, and so on.

The getAllTasks method returns all incomplete task descriptions for a given user, sorted by due date.

The getTasksForTag method behaves similarly, except it only includes incomplete tasks containing the specified tag.

The completeTask method marks a task as completed, but only if:

  1. The task actually exists.
  2. The task belongs to the specified user.
  3. The task has not already been completed.

If any of these conditions fail, the operation does nothing.

The input in LeetCode consists of a sequence of method calls on the TodoList object. The expected output corresponds to the return value of each method call. Methods returning void produce null.

The constraints are very important for choosing a solution strategy.

  • There are at most 100 calls per method.
  • userId, taskId, and dueDate are all at most 100.
  • Due dates are guaranteed to be unique.
  • Tags and descriptions are small.

These constraints are extremely small. Since there are at most a few hundred total tasks, even an approach involving sorting during retrieval is perfectly acceptable. We do not need advanced balanced trees, heaps, or indexing systems.

Several edge cases stand out immediately.

A user may not exist yet, so retrieval methods should return an empty list. A task completion request may reference the wrong user or a nonexistent task, which should safely do nothing. Tasks may have no tags, meaning tag filtering should naturally exclude them unless relevant. Since due dates are unique, sorting never faces tie-breaking ambiguity.

Approaches

Brute Force Approach

The most straightforward solution is to store every task in a single global list. Each task would contain all relevant information, including user ownership, completion status, tags, and due date.

For retrieval operations like getAllTasks, we would scan the entire task list and filter tasks that:

  • Belong to the requested user
  • Are not completed

Then we would sort the filtered tasks by due date and return their descriptions.

Similarly, for getTasksForTag, we would scan every task again and additionally check whether the requested tag exists in the task's tag list.

This works because every query explicitly checks the required conditions and sorting guarantees correct ordering.

However, this approach is inefficient because every query scans all tasks globally, even tasks belonging to unrelated users.

Optimal Approach

A better design is to organize tasks by user.

We maintain:

  1. A hash map from userId → list of taskIds
  2. A hash map from taskId → task data
  3. A sequential task ID counter

Each task stores:

  • Description
  • Due date
  • Tags
  • Completion state
  • Owner (userId)

When retrieving tasks, we only inspect the tasks owned by that user instead of scanning all tasks globally.

Since constraints are small, we can simply sort the user's active tasks during retrieval. Due dates are unique, so ordering is straightforward.

The major insight is that retrieval happens per user, so grouping tasks by user reduces unnecessary work and makes the design cleaner.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) per query O(n) Scans all tasks globally
Optimal O(k log k) per query O(n) Only scans tasks for one user

Here:

  • n = total number of tasks
  • k = number of tasks for a specific user

Since k ≤ n, the optimal solution is strictly better in practice.

Algorithm Walkthrough

Step 1: Create Task Storage

We maintain a dictionary mapping taskId to task information.

Each task stores:

  • userId
  • description
  • dueDate
  • tags
  • completed

This allows O(1) lookup by task ID.

Step 2: Group Tasks by User

We maintain another dictionary:

user_tasks[userId] → [taskIds]

This prevents us from scanning unrelated users' tasks.

Whenever a task is added, we append its ID to the appropriate user's list.

Step 3: Maintain Sequential Task IDs

We keep a counter starting at 1.

Every time addTask is called:

  1. Assign the current counter value.
  2. Increment the counter.
  3. Store the task.

This guarantees sequential IDs.

Step 4: Add a Task

When addTask is called:

  1. Generate a new task ID.
  2. Create a task object.
  3. Store it in the task map.
  4. Add the task ID to the user's list.
  5. Return the task ID.

This operation is constant time.

Step 5: Retrieve All Tasks

When getAllTasks(userId) is called:

  1. Retrieve that user's task IDs.
  2. Iterate through them.
  3. Ignore completed tasks.
  4. Collect (dueDate, description) pairs.
  5. Sort by due date.
  6. Return descriptions only.

Sorting ensures correct ordering.

Step 6: Retrieve Tasks for a Tag

When getTasksForTag(userId, tag) is called:

  1. Retrieve the user's task IDs.
  2. Skip completed tasks.
  3. Check whether the tag exists.
  4. Collect matching tasks.
  5. Sort by due date.
  6. Return descriptions.

Step 7: Complete a Task

When completeTask(userId, taskId) is called:

  1. Check whether the task exists.
  2. Verify ownership.
  3. Verify it is unfinished.
  4. Mark it as completed.

If any condition fails, do nothing.

Why it works

The correctness comes from maintaining a consistent mapping between users and tasks while preserving task metadata.

Every task is stored exactly once, and every user maintains references only to their own tasks. Retrieval methods explicitly filter out completed tasks and sort remaining tasks by due date, guaranteeing the required ordering. Since task completion only modifies a boolean flag, completed tasks naturally disappear from future queries.

Python Solution

from typing import List
from collections import defaultdict

class TodoList:

    def __init__(self):
        self.next_task_id = 1
        self.tasks = {}
        self.user_tasks = defaultdict(list)

    def addTask(
        self,
        userId: int,
        taskDescription: str,
        dueDate: int,
        tags: List[str]
    ) -> int:

        task_id = self.next_task_id
        self.next_task_id += 1

        self.tasks[task_id] = {
            "userId": userId,
            "description": taskDescription,
            "dueDate": dueDate,
            "tags": set(tags),
            "completed": False
        }

        self.user_tasks[userId].append(task_id)

        return task_id

    def getAllTasks(self, userId: int) -> List[str]:
        pending_tasks = []

        for task_id in self.user_tasks.get(userId, []):
            task = self.tasks[task_id]

            if not task["completed"]:
                pending_tasks.append(
                    (task["dueDate"], task["description"])
                )

        pending_tasks.sort()

        return [description for _, description in pending_tasks]

    def getTasksForTag(
        self,
        userId: int,
        tag: str
    ) -> List[str]:

        filtered_tasks = []

        for task_id in self.user_tasks.get(userId, []):
            task = self.tasks[task_id]

            if (
                not task["completed"]
                and tag in task["tags"]
            ):
                filtered_tasks.append(
                    (task["dueDate"], task["description"])
                )

        filtered_tasks.sort()

        return [description for _, description in filtered_tasks]

    def completeTask(
        self,
        userId: int,
        taskId: int
    ) -> None:

        if taskId not in self.tasks:
            return

        task = self.tasks[taskId]

        if task["userId"] != userId:
            return

        if task["completed"]:
            return

        task["completed"] = True

The implementation closely follows the algorithm.

The constructor initializes the sequential ID counter and two dictionaries. The tasks dictionary provides fast task lookup by ID, while user_tasks groups task IDs by owner.

The addTask method creates a task entry and inserts it into both structures. Tags are converted to a set so membership checking becomes O(1).

The retrieval methods iterate only through the requested user's tasks, filtering out completed items and optionally filtering by tag. Since the output must be sorted by due date, we collect (dueDate, description) tuples and sort them.

The completion method safely validates task existence and ownership before updating state.

Go Solution

package main

import "sort"

type Task struct {
	userId     int
	description string
	dueDate    int
	tags        map[string]bool
	completed   bool
}

type TodoList struct {
	nextTaskID int
	tasks      map[int]*Task
	userTasks  map[int][]int
}

func Constructor() TodoList {
	return TodoList{
		nextTaskID: 1,
		tasks:      make(map[int]*Task),
		userTasks:  make(map[int][]int),
	}
}

func (this *TodoList) AddTask(
	userId int,
	taskDescription string,
	dueDate int,
	tags []string,
) int {

	taskID := this.nextTaskID
	this.nextTaskID++

	tagSet := make(map[string]bool)
	for _, tag := range tags {
		tagSet[tag] = true
	}

	this.tasks[taskID] = &Task{
		userId:     userId,
		description: taskDescription,
		dueDate:    dueDate,
		tags:       tagSet,
		completed:  false,
	}

	this.userTasks[userId] =
		append(this.userTasks[userId], taskID)

	return taskID
}

func (this *TodoList) GetAllTasks(
	userId int,
) []string {

	type Pair struct {
		dueDate    int
		description string
	}

	var pending []Pair

	for _, taskID := range this.userTasks[userId] {
		task := this.tasks[taskID]

		if !task.completed {
			pending = append(
				pending,
				Pair{
					dueDate: task.dueDate,
					description: task.description,
				},
			)
		}
	}

	sort.Slice(
		pending,
		func(i, j int) bool {
			return pending[i].dueDate <
				pending[j].dueDate
		},
	)

	result := make([]string, 0, len(pending))

	for _, task := range pending {
		result = append(
			result,
			task.description,
		)
	}

	return result
}

func (this *TodoList) GetTasksForTag(
	userId int,
	tag string,
) []string {

	type Pair struct {
		dueDate    int
		description string
	}

	var filtered []Pair

	for _, taskID := range this.userTasks[userId] {
		task := this.tasks[taskID]

		if !task.completed &&
			task.tags[tag] {

			filtered = append(
				filtered,
				Pair{
					dueDate: task.dueDate,
					description: task.description,
				},
			)
		}
	}

	sort.Slice(
		filtered,
		func(i, j int) bool {
			return filtered[i].dueDate <
				filtered[j].dueDate
		},
	)

	result := make([]string, 0, len(filtered))

	for _, task := range filtered {
		result = append(
			result,
			task.description,
		)
	}

	return result
}

func (this *TodoList) CompleteTask(
	userId int,
	taskId int,
) {

	task, exists := this.tasks[taskId]

	if !exists {
		return
	}

	if task.userId != userId {
		return
	}

	if task.completed {
		return
	}

	task.completed = true
}

The Go solution mirrors the Python implementation closely.

Since Go does not have built-in sets, tags are stored using map[string]bool. A missing key naturally evaluates to false, making tag checks simple.

Maps return zero values for missing keys, so this.userTasks[userId] safely returns nil, which behaves like an empty slice during iteration.

Integer overflow is not a concern because the constraints are extremely small.

Worked Examples

Example 1

Initial state:

Variable Value
nextTaskID 1
tasks {}
userTasks {}

Step 1

addTask(1, "Task1", 50, [])

State:

Structure Value
tasks {1: (user=1, due=50, completed=False)}
userTasks {1: [1]}

Return:

1

Step 2

addTask(1, "Task2", 100, ["P1"])

State:

Structure Value
tasks {1, 2}
userTasks {1: [1, 2]}

Return:

2

Step 3

getAllTasks(1)

Uncompleted tasks:

Task Due Date
Task1 50
Task2 100

Sorted result:

["Task1", "Task2"]

Step 4

getAllTasks(5)

User 5 has no tasks.

Result:

[]

Step 5

addTask(1, "Task3", 30, ["P1"])

State:

Structure Value
userTasks {1: [1, 2, 3]}

Step 6

getTasksForTag(1, "P1")

Matching tasks:

Task Due Date
Task3 30
Task2 100

Result:

["Task3", "Task2"]

Step 7

completeTask(5, 1)

Task belongs to user 1, nothing changes.

Step 8

completeTask(1, 2)

Task 2 becomes completed.

Step 9

getTasksForTag(1, "P1")

Only Task3 remains.

Result:

["Task3"]

Step 10

getAllTasks(1)

Remaining active tasks:

Task Due Date
Task3 30
Task1 50

Result:

["Task3", "Task1"]

Complexity Analysis

Measure Complexity Explanation
Time O(k log k) Retrieval scans user tasks and sorts them
Space O(n) Stores all tasks and mappings

Here, n is the total number of tasks and k is the number of tasks owned by a specific user.

Adding tasks and completing tasks are O(1) operations because they only involve hash map lookups and updates. Retrieval operations dominate runtime because sorting is required to return tasks in due-date order.

Test Cases

todo = TodoList()

# Example from problem statement
assert todo.addTask(1, "Task1", 50, []) == 1
assert todo.addTask(1, "Task2", 100, ["P1"]) == 2
assert todo.getAllTasks(1) == ["Task1", "Task2"]  # basic retrieval
assert todo.getAllTasks(5) == []  # nonexistent user

assert todo.addTask(1, "Task3", 30, ["P1"]) == 3
assert todo.getTasksForTag(1, "P1") == [
    "Task3",
    "Task2"
]  # tag filtering and sorting

todo.completeTask(5, 1)
assert todo.getAllTasks(1) == [
    "Task3",
    "Task1",
    "Task2"
]  # wrong user completion ignored

todo.completeTask(1, 2)
assert todo.getTasksForTag(1, "P1") == [
    "Task3"
]  # completed task removed

assert todo.getAllTasks(1) == [
    "Task3",
    "Task1"
]  # sorted by due date

# Empty tag list
todo2 = TodoList()
todo2.addTask(1, "NoTags", 10, [])
assert todo2.getTasksForTag(1, "x") == []

# Multiple users
todo3 = TodoList()
todo3.addTask(1, "User1Task", 20, [])
todo3.addTask(2, "User2Task", 10, [])
assert todo3.getAllTasks(1) == ["User1Task"]
assert todo3.getAllTasks(2) == ["User2Task"]

# Complete nonexistent task
todo4 = TodoList()
todo4.addTask(1, "Task", 5, [])
todo4.completeTask(1, 999)
assert todo4.getAllTasks(1) == [
    "Task"
]  # no change

# Complete already completed task
todo5 = TodoList()
todo5.addTask(1, "Task", 5, [])
todo5.completeTask(1, 1)
todo5.completeTask(1, 1)
assert todo5.getAllTasks(1) == []

# Ordering check
todo6 = TodoList()
todo6.addTask(1, "Late", 100, [])
todo6.addTask(1, "Early", 10, [])
todo6.addTask(1, "Middle", 50, [])
assert todo6.getAllTasks(1) == [
    "Early",
    "Middle",
    "Late"
]  # due date sorting
Test Why
Problem example Validates expected behavior
Nonexistent user Ensures empty list handling
Empty tags Confirms tag filtering correctness
Multiple users Verifies user isolation
Nonexistent task completion Ensures safe no-op behavior
Double completion Confirms idempotency
Ordering test Verifies due-date sorting

Edge Cases

User Does Not Exist

A retrieval request may reference a user who has never added a task. A naive implementation could accidentally raise a lookup error.

Our implementation avoids this by using .get(userId, []) in Python and relying on Go's zero-value nil slice behavior. In both cases, iteration safely occurs over an empty collection, producing an empty result.

Completing a Task Owned by Another User

A task may exist, but belong to a different user. This is subtle because simply checking task existence is not enough.

Our implementation explicitly verifies ownership before modifying state. If task["userId"] != userId, the operation immediately returns, preventing accidental modification of another user's tasks.

Tasks Without Tags

Some tasks may have an empty tag list. A naive implementation could mistakenly include them during tag filtering or produce errors.

We handle this naturally by storing tags as a set or hash map. Membership checks fail cleanly, meaning untagged tasks are excluded from tag-specific queries.

Completing an Already Completed Task

The same task might be marked complete multiple times. A fragile implementation could behave unpredictably or duplicate side effects.

Our solution checks the completion flag first. If the task is already completed, the method immediately returns, making the operation safe and idempotent.