2590. Design a Todo List

MediumDesignArrayHash TableStringSorting

Problem Description

In this problem, we are tasked with designing a Todo List class that simulates a task management system. This system should allow users to add tasks, mark them as complete, and retrieve a list of their pending tasks. Each task can also have tags associated with it, which allows for additional organization and the ability to filter tasks by a specific tag.

Here are the main functionalities that the TodoList class needs to support:

Initialization of the TodoList object.
Addition of tasks, where each task has a unique sequential ID, a textual description, a due date, and a list of tags.
Retrieval of all uncompleted tasks for a user, sorted by due date.
Retrieval of all uncompleted tasks for a user that have a specific tag, sorted by due date.
Completion of a task by marking it as done, provided that the task exists and belongs to the user.

The challenge here is to efficiently handle the addition, completion, and retrieval of tasks for potentially many users while maintaining the ordering of tasks by due date and allowing tag-based filtering.

Intuition

To approach this solution, we need a data structure that can maintain the tasks in sorted order by their due date and facilitate the searching, filtering, and updating of tasks efficiently.

The key components of the design are:

A hash table (or a default dict in Python), which maps each user's ID to their set of tasks. This structure allows us to quickly access the tasks per user.
A sorted set to maintain the tasks sorted by due date. This is useful for efficiently retrieving tasks in the desired order.
Keeping a global task ID counter that increments sequentially as new tasks are added, ensuring unique and sequentially increasing task IDs.
Representing each task with a list that contains the due date, task description, set of tags, task ID, and a boolean flag indicating whether the task has been completed.

To add a task, we insert it into the user's sorted set of tasks with all the necessary information. Since we are using a sorted set, the due date ordering is maintained automatically. The unique task ID is generated using the global task ID counter.

When retrieving all tasks or tasks by a specific tag, we iterate through the user's set of tasks, selecting those that are not marked as completed. For tag-specific retrieval, we check if the tag is in the set of tags associated with the task.

Finally, to mark a task as complete, we iterate over the user's tasks and update the completion flag for the task with the matching task ID. This change is reflected in place since the tasks are stored as lists and the sorted set merely points to these lists.

Overall, this solution's efficiency stems from the ability of the sorted containers in Python to maintain the order and support fast searching and insertion operations.

Learn more about Sorting patterns.

Solution Approach

The implementation of the TodoList class in the reference solution uses several algorithms and data structures which are essential to achieve the desired functionalities of adding tasks, retrieving tasks, filtering tasks by tags, and marking tasks as complete.

Here is the breakdown of the solution:

Initialization (__init__ method): We start by initializing an instance variable i to 1. This variable will serve as the global task ID incrementing sequentially with each new task. We also create a tasks hash table (defaultdict of SortedList). Each key in the tasks dictionary represents a user's ID and the corresponding value is a SortedList. The SortedList is used because it maintains the ordering of tasks by their due date while still allowing for efficient task retrieval.
Adding Tasks (addTask method): When a new task is added with addTask, a new task ID is created from the i variable. The task information is stored in a list, which includes the due date, task description, a set of tags, the newly created task ID, and a boolean flag for task completion status (initially False). This list is added to the sorted list associated with the user's ID in the tasks dictionary. The sorted list ensures that tasks remain sorted by due date. After inserting the task, the task ID counter i is incremented, and the new task ID is returned.
Retrieving All Tasks (getAllTasks method): The getAllTasks method iterates through the sorted list of tasks for the user specified by userId, and filters out tasks that are not yet completed. It then creates a list containing the descriptions of the pending tasks, preserving the order by due date. This is achieved with a list comprehension that checks the completion status of each task (x[4]).
Filtering Tasks by Tag (getTasksForTag method): Similarly to getAllTasks, this method also iterates through the tasks of a particular user, but it includes an additional check to see if the specified tag exists in the set of tags for the task. Tasks that meet both criteria (uncompleted and containing the tag) have their descriptions included in the result list.
Completing a Task (completeTask method): To mark a task as completed, the method iterates over the user's task list, locates the task by the task ID (taskId), and sets the completion flag to True if the task is found. This marks the task as completed without removing it from the list, which means the task will be omitted when calling getAllTasks or getTasksForTag.

