09 Sept 2026•Go / Python / TypeScript•Easy

Relative Sort Array

Sort one array by another array's value order, then append remaining values ascending.

View original LeetCode question

Count the first array, emit requested values in the second array's order, sort leftover keys, and emit their counts.

complexity

O(n + u log u) time and O(u) space for u distinct values.

solution files

  • Go relative-sort-array/solution.go
  • Python relative-sort-array/solution.py
  • TypeScript relative-sort-array/solution.ts

Solution files

Go•relative-sort-array/solution.go
package main

import "sort"

func relativeSortArray(arr1 []int, arr2 []int) []int {
	count := map[int]int{}
	for _, value := range arr1 {
		count[value]++
	}
	result := make([]int, 0, len(arr1))
	emit := func(value int) {
		for used := 0; used < count[value]; used++ {
			result = append(result, value)
		}
		delete(count, value)
	}
	for _, value := range arr2 {
		emit(value)
	}
	remaining := []int{}
	for value := range count {
		remaining = append(remaining, value)
	}
	sort.Ints(remaining)
	for _, value := range remaining {
		emit(value)
	}
	return result
}
Python•relative-sort-array/solution.py
from collections import Counter


class Solution:
    def relativeSortArray(self, arr1: list[int], arr2: list[int]) -> list[int]:
        count = Counter(arr1); result: list[int] = []
        for value in arr2: result.extend([value] * count.pop(value))
        for value in sorted(count): result.extend([value] * count[value])
        return result
TypeScript•relative-sort-array/solution.ts
function relativeSortArray(arr1: number[], arr2: number[]): number[] {
  const count = new Map<number, number>(); for (const value of arr1) count.set(value, (count.get(value) ?? class="syntax-number">0) + class="syntax-number">1);
  const result: number[] = []; const emit = (value: number): void => { for (let used = class="syntax-number">0; used < (count.get(value) ?? class="syntax-number">0); used += class="syntax-number">1) result.push(value); count.delete(value); };
  for (const value of arr2) emit(value); for (const value of [...count.keys()].sort((a, b) => a - b)) emit(value); return result;
}