Facebook Pixel

2590. Design a Todo List 🔒

MediumDesignArrayHash TableStringSorting
Leetcode Link

Problem Description

This problem asks you to design a Todo List system where users can manage their tasks. The system needs to support multiple users, each with their own set of tasks.

The TodoList class should implement the following functionalities:

  1. TodoList(): Initialize an empty todo list system.

  2. addTask(userId, taskDescription, dueDate, tags): Add a new task for a specific user with:

    • userId: The ID of the user who owns the task
    • taskDescription: A string describing the task
    • dueDate: An integer representing when the task is due
    • tags: A list of string tags associated with the task
    • Returns a unique task ID (starting from 1 and incrementing sequentially)

  3. getAllTasks(userId): Get all uncompleted tasks for a specific user:

    • Returns a list of task descriptions
    • Tasks should be ordered by their due date (earliest first)
    • Returns an empty list if the user has no uncompleted tasks

  4. getTasksForTag(userId, tag): Get all uncompleted tasks for a user that have a specific tag:

    • Returns a list of task descriptions that contain the specified tag
    • Tasks should be ordered by their due date (earliest first)
    • Returns an empty list if no matching tasks exist

  5. completeTask(userId, taskId): Mark a task as completed:

    • Only marks the task if it exists, belongs to the specified user, and is currently uncompleted
    • No return value

The solution uses a hash table to map each user to their tasks, with tasks stored in a SortedList that automatically maintains order by due date. Each task is represented as a list containing [dueDate, taskDescription, tags_set, taskId, is_completed]. This design allows efficient insertion while maintaining sorted order, and quick retrieval of tasks based on completion status and tags.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is that we need to efficiently manage tasks for multiple users while maintaining specific ordering and filtering capabilities. Let's think through what data structures would best support our operations:

First, since we have multiple users, we need a way to separate each user's tasks. A hash table (dictionary) with userId as the key is the natural choice here - it gives us O(1) access to any user's task list.

For each user's tasks, we need to maintain them in order by due date since both getAllTasks and getTasksForTag require returning tasks sorted by due date. We could use a regular list and sort it each time we query, but that would be inefficient with O(n log n) sorting on each query. Instead, we can use a SortedList data structure that maintains sorted order automatically. When we add a task, it gets inserted in the correct position with O(log n) complexity.

Now, how should we represent each task? We need to store:

  • The due date (for sorting)
  • The task description (for returning in queries)
  • The tags (for filtering)
  • The task ID (for identifying tasks to complete)
  • Completion status (to filter out completed tasks)

We store each task as a list [dueDate, taskDescription, tags_set, taskId, is_completed]. The due date comes first because SortedList will use it as the primary sorting key. We convert tags to a set for O(1) membership checking when filtering by tag.

For task IDs, we use a simple counter that increments with each new task. This ensures unique, sequential IDs across all users.

When marking tasks as complete, rather than removing them from the list (which would require finding and removing, potentially O(n)), we simply mark them with a boolean flag. This makes the complete operation simpler - we just find the task and flip its completion status. During queries, we filter out completed tasks.

This design balances efficiency and simplicity: adding tasks is O(log n), retrieving tasks is O(n) (which is optimal since we need to examine all tasks anyway), and completing tasks is O(n) in the worst case but doesn't require restructuring the data.

Learn more about Sorting patterns.

Solution Approach

The solution uses a Hash Table + Sorted Set approach to efficiently manage tasks for multiple users.

Data Structures

  1. Hash Table (defaultdict(SortedList)): Maps each userId to their sorted list of tasks
  2. SortedList: Maintains tasks automatically sorted by due date
  3. Task Representation: Each task is stored as a list: [dueDate, taskDescription, tags_set, taskId, is_completed]
  4. Counter (self.i): Tracks the next task ID to assign

Implementation Details

Initialization (__init__):

  • Initialize self.i = 1 to start task IDs from 1
  • Create self.tasks as a defaultdict(SortedList) to automatically create a new sorted list for new users

Adding Tasks (addTask):

  • Generate a new taskId from the counter self.i and increment it
  • Create a task entry as [dueDate, taskDescription, set(tags), taskId, False]
    • Convert tags to a set for O(1) membership checking
    • Initialize completion status as False
  • Add the task to the user's sorted list: self.tasks[userId].add(...)
  • The SortedList automatically inserts the task in the correct position based on dueDate
  • Time Complexity: O(log n) where n is the number of tasks for the user