The aforementioned operations rely heavily on iterating over the sorted set of tasks, but it should be noted that the size of the task set per user could potentially become large. Optimization for marking tasks as completed could be achieved if the data structure allowed direct access to tasks by their ID, which would eliminate the need to iterate over the list; however, in this implementation, such direct access is traded off for simpler code.

In terms of time complexity, adding tasks is O(log n) due to the insertion into a sorted list, retrieving all tasks or tasks by tag is O(n) since it involves iterating over all tasks, and completing a task is O(n) for locating the specific task within the list.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's create an instance of the TodoList class and walk through each of the functionalities using a simple example:

Initialize the TodoList instance:
- Create todoList = TodoList(). This initializes the tasks dictionary and sets the global task ID i to 1.
Add tasks:
- User with ID 1 adds a task: "Buy groceries" with due date "2023-04-20" and tags ['shopping', 'urgent'].
  - We call taskId1 = todoList.addTask(1, "2023-04-20", "Buy groceries", ['shopping', 'urgent']). The system returns taskId1 as 1.
- Same user adds another task: "Pay bills" with due date "2023-04-22" and a tag ['finance'].
  - We call taskId2 = todoList.addTask(1, "2023-04-22", "Pay bills", ['finance']). The system returns taskId2 as 2.
- Now, the tasks dictionary has one key (user 1) with a SortedList holding two tasks sorted by due date.
Retrieve all uncompleted tasks:
- We call list1 = todoList.getAllTasks(1). This would iterate over the SortedList for user 1 and return a list with descriptions of pending tasks. Since both tasks are uncompleted, it would return ["Buy groceries", "Pay bills"] in sorted order by due date.
Retrieve tasks by a specific tag:
- We want to see all uncompleted shopping tasks for user 1, so we call shoppingTasks = todoList.getTasksForTag(1, "shopping"). This would return ["Buy groceries"], filtering by the tag and ensuring the task is not completed.
Complete a task:
- User 1 completes the task "Buy groceries". We call todoList.completeTask(1, taskId1). This sets the completion flag for task with taskId1 to True.
- Now if we call todoList.getAllTasks(1) again, it would return ["Pay bills"] only, since the "Buy groceries" task has been marked as complete.

In this example, the use of SortedList ensures that tasks remain sorted by their due date without additional sorting steps each time a query is made. It also illustrates the benefit of storing tasks with completion status and tags, allowing for efficient filtering without affecting the original task list ordering. The encapsulation of task data and operations in the TodoList class provides a clean interface for managing user tasks.

Solution Implementation

1from collections import defaultdict
2from typing import List, Set, Tuple
3
4class TodoList:
5    def __init__(self):
6        self.task_counter = 1  # Initialize task counter to assign unique IDs to tasks
7        self.tasks = defaultdict(list)  # Use a default dictionary to store tasks for each user
8
9    def addTask(
10        self, user_id: int, task_description: str, due_date: int, tags: List[str]
11    ) -> int:
12        """
13        Add a task to the TodoList for a given user. Returns the task ID.
14        :param user_id: Integer representing the user ID.
15        :param task_description: String representing the task description.
16        :param due_date: Integer representing the task's due date.
17        :param tags: List of strings representing the tags associated with the task.
18        :return: Integer representing the newly created task ID.
19        """
20        task_id = self.task_counter
21        self.task_counter += 1
22        # Add the task with its attributes as a tuple to the user's task list
23        self.tasks[user_id].append((due_date, task_description, set(tags), task_id, False))
24        self.tasks[user_id].sort()  # Ensure that tasks are sorted by due date
25        return task_id
26
27    def getAllTasks(self, user_id: int) -> List[str]:
28        """
29        Retrieve all incomplete tasks for a given user.
30        :param user_id: Integer representing the user ID.
31        :return: List of strings containing task descriptions for incomplete tasks.
32        """
33        return [task[1] for task in self.tasks[user_id] if not task[4]]  # Filter out completed tasks
34
35    def getTasksForTag(self, user_id: int, tag: str) -> List[str]:
36        """
37        Retrieve all incomplete tasks for a given user that have a specified tag.
38        :param user_id: Integer representing the user ID.
39        :param tag: String representing the tag to filter tasks by.
40        :return: List of strings containing task descriptions that match the tag.
41        """
42        # Filter tasks by the specified tag and completion status
43        return [task[1] for task in self.tasks[user_id] if not task[4] and tag in task[2]]
44
45    def completeTask(self, user_id: int, task_id: int) -> None:
46        """
47        Mark a task as complete for a given user.
48        :param user_id: Integer representing the user ID.
49        :param task_id: Integer representing the task ID to be marked as complete.
50        """
51        # Find the task by its ID and mark it as complete
52        for task in self.tasks[user_id]:
53            if task[3] == task_id:
54                task[4] = True
55                break  # Once the task is found and marked, exit the loop
56
57# Your TodoList object will be instantiated and called as such:
58# obj = TodoList()
59# param_1 = obj.addTask(user_id,task_description,due_date,tags)
60# param_2 = obj.getAllTasks(user_id)
61# param_3 = obj.getTasksForTag(user_id,tag)
62# obj.completeTask(user_id,task_id)
63

1import java.util.*;
2
3class Task {
4    int id; // Task identifier
5    String name; // Description of the task
6    int dueDate; // Due date for the task
7    Set<String> tags; // A set of tags associated with the task
8    boolean isCompleted; // Flag to indicate if the task is completed
9
10    // Constructor to initialize task properties
11    public Task(int id, String name, int dueDate, Set<String> tags) {
12        this.id = id;
13        this.name = name;
14        this.dueDate = dueDate;
15        this.tags = tags;
16        this.isCompleted = false; // By default, the task is not completed
17    }
18}
19
20class TodoList {
21    private int nextTaskId = 1; // Counter to generate unique task IDs
22    private Map<Integer, TreeSet<Task>> userTasksMap = new HashMap<>(); // Mapping from user ID to a set of tasks
23
24    // TodoList constructor
25    public TodoList() {
26    }
27
28    // Method to add a new task for a user and return the new task ID
29    public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
30        // Create a new task object
31        Task newTask = new Task(nextTaskId++, taskDescription, dueDate, new HashSet<>(tags));
32        // Add the task to the user's set of tasks, sorted by due date
33        userTasksMap.computeIfAbsent(userId, k -> new TreeSet<>(Comparator.comparingInt(task -> task.dueDate)))
34            .add(newTask);
35        // Return the assigned task ID
36        return newTask.id;
37    }
38
39    // Method to get all incomplete tasks for a user
40    public List<String> getAllTasks(int userId) {
41        List<String> taskDescriptions = new ArrayList<>();
42        if (userTasksMap.containsKey(userId)) {
43            for (Task task : userTasksMap.get(userId)) {
44                // Check if the task is not completed
45                if (!task.isCompleted) {
46                    taskDescriptions.add(task.name);
47                }
48            }
49        }
50        return taskDescriptions;
51    }
52
53    // Method to get all incomplete tasks for a user by a specific tag
54    public List<String> getTasksForTag(int userId, String tag) {
55        List<String> taskDescriptionsForTag = new ArrayList<>();
56        if (userTasksMap.containsKey(userId)) {
57            for (Task task : userTasksMap.get(userId)) {
58                // Check if the task includes the tag and is not completed
59                if (task.tags.contains(tag) && !task.isCompleted) {
60                    taskDescriptionsForTag.add(task.name);
61                }
62            }
63        }
64        return taskDescriptionsForTag;
65    }
66
67    // Method to mark a task as completed for a user by task ID
68    public void completeTask(int userId, int taskId) {
69        if (userTasksMap.containsKey(userId)) {
70            for (Task task : userTasksMap.get(userId)) {
71                // Find the task with the given ID and mark it as completed
72                if (task.id == taskId) {
73                    task.isCompleted = true;
74                    break; // No need to look further as task IDs are unique
75                }
76            }
77        }
78    }
79}
80
81/**
82 * The TodoList class can be used as follows:
83 * TodoList todoList = new TodoList();
84 * int taskId = todoList.addTask(userId, taskDescription, dueDate, tags);
85 * List<String> allTasks = todoList.getAllTasks(userId);
86 * List<String> tasksForTag = todoList.getTasksForTag(userId, tag);
87 * todoList.completeTask(userId, taskId);
88 */
89

