Skip to content

636. Exclusive Time of Functions 👎

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
 public:
  vector<int> exclusiveTime(int n, vector<string>& logs) {
    vector<int> ans(n);
    stack<int> stack;  // [oldest_id, ..., latest_id]
    int prevTime;

    for (const string& log : logs) {
      // Get the seperators' indices.
      const int colon1 = log.find_first_of(':');
      const int colon2 = log.find_last_of(':');
      // Get the function_id, the label, and the timestamp.
      const int id = stoi(log.substr(0, colon1));  // {function_id}
      const char label = log[colon1 + 1];  // {"s" ("start") | "e" ("end") }
      const int timestamp = stoi(log.substr(colon2 + 1));  // {timestamp}
      if (label == 's') {
        if (!stack.empty())
          ans[stack.top()] += timestamp - prevTime;
        stack.push(id);
        prevTime = timestamp;
      } else {
        ans[stack.top()] += timestamp - prevTime + 1, stack.pop();
        prevTime = timestamp + 1;
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int[] exclusiveTime(int n, List<String> logs) {
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // [oldest_id, ..., latest_id]
    int prevTime = -1;

    for (final String log : logs) {
      final String[] splits = log.split(":");
      // Get the function_id, the label, and the timestamp.
      final int id = Integer.parseInt(splits[0]);        // {function_id}
      final char label = splits[1].charAt(0);            // {"s" ("start") | "e" ("end") }
      final int timestamp = Integer.parseInt(splits[2]); // {timestamp}
      if (label == 's') {
        if (!stack.isEmpty())
          ans[stack.peek()] += timestamp - prevTime;
        stack.push(id);
        prevTime = timestamp;
      } else {
        ans[stack.pop()] += timestamp - prevTime + 1;
        prevTime = timestamp + 1;
      }
    }

    return ans;
  }
}