Getting All Tasks (getAllTasks):

  • Use list comprehension to filter and extract task descriptions: [x[1] for x in self.tasks[userId] if not x[4]]
  • x[1] extracts the task description (second element)
  • not x[4] filters out completed tasks (fifth element is completion status)
  • Tasks are already sorted by due date thanks to SortedList
  • Time Complexity: O(n) where n is the number of tasks for the user

Getting Tasks by Tag (getTasksForTag):

  • Similar to getAllTasks but with additional tag filtering: [x[1] for x in self.tasks[userId] if not x[4] and tag in x[2]]
  • tag in x[2] checks if the tag exists in the task's tag set (third element)
  • Set membership checking is O(1), making the filter efficient
  • Time Complexity: O(n) where n is the number of tasks for the user

Completing Tasks (completeTask):

  • Iterate through the user's tasks to find the one with matching taskId
  • When found, set task[4] = True to mark it as completed
  • Break immediately after finding the task since task IDs are unique
  • Time Complexity: O(n) in worst case, but average case is better since we can break early

Why This Approach Works

The combination of hash table and sorted list provides:

  • Fast user lookup: O(1) access to any user's task list
  • Automatic sorting: Tasks remain sorted by due date without manual sorting
  • Efficient filtering: Completed tasks are filtered out during queries rather than removed from storage
  • Simple task completion: Just flip a boolean flag instead of removing/restructuring data

This design balances simplicity with efficiency, making all operations reasonably fast while keeping the implementation straightforward.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to see how the TodoList system works:

Step 1: Initialize and Add Tasks

todo = TodoList()
# User 1 adds three tasks
id1 = todo.addTask(1, "Buy groceries", 20, ["shopping", "urgent"])  # Returns 1
id2 = todo.addTask(1, "Finish report", 15, ["work"])                # Returns 2  
id3 = todo.addTask(1, "Call mom", 25, ["personal", "urgent"])       # Returns 3

After these operations, User 1's task list looks like:

[15, "Finish report", {"work"}, 2, False]           # Due date 15 (earliest)
[20, "Buy groceries", {"shopping", "urgent"}, 1, False]  # Due date 20
[25, "Call mom", {"personal", "urgent"}, 3, False]       # Due date 25 (latest)

Notice how tasks are automatically sorted by due date, even though we added them in a different order.

Step 2: Get All Tasks

tasks = todo.getAllTasks(1)  
# Returns: ["Finish report", "Buy groceries", "Call mom"]

The method iterates through the sorted list and returns descriptions of uncompleted tasks in due date order.

Step 3: Complete a Task

todo.completeTask(1, 2)  # Mark "Finish report" as completed

This finds the task with ID 2 and sets its completion flag to True:

[15, "Finish report", {"work"}, 2, True]  # Now marked as completed

Step 4: Get Tasks by Tag

urgent_tasks = todo.getTasksForTag(1, "urgent")
# Returns: ["Buy groceries", "Call mom"]

The method filters for:

  1. Tasks that are not completed (x[4] == False)
  2. Tasks that contain the "urgent" tag ("urgent" in x[2])

Note that "Finish report" is excluded because it's completed, even though it comes first in due date order.

Step 5: Add Another User's Task

id4 = todo.addTask(2, "Study for exam", 10, ["education"])  # Returns 4

User 2 gets their own separate sorted list in the hash table. The task ID counter continues incrementing globally (returns 4, not 1).

Step 6: Verify User Separation

todo.getAllTasks(1)  # Returns: ["Buy groceries", "Call mom"] 
todo.getAllTasks(2)  # Returns: ["Study for exam"]

Each user's tasks remain completely separate, and User 1's completed task is still filtered out.

This walkthrough demonstrates how the sorted list maintains order automatically, how the completion flag allows us to filter tasks without deletion, and how the hash table keeps each user's data isolated.

Solution Implementation

