1122. Relative Sort Array #

Problem #

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that don’t appear in arr2 should be placed at the end of arr1 in ascending order.

Example 1:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
Output: [2,2,2,1,4,3,3,9,6,7,19]

Constraints:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• Each arr2[i] is distinct.
• Each arr2[i] is in arr1.

Summary #

Given two arrays, arr1 and arr2,

• the elements in arr2 are all distinct
• every element in arr2 appears in arr1

Sort the elements in arr1 so that the relative order of items in arr1 is the same as the relative order in arr2. Elements that do not appear in arr2 need to be placed at the end of arr1 in ascending order.

Notes:

• arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• The elements arr2[i] in arr2 are all distinct
• Every element arr2[i] in arr2 appears in arr1

Solution Ideas #

• Given 2 arrays A and B, A contains all elements in B. The requirement is to sort A according to the element order in B, and elements not in B are then placed after them in ascending order.
• There are multiple solutions to this problem. One brute-force solution is to follow the problem statement: first count the frequencies of all elements in A and store them in a map, then output according to the order of B, and finally sort the remaining elements and append them at the end. Another approach uses the idea of bucket sort. Since the problem limits the size of A to 1000, this scale is very small, so 1001 buckets can be used to store all numbers. Once the numbers are placed into buckets, they are already sorted by default. The subsequent approach is similar to the brute-force solution above: output according to frequencies. Elements outside B can simply be output in bucket order.

Code #

package leetcode

import "sort"

// Solution 1: Bucket sort, time complexity O(n^2)
func relativeSortArray(A, B []int) []int {
	count := [1001]int{}
	for _, a := range A {
		count[a]++
	}
	res := make([]int, 0, len(A))
	for _, b := range B {
		for count[b] > 0 {
			res = append(res, b)
			count[b]--
		}
	}
	for i := 0; i < 1001; i++ {
		for count[i] > 0 {
			res = append(res, i)
			count[i]--
		}
	}
	return res
}

// Solution 2: Simulation, time complexity O(n^2)
func relativeSortArray1(arr1 []int, arr2 []int) []int {
	leftover, m, res := []int{}, make(map[int]int), []int{}
	for _, v := range arr1 {
		m[v]++
	}
	for _, s := range arr2 {
		count := m[s]
		for i := 0; i < count; i++ {
			res = append(res, s)
		}
		m[s] = 0
	}
	for v, count := range m {
		for i := 0; i < count; i++ {
			leftover = append(leftover, v)
		}
	}
	sort.Ints(leftover)
	res = append(res, leftover...)
	return res
}