Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

636. Exclusive Time of Functions

Time: $O(n)$

Space: $O(n)$

			


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 seperators' indices
      const int colon1 = log.find_first_of(':');
      const int colon2 = log.find_last_of(':');
      // Get function_id, label, and 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;
  }
};




			


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 function_id, label, and 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;
  }
}