1from collections import defaultdict
2from sortedcontainers import SortedList
3from typing import List
4
5class TodoList:
6    def __init__(self):
7        # Initialize task ID counter starting from 1
8        self.task_id_counter = 1
9        # Dictionary mapping userId to SortedList of tasks
10        # Each task is stored as [dueDate, description, tags_set, taskId, is_completed]
11        self.user_tasks = defaultdict(SortedList)
12
13    def addTask(
14        self, userId: int, taskDescription: str, dueDate: int, tags: List[str]
15    ) -> int:
16        """
17        Add a new task for a user.
18      
19        Args:
20            userId: The ID of the user
21            taskDescription: Description of the task
22            dueDate: Due date of the task (used for sorting)
23            tags: List of tags associated with the task
24          
25        Returns:
26            The ID of the newly created task
27        """
28        # Assign current task ID and increment counter
29        task_id = self.task_id_counter
30        self.task_id_counter += 1
31      
32        # Create task entry: [dueDate, description, tags_set, taskId, is_completed]
33        # Tasks are automatically sorted by dueDate in SortedList
34        task_entry = [dueDate, taskDescription, set(tags), task_id, False]
35        self.user_tasks[userId].add(task_entry)
36      
37        return task_id
38
39    def getAllTasks(self, userId: int) -> List[str]:
40        """
41        Get all uncompleted tasks for a user, sorted by due date.
42      
43        Args:
44            userId: The ID of the user
45          
46        Returns:
47            List of task descriptions for uncompleted tasks
48        """
49        # Return descriptions of all uncompleted tasks (where index 4 is False)
50        return [task[1] for task in self.user_tasks[userId] if not task[4]]
51
52    def getTasksForTag(self, userId: int, tag: str) -> List[str]:
53        """
54        Get all uncompleted tasks for a user that contain a specific tag.
55      
56        Args:
57            userId: The ID of the user
58            tag: The tag to filter by
59          
60        Returns:
61            List of task descriptions for uncompleted tasks with the specified tag
62        """
63        # Return descriptions of uncompleted tasks that contain the specified tag
64        return [
65            task[1] 
66            for task in self.user_tasks[userId] 
67            if not task[4] and tag in task[2]
68        ]
69
70    def completeTask(self, userId: int, taskId: int) -> None:
71        """
72        Mark a task as completed.
73      
74        Args:
75            userId: The ID of the user
76            taskId: The ID of the task to complete
77        """
78        # Find the task with matching taskId and mark it as completed
79        for task in self.user_tasks[userId]:
80            if task[3] == taskId:
81                task[4] = True  # Set is_completed flag to True
82                break
83
84
85# Your TodoList object will be instantiated and called as such:
86# obj = TodoList()
87# param_1 = obj.addTask(userId,taskDescription,dueDate,tags)
88# param_2 = obj.getAllTasks(userId)
89# param_3 = obj.getTasksForTag(userId,tag)
90# obj.completeTask(userId,taskId)
91
1/**
2 * Represents a single task in the todo list system
3 */
4class Task {
5    int taskId;           // Unique identifier for the task
6    String taskName;      // Description/name of the task
7    int dueDate;          // Due date for the task
8    Set<String> tags;     // Set of tags associated with the task
9    boolean isFinished;   // Flag indicating if the task is completed
10
11    /**
12     * Constructor to create a new task
13     * @param taskId Unique identifier for the task
14     * @param taskName Description of the task
15     * @param dueDate Due date for the task
16     * @param tags Set of tags associated with the task
17     */
18    public Task(int taskId, String taskName, int dueDate, Set<String> tags) {
19        this.taskId = taskId;
20        this.taskName = taskName;
21        this.dueDate = dueDate;
22        this.tags = tags;
23        this.isFinished = false;  // Tasks are initially not completed
24    }
25}
26
27/**
28 * Todo list management system that handles tasks for multiple users
29 */
30class TodoList {
31    private int nextTaskId = 1;  // Counter for generating unique task IDs
32    // Map of userId to a TreeSet of tasks (sorted by due date)
33    private Map<Integer, TreeSet<Task>> userTasksMap = new HashMap<>();
34
35    /**
36     * Constructor to initialize an empty todo list
37     */
38    public TodoList() {
39    }
40
41    /**
42     * Adds a new task for a specific user
43     * @param userId The ID of the user adding the task
44     * @param taskDescription Description of the task
45     * @param dueDate Due date for the task
46     * @param tags List of tags associated with the task
47     * @return The unique task ID of the newly created task
48     */
49    public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
50        // Create a new task with auto-incremented ID
51        Task newTask = new Task(nextTaskId++, taskDescription, dueDate, new HashSet<>(tags));
52      
53        // Add task to user's task set (create set if it doesn't exist)
54        // Tasks are automatically sorted by due date
55        userTasksMap.computeIfAbsent(userId, 
56            k -> new TreeSet<>(Comparator.comparingInt(task -> task.dueDate)))
57            .add(newTask);
58      
59        return newTask.taskId;
60    }
61
62    /**
63     * Retrieves all uncompleted tasks for a specific user, sorted by due date
64     * @param userId The ID of the user
65     * @return List of task descriptions for uncompleted tasks
66     */
67    public List<String> getAllTasks(int userId) {
68        List<String> taskDescriptions = new ArrayList<>();
69      
70        // Check if user has any tasks
71        if (userTasksMap.containsKey(userId)) {
72            // Iterate through tasks in sorted order (by due date)
73            for (Task task : userTasksMap.get(userId)) {
74                // Only include uncompleted tasks
75                if (!task.isFinished) {
76                    taskDescriptions.add(task.taskName);
77                }
78            }
79        }
80      
81        return taskDescriptions;
82    }
83
84    /**
85     * Retrieves all uncompleted tasks with a specific tag for a user
86     * @param userId The ID of the user
87     * @param tag The tag to filter by
88     * @return List of task descriptions that have the specified tag
89     */
90    public List<String> getTasksForTag(int userId, String tag) {
91        List<String> taskDescriptions = new ArrayList<>();
92      
93        // Check if user has any tasks
94        if (userTasksMap.containsKey(userId)) {
95            // Iterate through tasks in sorted order (by due date)
96            for (Task task : userTasksMap.get(userId)) {
97                // Include only uncompleted tasks that contain the specified tag
98                if (task.tags.contains(tag) && !task.isFinished) {
99                    taskDescriptions.add(task.taskName);
100                }
101            }
102        }
103      
104        return taskDescriptions;
105    }
106
107    /**
108     * Marks a specific task as completed
109     * @param userId The ID of the user who owns the task
110     * @param taskId The ID of the task to complete
111     */
112    public void completeTask(int userId, int taskId) {
113        // Check if user has any tasks
114        if (userTasksMap.containsKey(userId)) {
115            // Search for the task with matching ID
116            for (Task task : userTasksMap.get(userId)) {
117                if (task.taskId == taskId) {
118                    // Mark task as finished
119                    task.isFinished = true;
120                    break;  // Exit loop once task is found
121                }
122            }
123        }
124    }
125}
126
127/**
128 * Your TodoList object will be instantiated and called as such:
129 * TodoList obj = new TodoList();
130 * int param_1 = obj.addTask(userId,taskDescription,dueDate,tags);
131 * List<String> param_2 = obj.getAllTasks(userId);
132 * List<String> param_3 = obj.getTasksForTag(userId,tag);
133 * obj.completeTask(userId,taskId);
134 */
135
1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5#include <set>
6#include <algorithm>
7
8using namespace std;
9
10/**
11 * Represents a single task in the todo list system
12 */
13class Task {
14public:
15    int task_id;                    // Unique identifier for the task
16    string task_name;               // Description/name of the task
17    int due_date;                   // Due date for the task
18    unordered_set<string> tags;     // Set of tags associated with the task
19    bool is_finished;               // Flag indicating if the task is completed
20
21    /**
22     * Constructor to create a new task
23     * @param taskId Unique identifier for the task
24     * @param taskName Description of the task
25     * @param dueDate Due date for the task
26     * @param taskTags Set of tags associated with the task
27     */
28    Task(int taskId, const string& taskName, int dueDate, const unordered_set<string>& taskTags) 
29        : task_id(taskId), task_name(taskName), due_date(dueDate), tags(taskTags), is_finished(false) {
30        // Tasks are initially not completed
31    }
32};
33
34/**
35 * Comparator for sorting tasks by due date
36 */
37struct TaskComparator {
38    bool operator()(const Task* a, const Task* b) const {
39        // Sort by due date first, then by task_id to ensure stable ordering
40        if (a->due_date != b->due_date) {
41            return a->due_date < b->due_date;
42        }
43        return a->task_id < b->task_id;
44    }
45};
46
47/**
48 * Todo list management system that handles tasks for multiple users
49 */
50class TodoList {
51private:
52    int next_task_id;  // Counter for generating unique task IDs
53    // Map of userId to a set of task pointers (sorted by due date)
54    unordered_map<int, set<Task*, TaskComparator>> user_tasks_map;
55    // Store all tasks to manage memory
56    vector<unique_ptr<Task>> all_tasks;
57
58public:
59    /**
60     * Constructor to initialize an empty todo list
61     */
62    TodoList() : next_task_id(1) {
63    }
64
65    /**
66     * Adds a new task for a specific user
67     * @param userId The ID of the user adding the task
68     * @param taskDescription Description of the task
69     * @param dueDate Due date for the task
70     * @param tags List of tags associated with the task
71     * @return The unique task ID of the newly created task
72     */
73    int addTask(int userId, string taskDescription, int dueDate, vector<string> tags) {
74        // Convert vector of tags to unordered_set
75        unordered_set<string> tag_set(tags.begin(), tags.end());
76      
77        // Create a new task with auto-incremented ID
78        auto new_task = make_unique<Task>(next_task_id++, taskDescription, dueDate, tag_set);
79        Task* task_ptr = new_task.get();
80      
81        // Store the task in our collection
82        all_tasks.push_back(move(new_task));
83      
84        // Add task to user's task set (create set if it doesn't exist)
85        // Tasks are automatically sorted by due date
86        user_tasks_map[userId].insert(task_ptr);
87      
88        return task_ptr->task_id;
89    }
90
91    /**
92     * Retrieves all uncompleted tasks for a specific user, sorted by due date
93     * @param userId The ID of the user
94     * @return List of task descriptions for uncompleted tasks
95     */
96    vector<string> getAllTasks(int userId) {
97        vector<string> task_descriptions;
98      
99        // Check if user has any tasks
100        if (user_tasks_map.find(userId) != user_tasks_map.end()) {
101            // Iterate through tasks in sorted order (by due date)
102            for (Task* task : user_tasks_map[userId]) {
103                // Only include uncompleted tasks
104                if (!task->is_finished) {
105                    task_descriptions.push_back(task->task_name);
106                }
107            }
108        }
109      
110        return task_descriptions;
111    }
112
113    /**
114     * Retrieves all uncompleted tasks with a specific tag for a user
115     * @param userId The ID of the user
116     * @param tag The tag to filter by
117     * @return List of task descriptions that have the specified tag
118     */
119    vector<string> getTasksForTag(int userId, string tag) {
120        vector<string> task_descriptions;
121      
122        // Check if user has any tasks
123        if (user_tasks_map.find(userId) != user_tasks_map.end()) {
124            // Iterate through tasks in sorted order (by due date)
125            for (Task* task : user_tasks_map[userId]) {
126                // Include only uncompleted tasks that contain the specified tag
127                if (task->tags.find(tag) != task->tags.end() && !task->is_finished) {
128                    task_descriptions.push_back(task->task_name);
129                }
130            }
131        }
132      
133        return task_descriptions;
134    }
135
136    /**
137     * Marks a specific task as completed
138     * @param userId The ID of the user who owns the task
139     * @param taskId The ID of the task to complete
140     */
141    void completeTask(int userId, int taskId) {
142        // Check if user has any tasks
143        if (user_tasks_map.find(userId) != user_tasks_map.end()) {
144            // Search for the task with matching ID
145            for (Task* task : user_tasks_map[userId]) {
146                if (task->task_id == taskId) {
147                    // Mark task as finished
148                    task->is_finished = true;
149                    break;  // Exit loop once task is found
150                }
151            }
152        }
153    }
154};
155
156/**
157 * Your TodoList object will be instantiated and called as such:
158 * TodoList* obj = new TodoList();
159 * int param_1 = obj->addTask(userId, taskDescription, dueDate, tags);
160 * vector<string> param_2 = obj->getAllTasks(userId);
161 * vector<string> param_3 = obj->getTasksForTag(userId, tag);
162 * obj->completeTask(userId, taskId);
163 */
164
1/**
2 * Represents a single task in the todo list system
3 */
4interface Task {
5    taskId: number;           // Unique identifier for the task
6    taskName: string;         // Description/name of the task
7    dueDate: number;          // Due date for the task
8    tags: Set<string>;        // Set of tags associated with the task
9    isFinished: boolean;      // Flag indicating if the task is completed
10}
11
12// Counter for generating unique task IDs
13let nextTaskId: number = 1;
14
15// Map of userId to an array of tasks (will be sorted by due date when needed)
16const userTasksMap: Map<number, Task[]> = new Map();
17
18/**
19 * Adds a new task for a specific user
20 * @param userId - The ID of the user adding the task
21 * @param taskDescription - Description of the task
22 * @param dueDate - Due date for the task
23 * @param tags - Array of tags associated with the task
24 * @returns The unique task ID of the newly created task
25 */
26function addTask(userId: number, taskDescription: string, dueDate: number, tags: string[]): number {
27    // Create a new task with auto-incremented ID
28    const newTask: Task = {
29        taskId: nextTaskId++,
30        taskName: taskDescription,
31        dueDate: dueDate,
32        tags: new Set(tags),
33        isFinished: false  // Tasks are initially not completed
34    };
35  
36    // Get or create the user's task array
37    if (!userTasksMap.has(userId)) {
38        userTasksMap.set(userId, []);
39    }
40  
41    // Add task to user's task array
42    const userTasks = userTasksMap.get(userId)!;
43    userTasks.push(newTask);
44  
45    // Sort tasks by due date to maintain order
46    userTasks.sort((a, b) => a.dueDate - b.dueDate);
47  
48    return newTask.taskId;
49}
50
51/**
52 * Retrieves all uncompleted tasks for a specific user, sorted by due date
53 * @param userId - The ID of the user
54 * @returns Array of task descriptions for uncompleted tasks
55 */
56function getAllTasks(userId: number): string[] {
57    const taskDescriptions: string[] = [];
58  
59    // Check if user has any tasks
60    if (userTasksMap.has(userId)) {
61        const userTasks = userTasksMap.get(userId)!;
62      
63        // Iterate through tasks (already sorted by due date)
64        for (const task of userTasks) {
65            // Only include uncompleted tasks
66            if (!task.isFinished) {
67                taskDescriptions.push(task.taskName);
68            }
69        }
70    }
71  
72    return taskDescriptions;
73}
74
75/**
76 * Retrieves all uncompleted tasks with a specific tag for a user
77 * @param userId - The ID of the user
78 * @param tag - The tag to filter by
79 * @returns Array of task descriptions that have the specified tag
80 */
81function getTasksForTag(userId: number, tag: string): string[] {
82    const taskDescriptions: string[] = [];
83  
84    // Check if user has any tasks
85    if (userTasksMap.has(userId)) {
86        const userTasks = userTasksMap.get(userId)!;
87      
88        // Iterate through tasks (already sorted by due date)
89        for (const task of userTasks) {
90            // Include only uncompleted tasks that contain the specified tag
91            if (task.tags.has(tag) && !task.isFinished) {
92                taskDescriptions.push(task.taskName);
93            }
94        }
95    }
96  
97    return taskDescriptions;
98}
99
100/**
101 * Marks a specific task as completed
102 * @param userId - The ID of the user who owns the task
103 * @param taskId - The ID of the task to complete
104 */
105function completeTask(userId: number, taskId: number): void {
106    // Check if user has any tasks
107    if (userTasksMap.has(userId)) {
108        const userTasks = userTasksMap.get(userId)!;
109      
110        // Search for the task with matching ID
111        for (const task of userTasks) {
112            if (task.taskId === taskId) {
113                // Mark task as finished
114                task.isFinished = true;
115                break;  // Exit loop once task is found
116            }
117        }
118    }
119}
120

