ROC AUC From Scratch in Python, With Ties

Given real scores and binary labels (1 positive, 0 negative), return the ROC AUC: the probability that a randomly chosen positive has a higher score than a randomly chosen negative, with ties counting one half. There is at least one positive and one negative. Aim for O(n log n).

Examples

Input scores = [0.9, 0.8, 0.3, 0.1], labels = [1, 1, 0, 0]

Output 1

Every positive outranks every negative: 1.0.

Input scores = [0.5, 0.5, 0.5, 0.5], labels = [1, 0, 1, 0]

Output 0.5

All scores tied: every pair counts one half, 0.5.

Input scores = [0.1, 0.4, 0.35, 0.8], labels = [0, 0, 1, 1]

Output 0.75

Three of the four positive–negative pairs are ordered correctly: 0.75.

Constraints

2 ≤ n ≤ 10⁵
At least one of each label
Checked to a relative tolerance of 10⁻⁹

Hints

Hint 1

AUC = P(score⁺ > score⁻) + ½P(score⁺ = score⁻) over all positive–negative pairs. That is the Mann–Whitney U statistic over n₊n₋.

Hint 2

Rank all scores together. Give a block of equal scores the average of the ranks it spans.

Hint 3

AUC = (sum of positive ranks − n₊(n₊ + 1)/2) / (n₊n₋), with ranks starting at 1.

Where candidates go wrong

Ranking with argsort(argsort(scores)), which gives tied scores different ranks depending on input order.
Integrating the ROC curve with the trapezium rule but stepping through tied scores one at a time, which turns a diagonal segment into a staircase.
Ranks starting at 0 in the formula that assumes 1.

The idea

Sort the scores once. Walk through the sorted order in blocks of equal scores; every member of a block spanning sorted positions i to j (0-based) gets rank (i + j)/2 + 1. The sum of the positives' ranks counts, for each positive, how many scores are at or below it, with ties shared. Subtracting n₊(n₊ + 1)/2 removes the positive–positive comparisons, leaving exactly the number of positive–negative pairs a positive wins, plus half the ties. Dividing by n₊n₋ turns the count into a probability.

Time O(n log n) · Space O(n)

Reference solution

import numpy as np

def roc_auc(scores, labels):
    s = np.asarray(scores, dtype=float)
    pos = np.asarray(labels) == 1
    order = np.argsort(s, kind='mergesort')
    srt = s[order]
    ranks = np.empty(len(s))
    i = 0
    while i < len(s):                            # one block of tied scores at a time
        j = i
        while j + 1 < len(s) and srt[j + 1] == srt[i]:
            j += 1
        ranks[order[i:j + 1]] = (i + j) / 2 + 1  # the average of ranks i+1 .. j+1
        i = j + 1
    n_pos, n_neg = pos.sum(), (~pos).sum()
    # Mann-Whitney: positive rank sum, minus its minimum possible value
    return float((ranks[pos].sum() - n_pos * (n_pos + 1) / 2) / (n_pos * n_neg))

Console⌘/Ctrl + Enter runs

Python runs in your browser with NumPy. The first run downloads the runtime, which takes a few seconds.

Why interviewers ask it

AUC is the default metric for binary classifiers, and in credit and fraud it is the metric a model is signed off on. Interviewers ask candidates to compute it without sklearn to see whether they know what it means. The probabilistic definition gets you to an O(n log n) answer; drawing the curve gets you to an O(n²) one.

The theory behind it is in the lesson Statistics coding questions: variance, AUC and rank correlation.

Keep going

Easy12 min

ROC AUC from scores, with ties