Tejav
#3586

Find COVID Recovery Patients

Medium
DatabaseHash MapArray
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n)
Space
O(1)
O(n)
💡

Intuition

Time O(n)Space O(n)

Use a single pass to track the first positive and negative tests for each patient, leveraging a hash map for efficient lookups.

⚙️

Algorithm

3 steps
  1. 1Step 1: Create a hash map to store the first positive test date for each patient.
  2. 2Step 2: Iterate through the tests to find the first negative test after the first positive for each patient.
  3. 3Step 3: Calculate recovery time and store results for patients who meet the criteria.
solution.py10 lines
1SELECT patient_id, patient_name, DATEDIFF(first_negative, first_positive) AS recovery_time
2FROM (
3  SELECT p.patient_id, p.patient_name,
4         MIN(CASE WHEN ct.result = 'Positive' THEN ct.test_date END) AS first_positive,
5         MIN(CASE WHEN ct.result = 'Negative' AND ct.test_date > MIN(CASE WHEN ct.result = 'Positive' THEN ct.test_date END) THEN ct.test_date END) AS first_negative
6  FROM patients p
7  JOIN covid_tests ct ON p.patient_id = ct.patient_id
8  GROUP BY p.patient_id, p.patient_name
9) AS recovery
10WHERE first_positive IS NOT NULL AND first_negative IS NOT NULL;
ℹ

Complexity note: This complexity is efficient because we only traverse the test results once and use a hash map for quick lookups.

  • 1Recovery requires at least one positive followed by a negative test.
  • 2Order of tests matters for determining recovery.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.