Solve 4 LeetCode algorithm problems

Question

LeetCode 636. Exclusive Time of Functions LeetCode 253. Meeting Rooms II LeetCode 314. Binary Tree Vertical Order Traversal LeetCode 215. Kth Largest Element in an Array

https://leetcode.com/problems/exclusive-time-of-functions/description/ https://leetcode.com/problems/meeting-rooms-ii/description/ https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/ https://leetcode.com/problems/kth-largest-element-in-an-array/description/

Exclusive Time of Functions Logs

Given n functions labeled 0..n-1 and a list of log entries describing start and end times of function calls on a single-threaded CPU, compute the exclusive execution time for each function. Each log entry is a string "function_id:type:timestamp", where type is "start" or "end". A "start" entry at time t means the function begins at the start of time t. An "end" entry at time t means the function ends at the end of time t (inclusive). Logs are in chronological order and properly nested (well-formed). Return an array ans of length n where ans[i] is the total time spent executing function i excluding time spent in functions it calls (including recursive calls).

Constraints

• 1 <= n <= 10^4
• 1 <= len(logs) <= 10^5
• 0 <= function_id < n
• 0 <= timestamp <= 10^9
• logs are in chronological order
• each start has a corresponding end; calls are properly nested
• single-threaded execution; at most one function runs at any time

Examples

Example 1

Input: n = 2, logs = ["0:start:0","1:start:2","1:end:5","0:end:6"]
Output: [3, 4]

Explanation: Function 0 runs at times [0,1] (2 units) and [6,6] (1 unit) for total 3. Function 1 runs from [2,5] (4 units).

Example 2

Input: n = 1, logs = ["0:start:0","0:end:0"]
Output: [1]

Explanation: Single function runs for one unit at time 0.

Hints

1. Use a stack to track the active function ids.
2. Keep a variable prev to mark the start of the current uninterrupted interval.
3. On a start at time t, add t - prev to the current top function before pushing the new one, then set prev = t.
4. On an end at time t, pop and add t - prev + 1 to that function, then set prev = t + 1.

Approach

Maintain a stack of active function ids and a pointer prev to the start of the currently running time segment. When a new function starts at time t, the function on top of the stack was running exclusively from prev to t-1, so attribute t - prev to it, then push the new function and set prev to t. When the current function ends at time t, attribute t - prev + 1 to it (end is inclusive), pop it, and set prev to t + 1 to mark the next free time unit. This correctly accumulates exclusive times while respecting nested calls and recursion.

• Time complexity: O(len(logs))
• Space complexity: O(n + depth_of_call_stack)