Identifying the quickselect pattern

There are many problems where we need to find the top or bottom k elements in a dataset based on some complex scoring criteria. These are generally medium or hard problems where we need to define a scoring function to rank elements in a dataset. The scoring function may be stateless (the score of an element depends only on the element itself, like abs(x - target)) or stateful (the score depends on auxiliary data computed from the whole dataset, like a character's frequency in the input string), depending on the complexity of the problem, and the goal is to find the elements with the top k or the bottom k scores.

If the problem statement or its solution follows the generic template below, it can be solved using the generic quickselect algorithm.

Template:
Given an array of data elements, find the elements with the top k or bottom k scores, where a function f computes the score of every element.

Example

Let's consider the following problem as an example to better understand how to identify and solve a problem using the generic quickselect algorithm.

Problem statement: Given an integer array `arr`, an integer `k` and a `target`, find the `k` closest elements to the `target`.

An integer `x` is closer to `target` than `y` if:

`|x - target| < |y - target|`, OR

`|x - target| == |y - target|` AND `x < y`