Average Time of Process per Machine | Leetcode 1661

1. Overview and Problem Statement

In database engineering and SQL interviews, calculating aggregated metrics across related rows within the same table is a classic pattern. LeetCode 1661: Average Time of Process per Machine tests a developer's ability to manipulate relational data using self-joins, conditional logic, aggregate functions, and rounding techniques.

The primary objective is to find the average time each machine takes to complete its processes. A process is defined by a start timestamp and an end timestamp recorded sequentially for a specific machine and process ID pair.

2. Table Schema and Data Model

The database contains a single base table named activity. The composite primary key consists of three columns: machine_id, process_id, and activity_type.

Key Business Rules

• Composite Primary Key: (machine_id, process_id, activity_type) uniquely identifies every row.
• Activity Lifecycle: Every process goes through two distinct states recorded as rows:
  • 'start': The machine initiates a process at a specific timestamp.
  • 'end': The machine completes the process at a subsequent timestamp.
• Temporal Constraint: The start timestamp is always strictly less than the end timestamp for any given (machine_id, process_id) pair.
• Required Output: Return a table containing machine_id and processing_time, where processing_time represents the average completion time per machine rounded to 3 decimal places.

3. Core Mental Model and Real-Life Analogy

Real-Life Analogy: Factory Stopwatch Tracking

Analogy: Imagine standing in a manufacturing plant holding a stopwatch for multiple assembly robots (machines). Each robot builds multiple units (processes). When robot #0 starts building Unit 1, you click Start. When it finishes Unit 1, you click Stop. You do this again for Unit 2. To find the average time robot #0 takes to build a unit, you take the duration of Unit 1, add it to the duration of Unit 2, and divide by 2.

In the database, the start and end events for the same process are stored on separate rows. Our mental model must bridge these two rows together horizontally so we can subtract start time from end time.

4. Naive vs. Better Approach

The Naive Approach (Single Table Scanning)

If we attempt to query the activity table directly without joining, we cannot easily perform row-to-row subtraction because start and end events exist as independent records across different rows. We cannot subtract row 2 from row 1 natively without maintaining state variables or writing complex window functions (like LEAD() or LAG()).

The Better Approach (Relational Self-Join)

We treat the activity table as two independent instances: a1 (representing the start activities) and a2 (representing the end activities). By joining these instances on matching machines and processes while filtering timestamps, we align start and end times onto a single logical row.

5. Step-by-Step Solution Evolution

Step 1: Designing the Self-Join Condition

To pair the correct start and end times, we join the table with itself (activity a1 inner join activity a2) using three strict matching criteria:

1. Same Machine: a1.machine_id = a2.machine_id
2. Same Process: a1.process_id = a2.process_id
3. Correct Temporal Order: a1.activity_type = 'start' AND a2.activity_type = 'end' (which is implicitly satisfied by ensuring a1.timestamp < a2.timestamp).

SELECT 
    a1.machine_id, 
    a1.timestamp AS start_time, 
    a2.timestamp AS end_time
FROM activity a1
INNER JOIN activity a2 
    ON a1.machine_id = a2.machine_id
   AND a1.process_id = a2.process_id
   AND a1.activity_type = 'start'
   AND a2.activity_type = 'end';

Step 2: Calculating Process Durations and Averages

Once aligned horizontally, calculating the duration for each individual process is a simple subtraction: a2.timestamp - a1.timestamp. To find the average duration per machine, we wrap this subtraction inside the SQL AVG() aggregate function.

SELECT 
    a1.machine_id,
    AVG(a2.timestamp - a1.timestamp) AS processing_time
FROM activity a1
INNER JOIN activity a2 
    ON a1.machine_id = a2.machine_id
   AND a1.process_id = a2.process_id
   AND a1.activity_type = 'start'
   AND a2.activity_type = 'end'
GROUP BY a1.machine_id;

Step 3: Formatting and Rounding to 3 Decimal Places

LeetCode requires the resulting processing_time to be rounded explicitly to 3 decimal places. We use the SQL ROUND(expression, decimals) function.

SELECT 
    a1.machine_id,
    ROUND(AVG(a2.timestamp - a1.timestamp), 3) AS processing_time
FROM activity a1
INNER JOIN activity a2 
    ON a1.machine_id = a2.machine_id
   AND a1.process_id = a2.process_id
   AND a1.activity_type = 'start'
   AND a2.activity_type = 'end'
GROUP BY a1.machine_id;

6. Complete Flow Walkthrough

Let's trace how the database executes our final query against an example dataset.

Execution Pipeline:

1. Inner Join Matching:
   • For machine_id = 0, process_id = 0, a1 catches 0.712 (start) and a2 catches 1.520 (end).
   • For machine_id = 0, process_id = 1, a1 catches 3.140 (start) and a2 catches 4.120 (end).
2. Subtraction Calculation:
   • Process 0 duration = 1.520 - 0.712 = 0.808
   • Process 1 duration = 4.120 - 3.140 = 0.980
3. Aggregation & Grouping (GROUP BY machine_id):
   • Machine 0 processes: (0.808 + 0.980) / 2 = 1.788 / 2 = 0.894
4. Rounding: ROUND(0.894, 3) outputs 0.894.

7. Alternative Approach: Conditional Aggregation (Case Study)

While the Self-Join approach is intuitive, senior engineers often prefer Conditional Aggregation using CASE WHEN or FILTER clauses combined with a single table scan. This avoids the overhead of joining a table with itself, which can degrade performance on tables with millions of rows.

SELECT 
    machine_id,
    ROUND(
        (SUM(CASE WHEN activity_type = 'end' THEN timestamp ELSE -timestamp END) / COUNT(DISTINCT process_id)), 
        3
    ) AS processing_time
FROM activity
GROUP BY machine_id;

Comparison of Strategies

8. Summary and Key Takeaways

• Relational Self-Joins: When related attributes live on separate rows within the same table, joining the table to itself is an effective pattern to align states horizontally.
• Composite Keys in Joins: Always join on all components of a composite key (machine_id and process_id) to prevent cross-product corruption.
• Filtering by Activity Type: Explicitly separate 'start' and 'end' rows during the join condition to ensure accurate temporal subtraction.
• Aggregation with AVG(): Combine AVG() with GROUP BY machine_id to compute metrics across multiple processes per machine.
• Precision Control: Use ROUND(val, 3) to satisfy exact output formatting requirements in reporting and interview environments.
• Alternative Optimization: Keep conditional aggregation (CASE WHEN) in your toolkit as a high-performance alternative to self-joins for massive tables.