Skip to content

2590. Design a Todo List

On LeetCode ->

Problem

Design a todo list with globally increasing task IDs. Return each user's pending task descriptions in due-date order, optionally filtered by tag. Completing a task must not affect another user's tasks.

addTask(1, "later", 20, ["work"]) -> 1
addTask(1, "first", 10, ["work"]) -> 2
getTasksForTag(1, "work") -> ["first", "later"]
completeTask(1, 2)
getAllTasks(1) -> ["later"]

class TodoList:
    def __init__(self):
        pass

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

    def getAllTasks(self, userId: int) -> list[str]:
        pass

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

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

Key trick

Keep a global task-ID lookup for completion and a per-user list of IDs for queries. Remove completed tasks from the lookup; sort only the matching pending tasks when queried.

Trap

Task IDs are global, not per-user. Tag-filtered results also need due-date sorting, and completeTask must verify ownership.

Why is it interesting?

It tests how to organize state for operations with different lookup needs without overengineering a small design problem.

Python solution

class TodoList:
    def __init__(self):
        self.next_id = 1
        self.tasks = {}  # task ID -> [user ID, description, due date, tags, completed]
        self.users = {}  # user ID -> task IDs

    def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: list[str]) -> int:
        task_id = self.next_id
        self.next_id += 1

        self.tasks[task_id] = [userId, taskDescription, dueDate, set(tags), False]
        self.users.setdefault(userId, []).append(task_id)
        return task_id

    def _get_tasks(self, userId: int, tag: str | None = None) -> list[str]:
        pending = []

        for task_id in self.users.get(userId, []):
            _, description, due_date, tags, completed = self.tasks[task_id]
            if not completed and (tag is None or tag in tags):
                pending.append((due_date, description))

        return [description for _, description in sorted(pending)]

    def getAllTasks(self, userId: int) -> list[str]:
        return self._get_tasks(userId)

    def getTasksForTag(self, userId: int, tag: str) -> list[str]:
        return self._get_tasks(userId, tag)

    def completeTask(self, userId: int, taskId: int) -> None:
        task = self.tasks.get(taskId)
        if task and task[0] == userId:
            task[4] = True

With \(t\) tasks added for the queried user and \(k\) tags on a new task, adding takes \(O(k)\) time, completing takes \(O(1)\) average time, and a query takes \(O(t \log t)\) time and \(O(t)\) space. Total stored space is \(O(T + K)\) for \(T\) added tasks and \(K\) stored tags.

Comment on my solution

  • dueDate int is missing a colon, and [tasks] should be ["tasks"].
  • Your task IDs restart for each user, but they must increase globally.
  • getTasksForTag does not sort by due date.
  • completeTask treats the global task ID as a position in one user's list, so it can complete the wrong task.
class TodoList:
    def __init__(self):
        self.users = [{"next_task_id": 1, "tasks": []} for _ in range(100)]


    def addTask(self, userId: int, taskDescription: str, dueDate int, tags: list[str]):
        user = self.users[userId - 1]
        task_id = user["next_task_id"]
        user["next_task_id"] += 1
        # False is for not completed
        user["tasks"].append([task_id, taskDescription, set(tags), dueDate, False])
        return task_id


    def getAllTasks(self, userId: int):
        tasks = self.users[userId - 1][tasks]
        if not tasks:
            return []
        ordered = sorted((due_date, task_description) for _, task_description, _, due_date, completed in tasks if completed == False)
        return [task_description for _, task_description in ordered]

    def getTasksForTag(self, userId: int, tag: str):
        tasks = self.users[userId - 1][tasks]
        if not tasks:
            return []
        not_completed = [(task_description, tags) for _, task_description, tags, _, completed in tasks if completed == False]
        return [task_description for task_description, tags in not_completed if tag in tags]

    def completeTask(self, userId: int, taskId: int):
        tasks = self.users[userId - 1][tasks]
        if len(tasks) < taskId:
            return
        tasks[taskId - 1][4] = True

Extra

Problem description

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.