Time and Space Complexity

Time Complexity:

  • __init__(): O(1) - Simple initialization of instance variables
  • addTask(): O(log m) where m is the number of tasks for the specific user, due to insertion into SortedList which maintains sorted order
  • getAllTasks(): O(m) where m is the number of tasks for the specific user, as it iterates through all tasks of that user
  • getTasksForTag(): O(m * t) where m is the number of tasks for the specific user and t is the average number of tags per task, as it checks tag membership for each task
  • completeTask(): O(m) where m is the number of tasks for the specific user, as it needs to linearly search through tasks to find the matching taskId

Space Complexity: O(n) where n is the total number of tasks across all users. The space is used to store:

  • The tasks dictionary which contains all tasks for all users
  • Each task stores: dueDate, taskDescription, tags set, taskId, and completion status
  • The SortedList data structure for each user maintains the tasks in sorted order by dueDate

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying SortedList Elements In-Place

The Pitfall: The most critical issue with this implementation is directly modifying elements within a SortedList. When we mark a task as completed with task[4] = True, we're changing the task object in-place. While this doesn't affect the sorting (since we sort by dueDate which is task[0]), it can lead to subtle bugs if the data structure implementation relies on immutability assumptions.

Why It's Problematic:

  • Some sorted container implementations may cache hash values or make assumptions about element immutability
  • If we later needed to sort by multiple fields (e.g., completion status + due date), the in-place modification would break the sort order without the SortedList knowing about it

Solution:

def completeTask(self, userId: int, taskId: int) -> None:
    tasks = self.user_tasks[userId]
    for i, task in enumerate(tasks):
        if task[3] == taskId and not task[4]:
            # Remove the old task
            removed_task = tasks.pop(i)
            # Create a new task with completed status
            completed_task = [
                removed_task[0],  # dueDate
                removed_task[1],  # description
                removed_task[2],  # tags
                removed_task[3],  # taskId
                True              # is_completed
            ]
            # Re-add the modified task
            tasks.add(completed_task)
            break

2. Missing Validation for Task Completion

The Pitfall: The current completeTask method doesn't verify if a task is already completed before marking it complete again. It also doesn't validate if the task actually belongs to the specified user (though the iteration inherently handles this).

Why It's Problematic:

  • Completing an already-completed task might trigger unwanted side effects in a real system (like sending duplicate notifications)
  • No feedback on whether the operation succeeded

Solution:

def completeTask(self, userId: int, taskId: int) -> bool:
    for task in self.user_tasks[userId]:
        if task[3] == taskId:
            if task[4]:  # Already completed
                return False
            task[4] = True
            return True
    return False  # Task not found

3. Using Mutable Default Arguments

The Pitfall: While not present in this code, a common mistake when working with collections is using mutable default arguments. If someone modified the code to have default tags like def addTask(..., tags=[]):, all tasks would share the same tags list.

Solution: Always use None as default and create a new list inside the function:

def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: List[str] = None) -> int:
    if tags is None:
        tags = []
    # ... rest of the implementation

4. Memory Leak from Completed Tasks

The Pitfall: Completed tasks are never removed from memory. Over time, users with many completed tasks will accumulate data that's rarely accessed but still consuming memory.

Why It's Problematic:

  • Memory usage grows unbounded
  • Performance of getAllTasks and getTasksForTag degrades as they must iterate through all tasks (including completed ones)

Solution: Periodically clean up or use a separate storage for completed tasks:

def __init__(self):
    self.task_id_counter = 1
    self.user_tasks = defaultdict(SortedList)
    self.completed_tasks = defaultdict(list)  # Archive completed tasks

def completeTask(self, userId: int, taskId: int) -> None:
    tasks = self.user_tasks[userId]
    for i, task in enumerate(tasks):
        if task[3] == taskId:
            completed_task = tasks.pop(i)
            completed_task[4] = True
            self.completed_tasks[userId].append(completed_task)
            break

5. Thread Safety Issues

The Pitfall: The current implementation is not thread-safe. If multiple threads access the same TodoList instance, race conditions can occur when incrementing task_id_counter or modifying task lists.

Solution: Use threading locks:

import threading

class TodoList:
    def __init__(self):
        self.task_id_counter = 1
        self.user_tasks = defaultdict(SortedList)
        self.lock = threading.Lock()
  
    def addTask(self, userId: int, taskDescription: str, dueDate: int, tags: List[str]) -> int:
        with self.lock:
            task_id = self.task_id_counter
            self.task_id_counter += 1
            # ... rest of the implementation
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More