3586. Find COVID Recovery Patients Solution

The problem

Table: patients

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| patient_id  | int     |
| patient_name| varchar |
| age         | int     |
+-------------+---------+
patient_id is the unique identifier for this table.
Each row contains information about a patient.

Table: covid_tests

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| test_id     | int     |
| patient_id  | int     |
| test_date   | date    |
| result      | varchar |
+-------------+---------+
test_id is the unique identifier for this table.
Each row represents a COVID test result. The result can be Positive, Negative, or Inconclusive.

Write a solution to find patients who have recovered from COVID - patients who tested positive but later tested negative.

A patient is considered recovered if they have at least one Positive test followed by at least one Negative test on a later date
Calculate the recovery time in days as the difference between the first positive test and the first negative test after that positive test
Only include patients who have both positive and negative test results

Return the result table ordered by recovery_time in ascending order, then by patient_name in ascending order.

The result format is in the following example.

Example:

Input:

patients table:

+------------+--------------+-----+
| patient_id | patient_name | age |
+------------+--------------+-----+
| 1          | Alice Smith  | 28  |
| 2          | Bob Johnson  | 35  |
| 3          | Carol Davis  | 42  |
| 4          | David Wilson | 31  |
| 5          | Emma Brown   | 29  |
+------------+--------------+-----+

covid_tests table:

+---------+------------+------------+--------------+
| test_id | patient_id | test_date  | result       |
+---------+------------+------------+--------------+
| 1       | 1          | 2023-01-15 | Positive     |
| 2       | 1          | 2023-01-25 | Negative     |
| 3       | 2          | 2023-02-01 | Positive     |
| 4       | 2          | 2023-02-05 | Inconclusive |
| 5       | 2          | 2023-02-12 | Negative     |
| 6       | 3          | 2023-01-20 | Negative     |
| 7       | 3          | 2023-02-10 | Positive     |
| 8       | 3          | 2023-02-20 | Negative     |
| 9       | 4          | 2023-01-10 | Positive     |
| 10      | 4          | 2023-01-18 | Positive     |
| 11      | 5          | 2023-02-15 | Negative     |
| 12      | 5          | 2023-02-20 | Negative     |
+---------+------------+------------+--------------+

Output:

+------------+--------------+-----+---------------+
| patient_id | patient_name | age | recovery_time |
+------------+--------------+-----+---------------+
| 1          | Alice Smith  | 28  | 10            |
| 3          | Carol Davis  | 42  | 10            |
| 2          | Bob Johnson  | 35  | 11            |
+------------+--------------+-----+---------------+

Explanation:

Alice Smith (patient_id = 1):
- First positive test: 2023-01-15
- First negative test after positive: 2023-01-25
- Recovery time: 25 - 15 = 10 days
Bob Johnson (patient_id = 2):
- First positive test: 2023-02-01
- Inconclusive test on 2023-02-05 (ignored for recovery calculation)
- First negative test after positive: 2023-02-12
- Recovery time: 12 - 1 = 11 days
Carol Davis (patient_id = 3):
- Had negative test on 2023-01-20 (before positive test)
- First positive test: 2023-02-10
- First negative test after positive: 2023-02-20
- Recovery time: 20 - 10 = 10 days
Patients not included:
- David Wilson (patient_id = 4): Only has positive tests, no negative test after positive
- Emma Brown (patient_id = 5): Only has negative tests, never tested positive

Output table is ordered by recovery_time in ascending order, and then by patient_name in ascending order.

Approach overview

Problem Overview: Given patients and covid_tests, return every patient who had a positive test followed later by a negative test. For each one, report the days between the first positive test and the first negative test after it. Sort by days ascending, then by name.

Approach 1: Correlated Subquery per Positive Test (O(P * T) time, O(1) extra space)

For each positive test row, run a subquery that searches covid_tests for a negative test from the same patient with a later date. Take the minimum date from that subquery as the recovery date. The logic is easy to verify because it reads like the problem statement. The cost is that the inner lookup rescans the table for every positive row, so it degrades on large logs. Use it only to validate results on small data.

Approach 2: Group Statistics + Equi-join (O(T log T) time, O(P) space)

Aggregate first. Run GROUP BY patient_id on positive tests and take MIN(test_date) to get each patient's first positive date. Then equi-join that result back to covid_tests on patient_id, keeping only negative rows where test_date is greater than the first positive date. Group again and take MIN(test_date) to get the recovery date. Join to patients for names, compute DATEDIFF, and order the result. Each table is scanned a fixed number of times, and the hash or sort-based grouping replaces the repeated lookups from Approach 1. The sort in the grouping step dominates at O(T log T), where T is the number of test rows and P is the number of patients.

Recommended for interviews: Write the correlated subquery first to show you understand the requirement. Then move to the grouped join to show you can reduce repeated work on large tables. Interviewers look for the second step because it is how you would write this in production against a real database with millions of rows. Keep the join conditions strict. Use > not >= on dates, and filter the result type with an explicit result = 'Positive' or 'Negative' check. Edge cases like same-day tests and patients with multiple positives are where most submissions fail. For more practice on this style of SQL query, work through related problems in the same topic.

Solution

Thinking

Recovery time is the day count from the first positive test to the first later negative. Take the minimum positive date per patient, then the minimum negative date after it.

Inner-join those two dates, compute the difference, join patient info, and sort by recovery time and name.

We can first find the date of the first positive test for each patient and record this in table first_positive. Next, we can find the date of the first negative test for each patient after their first positive test in the covid_tests table, and record this in table first_negative_after_positive. Finally, we join these two tables with the patients table, calculate the recovery time, and sort according to requirements.

MySQL

# Write your MySQL query statement below
WITH
    first_positive AS (
        SELECT
            patient_id,
            MIN(test_date) AS first_positive_date
        FROM covid_tests
        WHERE result = 'Positive'
        GROUP BY patient_id
    ),
    first_negative_after_positive AS (
        SELECT
            t.patient_id,
            MIN(t.test_date) AS first_negative_date
        FROM
            covid_tests t
            JOIN first_positive p
                ON t.patient_id = p.patient_id AND t.test_date > p.first_positive_date
        WHERE t.result = 'Negative'
        GROUP BY t.patient_id
    )
SELECT
    p.patient_id,
    p.patient_name,
    p.age,
    DATEDIFF(n.first_negative_date, f.first_positive_date) AS recovery_time
FROM
    first_positive f
    JOIN first_negative_after_positive n ON f.patient_id = n.patient_id
    JOIN patients p ON p.patient_id = f.patient_id
ORDER BY recovery_time ASC, patient_name ASC;

Pandas

import pandas as pd


def find_covid_recovery_patients(
    patients: pd.DataFrame, covid_tests: pd.DataFrame
) -> pd.DataFrame:
    covid_tests["test_date"] = pd.to_datetime(covid_tests["test_date"])

    pos = (
        covid_tests[covid_tests["result"] == "Positive"]
        .groupby("patient_id", as_index=False)["test_date"]
        .min()
    )
    pos.rename(columns={"test_date": "first_positive_date"}, inplace=True)

    neg = covid_tests.merge(pos, on="patient_id")
    neg = neg[
        (neg["result"] == "Negative") & (neg["test_date"] > neg["first_positive_date"])
    ]
    neg = neg.groupby("patient_id", as_index=False)["test_date"].min()
    neg.rename(columns={"test_date": "first_negative_date"}, inplace=True)

    df = pos.merge(neg, on="patient_id")
    df["recovery_time"] = (
        df["first_negative_date"] - df["first_positive_date"]
    ).dt.days

    out = df.merge(patients, on="patient_id")[
        ["patient_id", "patient_name", "age", "recovery_time"]
    ]
    return out.sort_values(by=["recovery_time", "patient_name"]).reset_index(drop=True)

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Correlated Subquery per Positive Test	O(P * T)	O(1) extra	Small datasets, quick validation
Group Statistics + Equi-join	O(T log T)	O(P)	General case, large test logs, interviews

Frequently asked questions

Is Find COVID Recovery Patients easy or hard?

Find COVID Recovery Patients is medium difficulty. The hard part is not the syntax but getting the logic right: you must pair each patient's first positive test with the first negative test after it, not any negative test. Careful date comparisons and a two-step aggregation are what separate correct answers from wrong ones.

Find COVID Recovery Patients Python/Java solution

This problem is written in SQL, so there is no Python or Java solution in the usual sense. In Pandas, you can get the same result by grouping positive tests with groupby and min, merging with negative tests on patient_id, filtering by date, and computing the day difference. The MySQL version uses GROUP BY, JOIN, and DATEDIFF.

How to solve Find COVID Recovery Patients in O(n)?

Aggregate first, then join. Use GROUP BY patient_id with MIN(test_date) filtered to positive results to get each patient's first positive date. Join that result to covid_tests on patient_id, filter for negative results after that date, and use a second GROUP BY with MIN to find the recovery date. Hash-based grouping keeps the work close to linear in the number of test rows.

What is the best approach for Find COVID Recovery Patients?

The best approach is Group Statistics + Equi-join. Aggregate the first positive date per patient with GROUP BY and MIN, join back to covid_tests for later negative results, then aggregate again to get the recovery date. This avoids repeated table scans and runs in O(T log T) time.

Is Find COVID Recovery Patients asked at Google/Amazon/Meta?

Find COVID Recovery Patients is a database problem on LeetCode with a 44.8 percent acceptance rate. It is a SQL-focused question, so it is more likely to appear in data-oriented or backend interviews than in general algorithm rounds. Company-specific frequency data is not listed on the problem tags.

What data structure is used in Find COVID Recovery Patients?

The problem relies on relational tables, not a classic data structure. The grouped solution uses intermediate result sets from GROUP BY, which the database engine typically implements with a hash table or a sort. Joins on patient_id use the same underlying indexing or hashing logic.

What is the time complexity of Find COVID Recovery Patients?

The grouped join solution runs in O(T log T) time, where T is the number of rows in covid_tests, because grouping sorts or hashes the test rows. The correlated subquery approach runs in O(P * T) time, where P is the number of positive tests, because it rescans the table for each positive row.

Find COVID Recovery Patients solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Find COVID Recovery Patients solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems