Frontend School

Maximum Average Patient Cohort Score

DSA
medium

Maximum Average Patient Cohort Score

Medium
Sliding Window
Hash Map
Arrays

Overview

At Innovaccer, we frequently analyze patient data to identify cohorts with specific characteristics, often aiming to optimize care pathways or identify high-performing groups. One common challenge is to find a group of patients (a 'cohort') that not only meets a minimum size requirement but also exhibits a diverse set of medical conditions, ensuring the cohort is representative or medically interesting. Simultaneously, we want to find the cohort with the best health outcomes, represented by an average score.

This problem asks you to identify a contiguous group of patients in a given dataset that satisfies both a minimum size and a minimum diversity of diagnoses, and among all such valid groups, determine the one with the highest average patient score.

What you need to do / Task

Implement the function maxAverageScore that takes four parameters:

  1. patientScores: An array of numbers representing the health outcome scores for a sequence of patients.
  2. diagnosisIds: An array of numbers, where diagnosisIds[i] is the unique ID for the primary diagnosis of patientScores[i].
  3. minPatients: An integer specifying the minimum number of patients required in a valid cohort.
  4. minDistinctDiagnoses: An integer specifying the minimum number of unique diagnosis IDs required within a valid cohort.

The function should return the maximum average score found among all contiguous patient cohorts that satisfy both minPatients and minDistinctDiagnoses criteria. If no such cohort exists, return -1.

Input & output

Input:

  • patientScores: number[] - An array of non-negative integers representing patient health scores. patientScores[i] is the score for the i-th patient.
  • diagnosisIds: number[] - An array of positive integers representing diagnosis IDs. diagnosisIds[i] is the diagnosis ID for the i-th patient, corresponding to patientScores[i].
  • minPatients: number - A positive integer representing the minimum required length of a patient cohort.
  • minDistinctDiagnoses: number - A positive integer representing the minimum required count of distinct diagnosis IDs within a patient cohort.

Output:

  • number - The maximum average score (a floating-point number) among all valid cohorts. Return -1 if no valid cohort is found.

Clarifications

  • The length of patientScores and diagnosisIds will always be equal.
  • A 'contiguous group' means a subarray of patients. The order of patients matters.
  • The average score should be calculated as sum_of_scores / number_of_patients_in_cohort.
  • If multiple cohorts yield the same maximum average, any one of them is valid, but you only need to return the numerical average.
  • The return value should be a floating-point number, so precision might be a consideration. Standard floating-point arithmetic is acceptable.
  • All patientScores are non-negative. All diagnosisIds are positive integers.

Examples

1

Example 1

Input:

patientScores = [10, 20, 30, 40, 50], diagnosisIds = [1, 2, 1, 3, 2], minPatients = 3, minDistinctDiagnoses = 2

Output:

40

Note:

Let's analyze cohorts:

  • [10, 20, 30] (IDs: 1, 2, 1): Length 3 (>=3), Distinct IDs: {1, 2} (count 2 >=2). Average = (10+20+30)/3 = 20.
  • [20, 30, 40] (IDs: 2, 1, 3): Length 3 (>=3), Distinct IDs: {1, 2, 3} (count 3 >=2). Average = (20+30+40)/3 = 30.
  • [30, 40, 50] (IDs: 1, 3, 2): Length 3 (>=3), Distinct IDs: {1, 2, 3} (count 3 >=2). Average = (30+40+50)/3 = 40.
  • [20, 30, 40, 50] (IDs: 2, 1, 3, 2): Length 4 (>=3), Distinct IDs: {1, 2, 3} (count 3 >=2). Average = (20+30+40+50)/4 = 35.
  • [10, 20, 30, 40, 50] (IDs: 1, 2, 1, 3, 2): Length 5 (>=3), Distinct IDs: {1, 2, 3} (count 3 >=2). Average = (10+20+30+40+50)/5 = 30. The maximum average among valid cohorts is 40.
2

Example 2

Input:

patientScores = [5, 10, 15, 20], diagnosisIds = [100, 100, 200, 100], minPatients = 2, minDistinctDiagnoses = 2

Output:

17.5

Note:

Let's analyze cohorts:

  • [5, 10] (IDs: 100, 100): Length 2 (>=2), Distinct IDs: {100} (count 1 < 2). Invalid.
  • [10, 15] (IDs: 100, 200): Length 2 (>=2), Distinct IDs: {100, 200} (count 2 >=2). Average = (10+15)/2 = 12.5.
  • [15, 20] (IDs: 200, 100): Length 2 (>=2), Distinct IDs: {100, 200} (count 2 >=2). Average = (15+20)/2 = 17.5.
  • [5, 10, 15] (IDs: 100, 100, 200): Length 3 (>=2), Distinct IDs: {100, 200} (count 2 >=2). Average = (5+10+15)/3 = 10.
  • [10, 15, 20] (IDs: 100, 200, 100): Length 3 (>=2), Distinct IDs: {100, 200} (count 2 >=2). Average = (10+15+20)/3 = 15.
  • [5, 10, 15, 20] (IDs: 100, 100, 200, 100): Length 4 (>=2), Distinct IDs: {100, 200} (count 2 >=2). Average = (5+10+15+20)/4 = 12.5. The maximum average among valid cohorts is 17.5.
3

Example 3

Input:

patientScores = [1, 2, 3], diagnosisIds = [10, 10, 10], minPatients = 1, minDistinctDiagnoses = 2

Output:

-1

Note:

No contiguous cohort in this dataset can have 2 or more distinct diagnosis IDs, as all patients share the same diagnosis ID (10). Therefore, no valid cohort exists, and the function should return -1.

Constraints

Constraints & assumptions

  • 1 <= patientScores.length <= 10^5
  • patientScores.length == diagnosisIds.length
  • 0 <= patientScores[i] <= 1000
  • 1 <= diagnosisIds[i] <= 10^9
  • 1 <= minPatients <= patientScores.length
  • 1 <= minDistinctDiagnoses <= patientScores.length

Out of scope

  • Handling non-integer or negative minPatients or minDistinctDiagnoses values (assume valid positive integers).
  • Optimization for extremely large ranges of diagnosisIds if the number of distinct IDs is also very large (standard hash map performance is expected).

What interviewers evaluate

  • Algorithmic Correctness: The solution correctly identifies the maximum average score under all specified conditions and edge cases.
  • Time Complexity: The solution should achieve optimal or near-optimal time complexity, typically O(N).
  • Space Complexity: The solution should use space efficiently, typically O(D) where D is the number of distinct diagnosis IDs, or O(N) in the worst case.
  • Code Structure & Readability: The code is well-organized, clean, and easy to understand, reflecting good software engineering practices.
  • Edge Case Handling: The solution correctly handles scenarios like no valid cohort found, or when minPatients or minDistinctDiagnoses are at their limits.

Loading editor...