One-Nearest-Neighbor Classification with Manhattan Distance

You are given a nonempty set of labeled training samples and a set of query samples. Each sample is an integer feature vector.
For every query, find the single training sample with the smallest Manhattan distance:
distance(a, b) = sum(abs(a[i] - b[i]))
If several training samples have the same minimum distance, choose the one that appears earliest in trainingFeatures.
Return the chosen training label for every query, in query order.

Function
classifyOneNearestNeighborManhattan(trainingFeatures: int[][], trainingLabels: int[], queries: int[][]) → int[]

Examples
Example 1
trainingFeatures = [[0,0],[3,0],[2,3]]
trainingLabels = [10,20,30]
queries = [[2,1],[2,3]]
return = [20,30]
The first query is two units from both the first and second rows, so the earlier of those tied nearest rows supplies label 20 only after checking all distances: its distances are 3, 2, and 2, making the second row the earliest minimum. The second query exactly matches the third row.
Example 2
trainingFeatures = [[-2,1],[2,1]]
trainingLabels = [7,9]
queries = [[0,1],[3,2]]
return = [7,9]
The first query ties at Manhattan distance two and selects the earlier row; the second is closest to [2,1].

Constraints
1 <= trainingFeatures.length == trainingLabels.length <= 2000.
1 <= queries.length <= 2000.
1 <= trainingFeatures[i].length == queries[j].length <= 100.
-10^4 <= trainingFeatures[i][k], queries[j][k] <= 10^4.
Every Manhattan-distance sum fits in a signed 64-bit integer.

The trick is that there is no trick. Constraints cap training and queries at 2000 each with up to 100 dimensions, so the nested loop is about 400 million simple operations at worst. Brute force is the intended answer. For each query, scan training rows in order, compute the sum of absolute differences, and update the best only when the new distance is strictly less than the current best. Strict less-than is the whole tie-break. Use <= and you pick the latest tie instead of the earliest. Initialize best distance to a huge value or to the first row's distance, not zero. You can also break early inside the distance sum once it exceeds the current best, which saves real time. Use 64-bit integers if your language needs it. If you freeze on the live OA, StealthCoder can hand you the loop structure, but the logic is short enough to own yourself.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.