2590. Design a Todo List

• Time:
  • Constructor: $O(1)$
  • addTask(userId: int, taskDescription, str, dueDate: int, tags: list[str]): $O(1)$
  • getAllTasks(userId: int): $O(|\texttt{tasks}| \log |\texttt{tasks}|)$
  • getTasksForTag(userId: int, tag: str): $O(|\texttt{tasks}| \log |\texttt{tasks}|)$
• Space: $O(|\texttt{addTask()}|)$

C++JavaPython

struct Task {
  // int taskId;
  string taskDescription;
  int dueDate;
  unordered_set<string> tags;

  bool operator<(const Task& other) const {
    return dueDate < other.dueDate;
  }
};

class TodoList {
 public:
  int addTask(int userId, string taskDescription, int dueDate,
              vector<string> tags) {
    userIdToTaskIdToTasks[userId][++taskId] =
        Task{.taskDescription = taskDescription,
             .dueDate = dueDate,
             .tags = {tags.begin(), tags.end()}};
    taskIds.insert(taskId);
    return taskId;
  }

  vector<string> getAllTasks(int userId) {
    vector<string> res;
    for (const Task& task : getTasksSortedByDueDate(userId))
      res.push_back(task.taskDescription);
    return res;
  }

  vector<string> getTasksForTag(int userId, string tag) {
    vector<string> res;
    for (const Task& task : getTasksSortedByDueDate(userId))
      if (task.tags.contains(tag))
        res.push_back(task.taskDescription);
    return res;
  }

  void completeTask(int userId, int taskId) {
    if (!taskIds.contains(taskId))
      return;
    const auto it = userIdToTaskIdToTasks.find(userId);
    if (it == userIdToTaskIdToTasks.cend())
      return;
    auto& taskIdToTasks = it->second;
    if (!taskIdToTasks.contains(taskId))
      return;
    taskIdToTasks.erase(taskId);
  }

 private:
  int taskId = 0;
  unordered_set<int> taskIds;
  // {userId: {taskId: tasks}}
  unordered_map<int, unordered_map<int, Task>> userIdToTaskIdToTasks;

  vector<Task> getTasksSortedByDueDate(int userId) {
    const auto it = userIdToTaskIdToTasks.find(userId);
    if (it == userIdToTaskIdToTasks.cend())
      return {};
    set<Task> tasks;
    for (const auto& [_, task] : it->second)
      tasks.insert(task);
    return {tasks.begin(), tasks.end()};
  }
};

class TodoList {
  public int addTask(int userId, String taskDescription, int dueDate, List<String> tags) {
    userIdToTaskIdToTasks.putIfAbsent(userId, new HashMap<>());
    userIdToTaskIdToTasks.get(userId).put(++taskId, new Task(taskDescription, dueDate, tags));
    taskIds.add(taskId);
    return taskId;
  }

  public List<String> getAllTasks(int userId) {
    List<String> res = new ArrayList<>();
    for (Task task : getTasksSortedByDueDate(userId))
      res.add(task.taskDescription);
    return res;
  }

  public List<String> getTasksForTag(int userId, String tag) {
    List<String> res = new ArrayList<>();
    for (Task task : getTasksSortedByDueDate(userId))
      if (task.tags.contains(tag))
        res.add(task.taskDescription);
    return res;
  }

  public void completeTask(int userId, int taskId) {
    if (!taskIds.contains(taskId))
      return;
    if (!userIdToTaskIdToTasks.containsKey(userId))
      return;
    Map<Integer, Task> taskIdToTasks = userIdToTaskIdToTasks.get(userId);
    if (!taskIdToTasks.containsKey(taskId))
      return;
    taskIdToTasks.remove(taskId);
  }

  private record Task(String taskDescription, int dueDate, List<String> tags) {}
  private int taskId = 0;
  private Set<Integer> taskIds = new HashSet<>();
  // {userId: {taskId: tasks}}
  private Map<Integer, Map<Integer, Task>> userIdToTaskIdToTasks = new HashMap<>();

  private List<Task> getTasksSortedByDueDate(int userId) {
    if (!userIdToTaskIdToTasks.containsKey(userId))
      return new ArrayList<>();
    TreeSet<Task> tasks = new TreeSet<>((a, b) -> Integer.compare(a.dueDate, b.dueDate));
    for (Task task : userIdToTaskIdToTasks.get(userId).values())
      tasks.add(task);
    return new ArrayList<>(tasks);
  }
}

from dataclasses import dataclass


@dataclass(frozen=True)
class Task:
  taskDescription: str
  dueDate: int
  tags: list[str]


class TodoList:
  def __init__(self):
    self.taskId = 0
    self.taskIds = set()
    self.userIdToTaskIdToTasks: dict[int, dict[int, list[Task]]] = {}

  def addTask(self, userId: int, taskDescription: str, dueDate: int,
              tags: list[str]) -> int:
    self.taskId += 1
    taskIdToTasks = self.userIdToTaskIdToTasks.setdefault(userId, {})
    taskIdToTasks[self.taskId] = Task(taskDescription, dueDate, tags)
    self.taskIds.add(self.taskId)
    return self.taskId

  def getAllTasks(self, userId: int) -> list[str]:
    return [task.taskDescription
            for task in self._getTasksSortedByDueDate(userId)]

  def getTasksForTag(self, userId: int, tag: str) -> list[str]:
    return [task.taskDescription
            for task in self._getTasksSortedByDueDate(userId)
            if tag in task.tags]

  def completeTask(self, userId: int, taskId: int) -> None:
    if taskId not in self.taskIds:
      return
    if userId not in self.userIdToTaskIdToTasks:
      return
    taskIdToTasks = self.userIdToTaskIdToTasks[userId]
    if taskId not in taskIdToTasks:
      return
    del taskIdToTasks[taskId]

  def _getTasksSortedByDueDate(self, userId: int) -> list[Task]:
    if userId not in self.userIdToTaskIdToTasks:
      return []
    taskIdToTasks = self.userIdToTaskIdToTasks[userId]
    return sorted(
        [task for task in taskIdToTasks.values()],
        key=lambda x: x.dueDate)