1#include <set>
2#include <map>
3#include <string>
4#include <vector>
5#include <algorithm>
6#include <functional>
7
8// Task struct which will store information about each task
9struct Task {
10    int id;                          // Task identifier
11    std::string name;                // Description of the task
12    int dueDate;                     // Due date for the task
13    std::set<std::string> tags;      // A set of tags associated with the task
14    bool isCompleted;                // Flag to indicate if the task is completed
15
16    // Constructor to initialize task properties
17    Task(int id, std::string name, int dueDate, const std::set<std::string>& tags) 
18        : id(id), name(std::move(name)), dueDate(dueDate), tags(tags), isCompleted(false) {
19        // By default, the task is not completed
20    }
21};
22
23// Comparison function for sorting Tasks by due date
24auto compareTasks = [](const Task& lhs, const Task& rhs) {
25    return lhs.dueDate < rhs.dueDate;
26};
27
28// TodoList class which will manage tasks for each user
29class TodoList {
30private:
31    int nextTaskId = 1; // Counter to generate unique task IDs
32    // Mapping from user ID to a set of tasks, which are sorted by their due date
33    std::map<int, std::set<Task, decltype(compareTasks)>> userTasksMap;
34
35public:
36    // TodoList constructor
37    TodoList() : userTasksMap(compareTasks) {
38    }
39
40    // Method to add a new task for a user and return the new task ID
41    int AddTask(int userId, const std::string& taskDescription, int dueDate, const std::vector<std::string>& tags) {
42        // Create a new task object with a unique ID
43        Task newTask(nextTaskId++, taskDescription, dueDate, std::set<std::string>(tags.begin(), tags.end()));
44        // Add the task to the user's set of tasks
45        userTasksMap[userId].insert(newTask);
46        // Return the newly assigned task ID
47        return newTask.id;
48    }
49
50    // Method to get all incomplete tasks for a user
51    std::vector<std::string> GetAllTasks(int userId) {
52        std::vector<std::string> taskDescriptions;
53        if (userTasksMap.find(userId) != userTasksMap.end()) { 
54            for (const Task& task : userTasksMap[userId]) {
55                if (!task.isCompleted) {
56                    taskDescriptions.push_back(task.name);
57                }
58            }
59        }
60        return taskDescriptions;
61    }
62
63    // Method to get all incomplete tasks for a user by a specific tag
64    std::vector<std::string> GetTasksForTag(int userId, const std::string& tag) {
65        std::vector<std::string> taskDescriptionsForTag;
66        auto it = userTasksMap.find(userId);
67        if (it != userTasksMap.end()) {
68            for (const Task& task : it->second) {
69                if (task.tags.count(tag) && !task.isCompleted) {
70                    taskDescriptionsForTag.push_back(task.name);
71                }
72            }
73        }
74        return taskDescriptionsForTag;
75    }
76
77    // Method to mark a task as completed for a user by task ID
78    void CompleteTask(int userId, int taskId) {
79        auto it = userTasksMap.find(userId);
80        if (it != userTasksMap.end()) {
81            auto& tasks = it->second;
82            auto taskIt = std::find_if(tasks.begin(), tasks.end(), [taskId](const Task& task) { return task.id == taskId; });
83            if (taskIt != tasks.end()) {
84                taskIt->isCompleted = true;
85            }
86        }
87    }
88};
89
90/**
91 * The TodoList class can be used as follows:
92 * TodoList todoList;
93 * int taskId = todoList.AddTask(userId, taskDescription, dueDate, tags);
94 * std::vector<std::string> allTasks = todoList.GetAllTasks(userId);
95 * std::vector<std::string> tasksForTag = todoList.GetTasksForTag(userId, tag);
96 * todoList.CompleteTask(userId, taskId);
97 */
98

1interface Task {
2    id: number;
3    name: string;
4    dueDate: number;
5    tags: Set<string>;
6    isCompleted: boolean;
7}
8
9// Comparator function for sorting tasks by due date
10function sortByDueDate(a: Task, b: Task) : number {
11    return a.dueDate - b.dueDate;
12}
13
14let nextTaskId = 1; // Counter to generate unique task IDs
15let userTasksMap: Map<number, Set<Task>> = new Map(); // Mapping from user ID to a set of tasks
16
17// Adds a new task for a user and returns the new task ID
18function addTask(userId: number, taskDescription: string, dueDate: number, tags: string[]): number {
19    const newTask: Task = {
20        id: nextTaskId++,
21        name: taskDescription,
22        dueDate: dueDate,
23        tags: new Set(tags),
24        isCompleted: false // By default, the task is not completed
25    };
26
27    // Add the task to the user's set of tasks, sorted by due date
28    const tasks = userTasksMap.get(userId) || new Set<Task>();
29    tasks.add(newTask);
30    userTasksMap.set(userId, tasks);
31
32    return newTask.id;
33}
34
35// Gets all incomplete tasks for a user
36function getAllTasks(userId: number): string[] {
37    const tasks: string[] = [];
38    const userTasks = userTasksMap.get(userId);
39    if (userTasks) {
40        for (let task of Array.from(userTasks).sort(sortByDueDate)) {
41            if (!task.isCompleted) {
42                tasks.push(task.name);
43            }
44        }
45    }
46    return tasks;
47}
48
49// Gets all incomplete tasks for a user by a specific tag
50function getTasksForTag(userId: number, tag: string): string[] {
51    const tasksForTag: string[] = [];
52    const userTasks = userTasksMap.get(userId);
53    if (userTasks) {
54        for (let task of Array.from(userTasks).sort(sortByDueDate)) {
55            if (!task.isCompleted && task.tags.has(tag)) {
56                tasksForTag.push(task.name);
57            }
58        }
59    }
60    return tasksForTag;
61}
62
63// Marks a task as completed for a user by task ID
64function completeTask(userId: number, taskId: number): void {
65    const userTasks = userTasksMap.get(userId);
66    if (userTasks) {
67        for (let task of userTasks) {
68            // Find the task with the given ID and mark it as completed
69            if (task.id === taskId) {
70                task.isCompleted = true;
71                break; // No need to look further as task IDs are unique
72            }
73        }
74    }
75}
76

Time and Space Complexity

Time Complexity

addTask() has a time complexity of O(log n) for a particular user where n is the number of tasks of that user, because it involves adding a task to the SortedList, which takes logarithmic time for insertion.
getAllTasks() has a time complexity of O(m), where m is the number of incomplete tasks for the user, since it requires iterating through all tasks to filter out completed ones and collect descriptions.
getTasksForTag() also has a time complexity of O(m), where m is again the number of incomplete tasks for the user. This is because it filters tasks by a specific tag.
completeTask() has a time complexity of O(m) where m is the number of tasks of a user. In the worst case, it involves iterating through all the tasks to find the one with the specified taskId.

Space Complexity

The overall space complexity of the TodoList class is O(n), where n is the total number of all tasks across all users. This accounts for the storage of task details (due date, description, tags, taskId, and completion status) in the tasks data structure.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What does the following code do?

1def f(arr1, arr2):
2  i, j = 0, 0
3  new_arr = []
4  while i < len(arr1) and j < len(arr2):
5      if arr1[i] < arr2[j]:
6          new_arr.append(arr1[i])
7          i += 1
8      else:
9          new_arr.append(arr2[j])
10          j += 1
11  new_arr.extend(arr1[i:])
12  new_arr.extend(arr2[j:])
13  return new_arr
14

1public static List<Integer> f(int[] arr1, int[] arr2) {
2  int i = 0, j = 0;
3  List<Integer> newArr = new ArrayList<>();
4
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.add(arr1[i]);
8          i++;
9      } else {
10          newArr.add(arr2[j]);
11          j++;
12      }
13  }
14
15  while (i < arr1.length) {
16      newArr.add(arr1[i]);
17      i++;
18  }
19
20  while (j < arr2.length) {
21      newArr.add(arr2[j]);
22      j++;
23  }
24
25  return newArr;
26}
27

1function f(arr1, arr2) {
2  let i = 0, j = 0;
3  let newArr = [];
4  
5  while (i < arr1.length && j < arr2.length) {
6      if (arr1[i] < arr2[j]) {
7          newArr.push(arr1[i]);
8          i++;
9      } else {
10          newArr.push(arr2[j]);
11          j++;
12      }
13  }
14  
15  while (i < arr1.length) {
16      newArr.push(arr1[i]);
17      i++;
18  }
19  
20  while (j < arr2.length) {
21      newArr.push(arr2[j]);
22      j++;
23  }
24  
25  return newArr;
26}
27

Find the intersection of two arrays.

Check if one array is a subsequence of the other.

Merge two sorted arrays.

Finding median values of 2 arrays.

I don’t know