# LeetCode 574: Winning Candidate

## Problem Restatement

We are given two tables.

`Candidate`:

| Column | Type | Meaning |
|---|---|---|
| `id` | int | Candidate id |
| `name` | varchar | Candidate name |

`Vote`:

| Column | Type | Meaning |
|---|---|---|
| `id` | int | Vote id |
| `candidateId` | int | The candidate who received this vote |

We need to report the name of the candidate who received the largest number of votes.

The test cases guarantee exactly one winner. The result table can be returned in any order because there is only one winning row.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `Candidate` and `Vote` tables |
| Output | Name of the winning candidate |
| Winner | Candidate with the largest vote count |
| Tie | The problem guarantees one winner |

Expected output column:

```sql
name
```

## Example

Candidate table:

| id | name |
|---:|---|
| 1 | A |
| 2 | B |
| 3 | C |
| 4 | D |
| 5 | E |

Vote table:

| id | candidateId |
|---:|---:|
| 1 | 2 |
| 2 | 4 |
| 3 | 3 |
| 4 | 2 |
| 5 | 5 |

Vote counts:

| candidateId | Candidate | Votes |
|---:|---|---:|
| 2 | B | 2 |
| 3 | C | 1 |
| 4 | D | 1 |
| 5 | E | 1 |

Candidate `B` has the most votes.

Output:

| name |
|---|
| B |

## First Thought: Count Votes Per Candidate

Each row in `Vote` represents one vote.

So we can group votes by `candidateId`:

```sql
GROUP BY candidateId
```

Then count how many rows are in each group:

```sql
COUNT(*)
```

The candidate with the largest count is the winner.

After finding the winning `candidateId`, we join back to the `Candidate` table to get the candidate's name.

## Key Insight

The `Vote` table gives counts.

The `Candidate` table gives names.

So the query naturally has two steps:

1. Aggregate votes to find the winning `candidateId`.
2. Join that id to `Candidate` to return the name.

Because the problem guarantees one winner, we can sort by vote count descending and use:

```sql
LIMIT 1
```

## Algorithm

1. Group the `Vote` table by `candidateId`.
2. Count votes for each candidate.
3. Sort candidates by vote count descending.
4. Keep the first candidate.
5. Join that candidate id with `Candidate.id`.
6. Return `Candidate.name`.

## Correctness

Grouping the `Vote` table by `candidateId` puts all votes for the same candidate into one group.

`COUNT(*)` gives the exact number of votes received by that candidate.

Sorting the groups by `COUNT(*) DESC` places the candidate with the largest vote count first.

Since the problem guarantees exactly one winner, `LIMIT 1` selects the winning candidate id.

Joining this id to `Candidate.id` retrieves the corresponding candidate row. Selecting `name` returns exactly the winning candidate's name.

## Complexity

Let `v` be the number of rows in `Vote`, and let `c` be the number of rows in `Candidate`.

| Metric | Value | Why |
|---|---|---|
| Time | `O(v log v)` or better | The database groups and sorts vote counts |
| Space | `O(c)` | The grouping step stores one count per candidate with votes |

The exact cost depends on the database engine and indexes.

## Implementation

```sql
SELECT c.name
FROM Candidate AS c
JOIN (
    SELECT candidateId
    FROM Vote
    GROUP BY candidateId
    ORDER BY COUNT(*) DESC
    LIMIT 1
) AS winner
    ON c.id = winner.candidateId;
```

## Code Explanation

The subquery finds the winning candidate id:

```sql
SELECT candidateId
FROM Vote
GROUP BY candidateId
ORDER BY COUNT(*) DESC
LIMIT 1
```

`GROUP BY candidateId` creates one group per candidate.

`COUNT(*)` counts that candidate's votes.

`ORDER BY COUNT(*) DESC` puts the highest vote count first.

`LIMIT 1` keeps only the winner.

Then the outer query joins the winner to the candidate table:

```sql
ON c.id = winner.candidateId
```

Finally, it returns:

```sql
SELECT c.name
```

## Join-First Version

We can also join first, then group by candidate.

```sql
SELECT c.name
FROM Candidate AS c
JOIN Vote AS v
    ON c.id = v.candidateId
GROUP BY c.id, c.name
ORDER BY COUNT(*) DESC
LIMIT 1;
```

This version is shorter and also correct.

It joins each vote to its candidate, groups by candidate, sorts by vote count, and returns the top candidate.

## Testing

Create sample data:

```sql
CREATE TABLE Candidate (
    id INT PRIMARY KEY,
    name VARCHAR(255)
);

CREATE TABLE Vote (
    id INT PRIMARY KEY,
    candidateId INT
);

INSERT INTO Candidate (id, name) VALUES
(1, 'A'),
(2, 'B'),
(3, 'C'),
(4, 'D'),
(5, 'E');

INSERT INTO Vote (id, candidateId) VALUES
(1, 2),
(2, 4),
(3, 3),
(4, 2),
(5, 5);
```

Expected result:

| name |
|---|
| B |

Additional cases:

| Case | Expected behavior |
|---|---|
| One candidate has all votes | Return that candidate |
| Several candidates have votes | Return the one with highest count |
| Candidate has no votes | Does not affect the winner |
| Exactly one winning candidate | `LIMIT 1` is safe under the problem guarantee |