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.

Description Solution Video 14:16

3586. Find COVID Recovery Patients

Medium44.8% acceptance

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.

Topics

Database

14:16

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Write your MySQL query statement below

Starter codeMySQLSpaces: 4

Examples

Case 1

Input

{"headers":{"patients":["patient_id","patient_name","age"],"covid_tests":["test_id","patient_id","test_date","result"]},"rows":{"patients":[[1,"Alice Smith",28],[2,"Bob Johnson",35],[3,"Carol Davis",42],[4,"David Wilson",31],[5,"Emma Brown",29]],"covid_tests":[[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"]]}}

Your code is saved on this device.Solution