636. Exclusive Time of Functions - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement:

On a single-threaded CPU, we have n functions labeled from 0 to n-1. We receive a list of logs describing when each function starts and ends. Each log entry is a string in the format:

"{function_id}:{start or end}:{timestamp}"

For example, "0:start:3" means function 0 started at the beginning of time unit 3, and "1:end:2" means function 1 ended at the end of time unit 2 . Because the CPU is single-threaded, only one function runs at any given time .

When a function starts, it pauses the current running function (if any) and that function will resume only after the new function ends. A function’s exclusive time is the total time spent executing in the CPU for that function alone, excluding time spent in any other function calls it invoked . If a function is called multiple times (even recursively), we sum up all the time it spent running.

The task is to return an array of length n where the value at index i is the exclusive time of function i in the execution logs.

Example 1:
```
n = 2  
logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
```
Output: [3, 4]
Explanation: Function 0 starts at time 0 and runs until time 1 (2 units of time). Then function 1 starts at time 2, runs until time 5 (4 units). After that, function 0 resumes at time 6 and ends at time 6 (1 unit). So, total exclusive time = 0 runs 2+1 = 3 units, 1 runs 4 units .
Example 2:
```
n = 2  
logs = ["0:start:0", "0:start:2", "0:end:5", "1:start:6", "1:end:6", "0:end:7"]
```
Output: [7, 1]
Explanation: Function 0 starts at time 0 and then calls itself (recursive call) at time 2. The inner call of 0 runs from 2 to 5 (4 units). Function 0 (outer call) was paused during that period but had run 2 units before (time 0 to 1). After the inner call ends, at time 6 function 0 calls function 1, which runs only at time 6 (1 unit). Finally, function 0 resumes at time 7 for 1 unit and ends. Total time for function 0 = 2 (before recursion) + 4 (inner recursion) + 1 (after) = 7. Function 1 = 1 unit.
Example 3:
```
n = 3  
logs = [
  "0:start:0",
  "1:start:1",
  "2:start:2",
  "2:end:3",
  "1:end:4",
  "0:end:5"
]
```
Output: [2, 2, 2]
Explanation: Function 0 starts at 0. At time 1, function 1 starts, pausing 0. At time 2, function 2 starts, pausing 1. Function 2 runs from 2 to 3 (2 units). Function 1 then resumes at 4 and runs until 4 (1 unit, since it had run 1 unit at time 1 before pausing). Function 0 resumes at 5 and runs for 1 unit (it had run 1 unit at time 0 before). So each function ran 2 units in total.

Constraints:

1 <= n <= 100 (number of functions)
The logs are given in increasing timestamp order. No two functions start or end at the same time stamp (so no ties in logs) .
Every "start" log has a matching "end" log for the same function (functions always log when they exit).
The output array should include an entry for every function ID from 0 to n-1 (if a function never ran, its time will be 0).

Hints:

Understand the scenario: Since the CPU is single-threaded, at any time there is only one active function. When a new function starts, the previous one is put on hold. Think of how a call stack works in programming – when a function calls another, the caller is paused until the callee finishes.
Track the running function: We need to know which function is currently running as we go through the logs. A suitable data structure for managing function calls (especially nested ones) is a stack. Whenever a function starts, push its ID onto the stack, and when it ends, pop it. The function on top of the stack is the one running.
Use time differences: To calculate exclusive time, consider the difference in timestamps between events. When a new function starts at time t, the function that was previously on the stack ran exclusively from the last recorded time up to t-1. When a function ends at time t, it ran from the last recorded time up to t (inclusive). Be careful with the inclusive end – if a function ends at time t, that entire time unit t counts toward that function’s time.
Approach step-by-step: Parse each log entry. If it's a "start", record the time for the currently running function and then push the new function. If it's an "end", add the elapsed time to that function and pop it from the stack, then resume the previous one. Maintaining a prevTime (the time of the last processed log) is helpful to compute time differences.

Approaches:

1. Brute Force Approach:

Logic: A straightforward (but inefficient) way to solve this is to simulate the execution timeline time unit by time unit. We can iterate through each unit of time between the earliest and latest timestamp, keeping track of which function is running. This can be done by using a stack to mirror the function call stack, but instead of jumping directly in time, we increment one unit at a time:

Initialize an array result of size n with all 0s to accumulate exclusive times.
Parse the logs into a structured form (e.g., list of tuples (id, type, timestamp)).
Use a stack to track active functions. Also keep a currentFunction variable and a currentTime pointer.
Iterate through time from the first log’s timestamp to the last log’s timestamp, advancing one unit at a time:
- If a new function starts at the current time, push it to the stack and update currentFunction.
- If the current function ends at this time, pop it from the stack. The function’s end log means it finished at this time.
- Otherwise, if no new event at this time, it means the currentFunction continues running.
- For each time unit, increment the count for the currentFunction in result.
Continue until all logs are processed and time has reached the end of the last event.

This brute-force simulation will correctly accumulate each function’s exclusive running time. However, it is not efficient if the timeline is large. Its time complexity can be as bad as O(T) where T is the total time span of execution (which could be much larger than the number of log entries). For example, if the first log is at time 0 and the last log is at time 1,000,000, this approach would iterate a million steps. We will implement it for clarity, but then we’ll explore an optimal approach.

Python Implementation (Brute Force):

Python3

. . . .

Java Implementation (Brute Force):

Java

. . . .

Complexity Analysis (Brute Force):

Time Complexity: In the worst case, if the time span of the logs is large, this approach iterates through each time unit in that span. If the last timestamp is T, complexity is about O(T). This can be very inefficient if T is big (for instance, 10^6 or more). For each time unit we do O(1) operations, but T could far exceed the number of logs. For a smaller timeline, it works fine, but generally this is not optimal.
Space Complexity: O(n + m) where n is the number of functions and m is the number of log entries. We use O(n) for the result array and up to O(m) for the stack in the worst case of deep nesting. If we explicitly stored a timeline array it would be O(T) space, but in the above implementation we avoided that. The stack and parsed events list use space proportional to the logs.

2. Optimal Stack-Based Approach:

Key Observations:
The inefficiency in the brute-force method comes from iterating over each individual time unit. We can do better by leveraging the fact that the input already partitions the timeline into segments (between log events). Instead of unit-by-unit simulation, we jump between log timestamps and accumulate time differences. The stack-based approach effectively does this in one pass:

Use a stack to keep track of active function calls (function IDs). The function on top of the stack is currently running.
Keep a variable prevTime to remember the timestamp of the last processed log event. This helps in calculating the duration that the top function was running since the last event.
Iterate through each log in order:
- If it's a "start" event for function f at time t:
  - If another function was running (stack not empty), then from prevTime up to t-1, that previous function was running exclusively. So we add (t - prevTime) to the exclusive time of the function on top of the stack.
  - Push f onto the stack (now f is the current running function).
  - Update prevTime = t because the new function starts at time t.
- If it's an "end" event for function f at time t:
  - The function on top of the stack (which should be f) ran from prevTime up to and including t. So its run duration for this segment is (t - prevTime + 1). Add that to f’s exclusive time.
  - Pop f from the stack (function f has finished).
  - Update prevTime = t + 1 because after time t finishes, the next active time will be t+1 (the next time unit after f ended). If there is a parent function beneath in the stack, it will resume at t+1.

These steps rely on carefully handling the time intervals. The prevTime helps ensure we don’t double count time across events. The +1 on an "end" event accounts for the inclusive end time. (Remember, if a function ends at time t, it occupies the entire unit of time t .)

By processing the logs this way, we account for all execution time in segments defined by the log events, rather than every unit. This yields a linear solution.

Step-by-Step Breakdown of Stack Approach:

Initialize result = [0]*n, an empty stack, and set prevTime to 0.
For each log entry in logs:
- Parse the entry into id, action, timestamp.
- If action == "start":
  - If stack not empty, let top = stack[-1] (currently running function). Update result[top] += timestamp - prevTime (the function on top ran from prevTime to just before this new start time).
  - Push id onto stack (function id starts running).
  - Set prevTime = timestamp.
- If action == "end":
  - Let top = stack.pop() (this should equal id). Update result[top] += timestamp - prevTime + 1. (Add the time from prevTime to timestamp inclusive to this function’s time.)
  - Set prevTime = timestamp + 1 (next time unit after the function ended).
Return result.

Using this algorithm, each log is processed once, and each function ID is pushed and popped at most once from the stack in sequence, making it very efficient.

Python Implementation (Optimal):

Python3

. . . .

Java Implementation (Optimal):

Java

. . . .

Complexity Analysis (Optimal Stack Solution):

Time Complexity: O(m), where m is the number of log entries. We go through each log once and perform O(1) operations for each (push, pop, arithmetic). This is much better than iterating over each time unit. The time complexity is linear in the size of the input logs.
Space Complexity: O(n) for the result array and up to O(m) for the stack in the worst case (if logs are deeply nested, the stack could hold many function IDs at once). In the worst scenario of maximum nesting (which is bounded by m, and m itself is at most 2 * number of function calls), the stack is O(m). However, since each function start must eventually have an end, the stack will at most grow to the depth of nested calls. Typically, we consider the space as O(n + m) ~ O(m) in the worst case, which for practical input sizes is fine (and m itself is limited by program call structure).

Step-by-Step Walkthrough:

To illustrate how the stack-based algorithm works, let’s walk through Example 1 in detail, using the optimal approach:

Example 1 Revisited: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"] – expected output [3,4].

Now, let's simulate the log processing step by step, maintaining a stack and prevTime:

Initial State: stack = [], prevTime = 0, result = [0, 0]. No function is running yet.
Log 1: "0:start:0" – Function 0 starts at time 0.
- Stack was empty, so no previously running function to update.
- Push 0 onto the stack. Now stack = [0].
- Set prevTime = 0 (the start time of function 0).
- Current running function is 0.
  (No time has elapsed yet; we just set up the initial state with function 0 running.)
Log 2: "1:start:2" – Function 1 starts at time 2. This will pause function 0.
- The top of the stack is 0 (function 0 was running). We calculate time since prevTime: from 0 to 1 (since the new event is at time 2, function 0 ran up to time 1). That duration is 2 - 0 = 2 units.
- Add this to result[0]: now result = [2, 0] (function 0 has 2 units so far).
- Push 1 onto the stack (stack = [0, 1]). Function 1 is now on top and becomes the current running function.
- Update prevTime = 2 (function 1’s start time).
- Status: Function 0 is paused at time 2, function 1 is running from time 2 onward.
Log 3: "1:end:5" – Function 1 ends at time 5.
- The top of the stack is 1 (function 1 itself, as expected). Calculate its running time since prevTime: from 2 to 5 inclusive. That duration is 5 - 2 + 1 = 4 units.
- Add to result[1]: now result = [2, 4]. (Function 1 ran for 4 time units total.)
- Pop 1 from the stack (stack becomes [0] again). Function 1 is done, so we resume the previous function.
- Update prevTime = 5 + 1 = 6. We set prevTime to 6 because the next time unit after function 1’s end is 6. This is when function 0 will resume.
- Status: Function 1 has finished. Function 0 is now back on top of the stack and will continue from time 6.
Log 4: "0:end:6" – Function 0 ends at time 6.
- Top of stack is 0. Calculate running time from prevTime (which is 6) to 6 inclusive: 6 - 6 + 1 = 1 unit.
- Add to result[0]: result becomes [2+1, 4] = [3, 4]. (Function 0 ran 1 more unit after resuming, totaling 3.)
- Pop 0 from stack, now stack is empty.
- Update prevTime = 6 + 1 = 7 (though we have no more logs, this indicates the end of all processing at time 7).
- Status: All functions have finished, stack is empty, and we have our result.

At the end, result = [3, 4], which matches the expected output. We correctly accounted 3 units to function 0 and 4 units to function 1. Notice how the use of prevTime and the stack ensured we allocated each time segment to the right function. Function 0’s time was split into two segments (before calling function 1, and after function 1), and function 1’s time was calculated while it was on top of the stack. We never double-counted or lost any time units.

For Example 2 and Example 3, the same algorithm applies. The stack will grow deeper for nested calls and unwind as calls end, but the logic of updating the result with time differences remains consistent. The inclusive end logic (+1) ensures that end timestamps are counted for the function that ends. If you walk through those examples, you would see the prevTime jump forward appropriately and each function’s time accumulating correctly.

Additional Insights:

Common Mistakes:
- Off-by-one errors: Forgetting to add the inclusive end time can result in undercounting. Always remember that when a function ends at time t, it occupies that entire time unit t. That’s why we do time - prevTime + 1 on an end event. If you omit the +1 or handle timestamps incorrectly, results will be wrong.
- Not updating prevTime correctly: This is crucial. If prevTime isn’t moved to the right value after each event, the next time difference calculation will be off. For a start event, after pushing the new function, prevTime should remain at the start time of the new function (since that time will be counted for the new function going forward). For an end event, prevTime should jump to end_time + 1 (the next unit after the function ended). Skipping these updates or doing them in the wrong place can cause errors.
- Mismatched push/pop: Make sure that when you see an "end" log for function X, the stack’s top is indeed X. The input guarantees well-formed logs, but a logical error in code could lead to mismanaging the stack. Each "start" should push one ID, and each "end" should pop the same ID. If these get out of sync, the results will be nonsense.
- Ignoring multiple calls: Some might assume each function is called only once. Remember, a function ID can appear multiple times in the logs (recursion or repeated calls). Our result array should accumulate all time for each ID across all calls.

Edge Cases:

Single function: If n=1, there will be just one function’s start and end logs. The exclusive time is simply the difference between start and end plus one. For example, ["0:start:5","0:end:7"] should output [3] (ran from time 5 to 7 inclusive = 3 units). Our algorithm handles this by an empty stack at first, pushing 0 at start, then on end adding 7-5+1.
Back-to-back calls: If one function ends and another begins at the next moment, e.g., ... "a:end:10", "b:start:11", ..., the calculation still holds. The first function gets time up to 10, then we set prevTime = 11 and start the next. If a new function starts exactly when another ends (which by problem constraints shouldn’t happen at the same exact time stamp), our approach can still handle it by the order of operations (end event processes and then start event).
No nested calls (flat sequence): If functions are called one after another without overlap, the stack will mostly have one element at a time. Each function’s time will just be its total runtime. The algorithm still works (it will just add big chunks for each function and the stack rarely has more than one item).
Deeply nested calls: The approach naturally handles deep recursion. The stack will grow, and each new start pauses the previous function. Ensure that your recursion depth (or stack size) doesn’t exceed any limits (in Python, a list can grow, and in Java, a Deque can grow – given n <= 100 and well-formed calls, it won’t blow up).
Function never called: If a function ID from 0 to n-1 never appears in any log, its exclusive time remains 0. Our result array is initialized to 0 for all, and we only add time when a function is encountered in logs. So those will correctly stay 0.

Alternative Variations:

This problem is essentially parsing and distributing time intervals. An alternative way to think about it is to break each function’s runtime into segments by subtracting out the time consumed by inner calls. For instance, one could try a recursion-based approach: whenever you find a start, recursively process its inner calls until the matching end, then compute exclusive time by subtracting child times from total time. This is more complex to implement and essentially mirrors what the stack does implicitly. Another variation could be if the logs were not sorted by time; then the first step would be to sort them (but the problem guarantees they are sorted by timestamp).

A more advanced twist might be if this were a multi-threaded scenario (multiple CPUs). In that case, functions could run in parallel, and exclusive time calculation would be different (you’d be summing segments possibly running concurrently). Our single-thread assumption simplifies it greatly. Also, if two events could share the same timestamp (not in this problem), we’d have to carefully define an order (the problem assures us we won’t face that ambiguity).

636. Exclusive Time of Functions - Detailed Explanation

Problem Statement:

Hints:

Approaches:

1. Brute Force Approach:

2. Optimal Stack-Based Approach:

Step-by-Step Walkthrough:

Additional Insights:

Edge Cases:

Alternative Variations:

Related Problems: