LeetCode Solutions Blog

Design a Todo List

Number: 2688

Difficulty: Medium

Paid? Yes

Companies: Bloomberg

Problem Description

Design a Todo List system where users can add tasks with a description, due date, and optional tags. Users can then retrieve their pending tasks (ordered by due date), filter their tasks by specific tags, and mark tasks as complete. Each task is assigned a unique, sequentially increasing ID starting from 1.

Key Insights

Use a global counter to generate sequential task IDs.
Maintain a mapping from userIds to their active (uncompleted) tasks.
Each task record stores its id, description, due date, and tags.
For retrieval, sort tasks by dueDate (all dueDate values are unique).
Filtering by tag requires checking the tags list for each task.
Given the problem constraints (at most 100 calls per method), simple data structures and sorting on the fly are acceptable.

Space and Time Complexity

Time Complexity:

addTask: O(1)
getAllTasks: O(n log n) per call (n is number of uncompleted tasks for the user) due to sorting.
getTasksForTag: O(n log n) per call in the worst case.
completeTask: O(1)

Space Complexity:

O(T) where T is the total number of tasks added (each user has their own mapping).

Solution

We maintain a global counter to assign unique task IDs. For each user, we store the tasks in a dictionary keyed by taskId, which holds the task details (description, dueDate, tags). When retrieving tasks (either all or by tag), we filter tasks that are uncompleted and sort them by dueDate. The completeTask function checks if the task exists for the user and marks it as completed (or removes it from the active list). Since the number of tasks is limited by the problem constraints, re-sorting during retrieval is efficient and simplifies our design.

Code Solutions

# Python implementation of TodoList
class TodoList:
    def __init__(self):
        # Global counter for task id assignment.
        self.global_task_id = 1
        # Dictionary mapping userId to a dictionary of taskId: taskInfo.
        self.user_tasks = {}
    
    def addTask(self, userId, taskDescription, dueDate, tags):
        # Create task object.
        task = {
            'id': self.global_task_id,
            'description': taskDescription,
            'dueDate': dueDate,
            'tags': set(tags)
        }
        # Add task for the user.
        if userId not in self.user_tasks:
            self.user_tasks[userId] = {}
        self.user_tasks[userId][self.global_task_id] = task
        self.global_task_id += 1
        return task['id']
    
    def getAllTasks(self, userId):
        if userId not in self.user_tasks:
            return []
        # Get all active tasks sorted by dueDate.
        tasks = list(self.user_tasks[userId].values())
        tasks.sort(key=lambda x: x['dueDate'])
        return [task['description'] for task in tasks]
    
    def getTasksForTag(self, userId, tag):
        if userId not in self.user_tasks:
            return []
        # Filter tasks that include the tag.
        tasks = [task for task in self.user_tasks[userId].values() if tag in task['tags']]
        tasks.sort(key=lambda x: x['dueDate'])
        return [task['description'] for task in tasks]
    
    def completeTask(self, userId, taskId):
        # Only complete the task if it exists and belongs to the user.
        if userId in self.user_tasks and taskId in self.user_tasks[userId]:
            del self.user_tasks[userId][taskId]
            
# Example usage:
# todoList = TodoList()
# task1 = todoList.addTask(1, "Task1", 50, [])
# task2 = todoList.addTask(1, "Task2", 100, ["P1"])
# print(todoList.getAllTasks(1))  # ["Task1", "Task2"]
# todoList.completeTask(1, task2)
# print(todoList.getTasksForTag(1, "P1"))  # []