Design a Todo List

Problem

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.

Examples

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.

Solution

Method 1 – Hash Map and Sorting for User Tasks

Intuition

We need to efficiently add, complete, and query tasks for each user, including filtering by tags and ordering by due date. Using a hash map to store user tasks and a global task ID counter allows us to manage tasks efficiently. Sorting by due date ensures correct ordering for queries.

Approach

1. Use a global task ID counter, incremented for each new task.
2. Store all tasks in a hash map from task ID to task info (userId, description, dueDate, tags, completed).
3. For each user, maintain a set of their task IDs.
4. For addTask, create a new task, store it, and add its ID to the user's set.
5. For getAllTasks, filter the user's tasks for uncompleted ones, sort by due date, and return descriptions.
6. For getTasksForTag, filter the user's uncompleted tasks for the tag, sort by due date, and return descriptions.
7. For completeTask, mark the task as completed if it exists, belongs to the user, and is not already completed.

Code

Python

class TodoList:
    def __init__(self):
        self.task_id = 1
        self.tasks = {}  # taskId -> {userId, desc, due, tags, completed}
        self.user_tasks = {}  # userId -> set of taskIds
    def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: list[str]) -> int:
        tid = self.task_id
        self.task_id += 1
        self.tasks[tid] = {
            'userId': userId,
            'desc': taskDescription,
            'due': dueDate,
            'tags': set(tags),
            'completed': False
        }
        if userId not in self.user_tasks:
            self.user_tasks[userId] = set()
        self.user_tasks[userId].add(tid)
        return tid
    def getAllTasks(self, userId: int) -> list[str]:
        if userId not in self.user_tasks:
            return []
        tasks = [self.tasks[tid] for tid in self.user_tasks[userId] if not self.tasks[tid]['completed']]
        tasks.sort(key=lambda x: x['due'])
        return [t['desc'] for t in tasks]
    def getTasksForTag(self, userId: int, tag: str) -> list[str]:
        if userId not in self.user_tasks:
            return []
        tasks = [self.tasks[tid] for tid in self.user_tasks[userId] if not self.tasks[tid]['completed'] and tag in self.tasks[tid]['tags']]
        tasks.sort(key=lambda x: x['due'])
        return [t['desc'] for t in tasks]
    def completeTask(self, userId: int, taskId: int) -> None:
        if taskId in self.tasks and self.tasks[taskId]['userId'] == userId and not self.tasks[taskId]['completed']:
            self.tasks[taskId]['completed'] = True

Java

import java.util.*;
public class TodoList {
    private int nextId = 1;
    private static class Task {
        int userId, dueDate;
        String desc;
        Set<String> tags;
        boolean completed;
        Task(int userId, String desc, int dueDate, List<String> tags) {
            this.userId = userId;
            this.desc = desc;
            this.dueDate = dueDate;
            this.tags = new HashSet<>(tags);
            this.completed = false;
        }
    }
    private Map<Integer, Task> tasks = new HashMap<>();
    private Map<Integer, Set<Integer>> userTasks = new HashMap<>();
    public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
        int tid = nextId++;
        Task t = new Task(userId, taskDescription, dueDate, tags);
        tasks.put(tid, t);
        userTasks.computeIfAbsent(userId, k -> new HashSet<>()).add(tid);
        return tid;
    }
    public List<String> getAllTasks(int userId) {
        if (!userTasks.containsKey(userId)) return new ArrayList<>();
        List<Task> list = new ArrayList<>();
        for (int tid : userTasks.get(userId)) {
            Task t = tasks.get(tid);
            if (!t.completed) list.add(t);
        }
        list.sort(Comparator.comparingInt(a -> a.dueDate));
        List<String> ans = new ArrayList<>();
        for (Task t : list) ans.add(t.desc);
        return ans;
    }
    public List<String> getTasksForTag(int userId, String tag) {
        if (!userTasks.containsKey(userId)) return new ArrayList<>();
        List<Task> list = new ArrayList<>();
        for (int tid : userTasks.get(userId)) {
            Task t = tasks.get(tid);
            if (!t.completed && t.tags.contains(tag)) list.add(t);
        }
        list.sort(Comparator.comparingInt(a -> a.dueDate));
        List<String> ans = new ArrayList<>();
        for (Task t : list) ans.add(t.desc);
        return ans;
    }
    public void completeTask(int userId, int taskId) {
        if (tasks.containsKey(taskId)) {
            Task t = tasks.get(taskId);
            if (t.userId == userId && !t.completed) t.completed = true;
        }
    }
}

Complexity

• ⏰ Time complexity:
  • addTask: O(t) time to insert the task and copy its tags (where t is the number of tags for the task). Average O(1) if tag count is bounded.
  • getAllTasks: O(m log m) time where m is the number of tasks for the user (filter uncompleted tasks O(m) and sort by due date O(m log m)).
  • getTasksForTag: O(m log m) time where m is the number of tasks for the user (filter by tag O(m) and sort the matched tasks O(r log r) which is O(m log m) in the worst case).
  • completeTask: O(1) average time (hash-map lookup + update).
• 🧺 Space complexity:
  • O(n) persistent space to store all tasks (where n is number of created tasks).
  • O(m) additional temporary space for getAllTasks / getTasksForTag results and sorting (where m is the number of tasks considered for that user).