Leetcode discuss: 1122. Relative Sort Array

Aug. 26, 2021

Here is the link. 

C# | Counting sort and O(1) lookup using HashMap | 2021 Aug 26

Aug. 26, 2021
Introduction
I chose to practice Leetcode premium Amazon code assessment, so I came cross this algorithm.

C# | List.Sort() API | HashSet | Counting sort using int[] | O(NlogN) time complexity

I tried to put together a few data structure to solve the problem, in other words, put arr2 into a hashset, build a O(1) lookup map to find index by value in arr2, and record count of value in arr2 by counting the occurrence in the array arr1.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ArraySort
{
    class Program
    {
        static void Main(string[] args)
        {
            var arr1 = new int[] { 2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19 };
            var arr2 = new int[] { 2, 1, 4, 3, 9, 6 };

            var result = RelativeSortArray(arr1, arr2);
        }

        public static int[] RelativeSortArray(int[] arr1, int[] arr2)
        {
            var length1 = arr1.Length;
            var length2 = arr2.Length;

            var mapCount = new int[length2];
            var set = new HashSet<int>(arr2);
            var indexMap = new Dictionary<int, int>();

            for (int i = 0; i < length2; i++)
            {
                indexMap.Add(arr2[i], i);
            }

            var notIn2 = new List<int>();
            foreach (var item in arr1)
            {
                if (set.Contains(item))
                {
                    var pos = indexMap[item];
                    mapCount[pos]++;
                }
                else
                {
                    notIn2.Add(item);
                }
            }

            notIn2.Sort();

            var list = new List<int>();
            for (int i = 0; i < length2; i++)
            {
                var current = arr2[i];
                for (int j = 0; j < mapCount[i]; j++)
                {
                    list.Add(current);
                }
            }

            foreach (var item in notIn2)
            {
                list.Add(item);
            }

            return list.ToArray();
        }
    }
}