Skip to main content
Talentd

Find Cutoff Score for Each School - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase5 min read
Practice this problem

Problem Statement

Table: Schools

+-------------+------+
| Column Name | Type |
+-------------+------+
| school_id   | int  |
| capacity    | int  |
+-------------+------+
school_id is the column with unique values for this table.
This table contains information about the capacity of some schools. The capacity is the maximum number of students the school can accept.

 

Table: Exam

+---------------+------+
| Column Name   | Type |
+---------------+------+
| score         | int  |
| student_count | int  |
+---------------+------+
score is the column with unique values for this table.
Each row in this table indicates that there are student_count students that got at least score points in the exam.
The data in this table will be logically correct, meaning a row recording a higher score will have the same or smaller student_count compared to a row recording a lower score. More formally, for every two rows i and j in the table, if scorei > scorej then student_counti <= student_countj.

 

Every year, each school announces a minimum score requirement that a student needs to apply to it. The school chooses the minimum score requirement based on the exam results of all the students:

  1. They want to ensure that even if every student meeting the requirement applies, the school can accept everyone.
  2. They also want to maximize the possible number of students that can apply.
  3. They must use a score that is in the Exam table.

Write a solution to report the minimum score requirement for each school. If there are multiple score values satisfying the above conditions, choose the smallest one. If the input data is not enough to determine the score, report -1.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input:
Schools table:
+-----------+----------+
| school_id | capacity |
+-----------+----------+
| 11        | 151      |
| 5         | 48       |
| 9         | 9        |
| 10        | 99       |
+-----------+----------+
Exam table:
+-------+---------------+
| score | student_count |
+-------+---------------+
| 975   | 10            |
| 966   | 60            |
| 844   | 76            |
| 749   | 76            |
| 744   | 100           |
+-------+---------------+
Output:
+-----------+-------+
| school_id | score |
+-----------+-------+
| 5         | 975   |
| 9         | -1    |
| 10        | 749   |
| 11        | 744   |
+-----------+-------+
Explanation: 
- School 5: The school's capacity is 48. Choosing 975 as the min score requirement, the school will get at most 10 applications, which is within capacity.
- School 10: The school's capacity is 99. Choosing 844 or 749 as the min score requirement, the school will get at most 76 applications, which is within capacity. We choose the smallest of them, which is 749.
- School 11: The school's capacity is 151. Choosing 744 as the min score requirement, the school will get at most 100 applications, which is within capacity.
- School 9: The data given is not enough to determine the min score requirement. Choosing 975 as the min score, the school may get 10 requests while its capacity is 9. We do not have information about higher scores, hence we report -1.

Approach Overview

Problem Overview: Each school has a fixed admission capacity. Exam results provide scores and the number of students who achieved each score. For every school, determine the lowest score that still gets admitted when students are taken from highest score downward until the capacity is filled.

Approach 1: Correlated Subquery with Cumulative Counting (O(S * E log E) time, O(1) extra space)

Sort exam scores in descending order and progressively count how many students would be admitted if the cutoff were a particular score. For each school, use a correlated subquery that sums student_count for all rows where score >= current_score. The first score where this cumulative total reaches or exceeds the school's capacity becomes the cutoff. This approach works in pure SQL without advanced features but repeatedly recomputes aggregates, which increases cost as the number of schools or score rows grows.

Approach 2: Window Function with Running Sum (O(E log E + S * E) time, O(E) space)

Compute a running cumulative count of students using a window function. Sort the exam table by score DESC and calculate SUM(student_count) OVER (ORDER BY score DESC). This produces the number of admitted students if the cutoff were each score. Join this derived result with the Schools table and filter rows where the cumulative count is greater than or equal to the school's capacity. Taking the MIN(score) among those candidates gives the exact cutoff. If no cumulative count reaches the capacity, return -1 for that school. Window aggregation avoids repeated scans and is the cleanest solution in modern SQL.

The key insight: admission always proceeds from the highest score downward. Once the cumulative number of students meets or exceeds the capacity, that score defines the cutoff. The window function effectively simulates the admission process in a single pass over sorted scores.

This problem mainly tests reasoning about cumulative aggregates and ranking patterns commonly used in database queries. Window functions like running sums frequently appear in analytics queries and interview-style SQL problems related to window functions.

Recommended for interviews: The window function approach. It demonstrates strong SQL fundamentals, avoids repeated aggregation, and clearly models the admission process with a single ordered pass. The correlated subquery version proves correctness but is less efficient and harder to scale.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Correlated Subquery with Cumulative CountO(S * E log E)O(1)When window functions are unavailable or when working with smaller datasets
Window Function Running SumO(E log E + S * E)O(E)Preferred modern SQL approach for cumulative calculations and analytics queries

Video Solution

LeetCode Medium 1988 "Find Cutoff Score for Each School" Interview SQL Question with Explanation • Everyday Data Science • 1,975 views views

Frequently Asked Questions

Is Find Cutoff Score for Each School easy or hard?
LeetCode classifies it as Medium difficulty. The challenge is not the logic itself but expressing cumulative admission logic correctly in SQL using window functions and joins.
Find Cutoff Score for Each School Python/Java solution
This problem is primarily designed for SQL. If implemented in Python or Java, the logic would sort scores in descending order and maintain a running prefix sum of student counts. For each school capacity, locate the first score where the cumulative count reaches the capacity and return that score as the cutoff.
How to solve Find Cutoff Score for Each School in O(n)?
Pure O(n) processing is difficult because SQL engines typically sort scores to compute ordered cumulative sums. The closest practical approach uses SUM(student_count) OVER (ORDER BY score DESC), which performs a single ordered pass after sorting. This efficiently determines the first score where the cumulative admitted students reach the school's capacity.
What is the best approach for Find Cutoff Score for Each School?
The most efficient approach uses a SQL window function to compute a running cumulative sum of students ordered by score descending. After calculating SUM(student_count) OVER (ORDER BY score DESC), join this result with the Schools table and pick the minimum score where the cumulative count meets or exceeds the school's capacity. This models the admission process directly and avoids repeated aggregation.
Is Find Cutoff Score for Each School asked at Google/Amazon/Meta?
Database-style SQL questions involving cumulative sums, ranking, and window functions appear frequently in data engineering and analytics interviews at companies like Amazon, Google, and Meta. Problems like this test understanding of ordered aggregations and how to translate real-world constraints into SQL queries.
What data structure is used in Find Cutoff Score for Each School?
The problem relies on relational database tables and ordered aggregation rather than traditional data structures. The key mechanism is a cumulative sum computed with SQL window functions, which internally operates over a sorted dataset of exam scores.
What is the time complexity of Find Cutoff Score for Each School?
The dominant cost comes from sorting exam scores before computing the window function, which is O(E log E) where E is the number of score rows. After that, joining with schools and filtering rows adds roughly O(S * E) processing depending on the query plan.

Ready to solve this problem?

Practice Find Cutoff Score for Each School with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary