Given an array of integers, sort the array according to frequency of elements. That is elements that have higher frequency come first. If frequencies of two elements are same, then smaller number comes first.
Example 1:
Input:
N = 5
A[] = {5,5,4,6,4}
Output: 4 4 5 5 6
Explanation: The highest frequency here is
2. Both 5 and 4 have that frequency. Now
since the frequencies are same then 
smallerelement comes first. So 4 4 comes 
firstthen comes 5 5. Finally comes 6.
The output is 4 4 5 5 6.
Example 2:
Input:
N = 5
A[] = {9,9,9,2,5}
Output: 9 9 9 2 5
Explanation: The highest frequency here is
3. The element 9 has the highest frequency
So 9 9 9 comes first. Now both 2 and 5
have same frequency. So we print smaller
element first.
The output is 9 9 9 2 5.
Your Task:
You only need to complete the function sortByFreq that takes arr, and n as parameters and returns the sorted array.
Expected Time Complexity: O(NLogN).
Expected Auxiliary Space: O(N). 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A_{i} ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3

 

class Solution:

   

    #Function to sort the array according to frequency of elements.

    def sortByFreq(self,a,n):

        #code here



Solutions:
import heapq

class Solution:

	def sortByFreq(self, a, n):
		freq_map = {}
		for num in a:
			freq_map[num] = freq_map.get(num, 0) + 1
		min_heap = []
		for (val, freq) in freq_map.items():
			heapq.heappush(min_heap, (-freq, val))
		min_heap.sort(key=lambda x: (x[0], x[1]))
		ans = [val for (freq, val) in min_heap for i in range(-freq)]
		return ans


import heapq

class Solution:

	def sortByFreq(self, a, n):
		freq_map = {}
		for num in a:
			freq_map[num] = freq_map.get(num, 0) + 1
		min_heap = []
		for (val, freq) in freq_map.items():
			heapq.heappush(min_heap, (-freq, val))
		ans = []
		while min_heap:
			(freq, val) = heapq.heappop(min_heap)
			ans += [val] * -freq
		return ans


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		cnt = Counter(a)
		a.sort(key=lambda x: (-cnt[x], x))
		return a


class Solution:

	def sortByFreq(self, a, n):
		d = dict()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		a.sort(key=lambda x: (-d[x], x))
		return a


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		return sorted(a, key=lambda x: (-d[x], x))


from collections import defaultdict

class Solution:

	def sortByFreq(self, arr, n):
		d = defaultdict(lambda : 0)
		for i in range(n):
			d[arr[i]] += 1
		arr.sort(key=lambda x: (-d[x], x), reverse=False)
		return arr


class Solution:

	def sortByFreq(self, a, n):
		f = {}
		for i in a:
			if i in f:
				f[i] += 1
			else:
				f[i] = 1
		s = sorted(f.items(), key=lambda x: (-x[1], x[0]))
		x = []
		for i in s:
			x.extend([i[0]] * i[1])
		return x


class Solution:

	def sortByFreq(self, a, n):
		import collections

		def sortBasedOnFrequencyAndValue(lst):
			m = {}
			for i in range(n):
				m[lst[i]] = m.get(lst[i], 0) + 1
			lst.sort(key=lambda x: (-m[x], x))
			return lst
		return sortBasedOnFrequencyAndValue(a)


from collections import *

class Solution:

	def sortByFreq(self, a, n):
		freq_dict = defaultdict(int)
		for i in a:
			freq_dict[i] += 1
		max_freq = max(freq_dict.values())
		buckets = [[] for _ in range(max_freq + 1)]
		for (k, v) in freq_dict.items():
			buckets[v].append(k)
		result = []
		for i in range(max_freq, 0, -1):
			if buckets[i]:
				result.extend([str(x) for x in sorted(buckets[i]) for _ in range(i)])
		return result


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		count = Counter(a)
		return sorted(a, key=lambda x: (count[x], -x), reverse=True)


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		di = Counter(a)
		di = sorted(di.items(), key=lambda item: (-item[1], item[0]))
		li = []
		for i in di:
			li.extend([i[0]] * i[1])
		return li


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		d = dict()
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		a.sort(key=lambda x: (-d[x], x))
		return a


class Solution:

	def sortByFreq(self, a, n):
		dic = {}
		for elem in a:
			dic[elem] = dic.get(elem, 0) + 1
		sorteddic = sorted(dic.items(), key=lambda x: (x[1], -x[0]), reverse=True)
		ansAr = []
		for (k, v) in sorteddic:
			ansAr.extend([k] * v)
		return ansAr


class Solution:

	def sortByFreq(self, a, n):
		d = {x: 0 for x in a}
		for i in a:
			d[i] += 1
		a.sort(key=lambda x: (-d[x], x))
		return a


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		fre = Counter(a)
		return sorted(a, key=lambda x: (-fre[x], x))


class Solution:

	def sortByFreq(self, a, n):
		a.sort()
		cnt = {}
		for i in range(n):
			if a[i] in cnt:
				cnt[a[i]] += 1
			else:
				cnt[a[i]] = 1

		def givefreq(c):
			return cnt[c]
		a.sort(key=givefreq, reverse=True)
		return a


class Solution:

	def sortByFreq(self, a, n):
		from collections import Counter
		p = Counter(a)
		p = sorted(p.items(), key=lambda x: (-x[1], x[0]))
		l = []
		for i in p:
			l += [i[0]] * i[1]
		return l


class Solution:

	def sortByFreq(self, a, n):
		hmap = {}
		for val in a:
			hmap[val] = hmap.get(val, 0) + 1
		temp = [(hmap[key], key) for key in hmap]
		temp.sort(key=lambda x: (-x[0], x[1]))
		i = 0
		for tup in temp:
			(freq, val) = tup
			for j in range(freq):
				a[i] = val
				i += 1
		return a


class Solution:

	def sortByFreq(self, a, n):
		dic = {}
		a.sort()
		for each in a:
			if each in dic:
				dic[each] += 1
			else:
				dic[each] = 1
		res = []
		for each in a:
			res.append([each, dic[each]])
		res.sort(key=lambda x: x[1], reverse=True)
		res1 = []
		for each in res:
			res1.append(each[0])
		return res1


from collections import Counter, defaultdict
import heapq

class Solution:

	def sortByFreq(self, a, n):
		d = defaultdict()
		for num in a:
			d[num] = d.get(num, 0) + 1
		li = list(d.items())
		li.sort(key=lambda a: [-a[1], a[0]])
		ans = []
		for (k, v) in li:
			for i in range(v):
				ans.append(k)
		return ans


class Solution:

	def sortByFreq(self, a, n):
		ans = []
		dic = dict()
		for i in a:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		lst = list(dic.items())
		lst.sort(key=lambda a: (-a[1], a[0]))
		for (k, v) in lst:
			for i in range(v):
				ans.append(k)
		return ans


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		d_ = {}
		ans = []
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		for i in d.keys():
			if d[i] not in d_.keys():
				d_[d[i]] = [i]
			else:
				d_[d[i]].append(i)
		for i in sorted(d_, reverse=True):
			d_[i].sort()
			for j in range(len(d_[i])):
				for k in range(i):
					ans.append(d_[i][j])
		return ans


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		res = sorted(a, key=lambda x: (d[x], -x), reverse=True)
		return res


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		k = sorted(d.items(), key=lambda x: x[1], reverse=True)
		i = 0
		(temp, res) = ([], [])
		while i < len(k):
			while i + 1 < len(k) and k[i][1] == k[i + 1][1]:
				temp += [k[i][0]] * k[i][1]
				i += 1
			temp += [k[i][0]] * k[i][1]
			temp.sort()
			res += temp
			temp = []
			i += 1
		return res


class Solution:

	def sortByFreq(self, a, n):
		r = []
		d = {}
		for b in a:
			if b in d:
				d[b] = d[b] + 1
			else:
				d[b] = 1
		for b in d:
			r.append((b, d[b]))
		r.sort(key=lambda x: (-x[1], x[0]))
		res = []
		for x in r:
			freq = x[1]
			for i in range(freq):
				res.append(x[0])
		return res


class Solution:

	def sortByFreq(self, a, n):
		freq = [0 for i in range(max(a) + 1)]
		hash_for_freq = [[] for i in range(n + 1)]
		for num in a:
			freq[num] += 1
		for i in range(max(a) + 1):
			if freq[i]:
				hash_for_freq[freq[i]].append(i)
		l = []
		for i in range(n, 0, -1):
			for num in hash_for_freq[i]:
				for j in range(i):
					l.append(num)
		return l


import heapq

class Solution:

	def sortByFreq(self, a, n):
		freq_map = {}
		for x in a:
			if freq_map.get(x):
				freq_map[x] += 1
			else:
				freq_map[x] = 1
		max_heap = []
		for (x, freq) in freq_map.items():
			pair = (freq * -1, x)
			heapq.heappush(max_heap, pair)
		max_heap.sort(key=lambda x: (x[0], x[1]))
		ans = [x for (freq, x) in max_heap for i in range(freq * -1)]
		return ans


class Solution:

	def sortByFreq(self, a, n):
		mapp = {}
		arr1 = list(set(a))
		n = len(list(set(a)))
		for i in a:
			if i in mapp:
				mapp[i] += 1
			else:
				mapp[i] = 1
		a.sort(key=lambda x: (-mapp[x], x), reverse=True)
		return a[::-1]


from collections import Counter

class Solution:

	def sortByFreq(self, arr, n):
		count = Counter(arr)
		sorted_arr = sorted(arr, key=lambda x: (-count[x], x))
		return sorted_arr


class Solution:

	def sortByFreq(self, a, n):
		f = {}
		for i in a:
			if i in f:
				f[i] += 1
			else:
				f[i] = 1
		a = sorted(a)
		a = sorted(a, key=lambda x: f[x], reverse=True)
		return a


import heapq

class Solution:

	def sortByFreq(self, a, n):
		dict1 = {}
		ans = []
		for i in a:
			if i not in dict1:
				dict1[i] = 1
			else:
				dict1[i] += 1
		keys = list(dict1.keys())
		values = list(dict1.values())
		max_heap = []
		heapq.heapify(max_heap)
		for i in range(len(keys)):
			heapq.heappush(max_heap, (-1 * values[i], keys[i]))
		while max_heap:
			f = -1 * max_heap[0][0]
			e = max_heap[0][1]
			for i in range(0, f):
				ans.append(e)
			heapq.heappop(max_heap)
		return ans


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in range(len(a)):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		a.sort(key=lambda x: (d[x], -x), reverse=True)
		return a


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		x = sorted(d.items())
		y = sorted(x, key=lambda x: x[1], reverse=True)
		res = []
		for (k, v) in y:
			j = v * [k]
			res.extend(j)
		return res


class Solution:

	def sortByFreq(self, a, n):
		A = {}
		l = []
		ans = []
		for i in a:
			if i in A:
				A[i] += 1
			else:
				A[i] = 1
		for i in A:
			l.append((A[i], i))
		l.sort(key=lambda x: (-x[0], x[1]))
		for i in l:
			ans += [i[1]] * i[0]
		return ans


import collections as c

class Solution:

	def sortByFreq(self, a, n):
		k = c.Counter(a)
		l = []
		for i in k:
			l.append([k[i], i])
		l.sort(key=lambda x: (-x[0], x[1]))
		p = []
		for i in l:
			p += [i[1]] * i[0]
		return p


import heapq

class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			d[i] = 1 + d.get(i, 0)
		d2 = {}
		for key in d:
			if d[key] not in d2:
				d2[d[key]] = [key]
			else:
				d2[d[key]].append(key)
		d.clear()
		heap = []
		for i in d2:
			d2[i].sort()
			heap.append([i, d2[i]])
			heapq._siftdown_max(heap, 0, len(heap) - 1)
		d2.clear()
		a.clear()
		while heap:
			p = heapq._heappop_max(heap)
			for ele in p[1]:
				for i in range(p[0]):
					a.append(ele)
		return a


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		freq = Counter(a)
		a.sort()
		a.sort(key=lambda x: freq[x], reverse=True)
		return a


class Solution:

	def sortByFreq(self, a, n):
		a.sort()
		a1 = {}
		for i in a:
			if i not in a1:
				a1[i] = 0
			a1[i] += 1
		a2 = {}
		d = []
		for i in a:
			if a1[i] not in a2:
				a2[a1[i]] = []
				d.append(a1[i])
			a2[a1[i]].append(i)
		d.sort(reverse=True)
		e = []
		for i in d:
			e += a2[i]
		return e


class Solution:

	def sortByFreq(self, a, n):
		from collections import Counter
		dict = {}
		for i in a:
			dict[i] = dict.get(i, 0) + 1
		s = sorted(a, key=lambda x: (-dict[x], x))
		return s


class Solution:

	def sortByFreq(self, a, n):
		a.sort()
		freq_arr = []
		if len(a) == 1:
			freq_arr.append((a[0], 1))
		else:
			freq = 1
			for i in range(1, len(a)):
				if a[i] == a[i - 1]:
					freq += 1
				else:
					freq_arr.append((a[i - 1], freq))
					freq = 1
			freq_arr.append((a[-1], freq))
		freq_arr_sorted = sorted(freq_arr, key=lambda x: x[-1], reverse=True)
		res = []
		for item in freq_arr_sorted:
			res.extend([item[0]] * item[1])
		return res


from collections import defaultdict

class Solution:

	def sortByFreq(self, a, n):
		x = defaultdict(lambda : 0)
		for i in range(n):
			x[a[i]] += 1
		a.sort(key=lambda y: (-x[y], y))
		return a


class Solution:

	def sortByFreq(self, a, n):
		dt = {}
		for i in a:
			if i in dt:
				dt[i] += 1
			else:
				dt[i] = 1
		a.sort(key=lambda x: (dt[x], -x), reverse=True)
		return a


class Solution:

	def sortByFreq(self, a, n):
		f = {}
		for i in range(n):
			if a[i] not in f:
				f[a[i]] = 1
			else:
				f[a[i]] += 1
		a.sort(key=lambda x: (-f[x], x))
		return a


class Solution:

	def sortByFreq(self, a, n):
		a_dict = dict()
		for i in a:
			if i in a_dict:
				a_dict[i] += 1
			else:
				a_dict[i] = 1
		sorted_a_dict = list(sorted(a_dict.items(), key=lambda item: [item[1], -item[0]], reverse=True))
		res = list()
		for (ele, freq) in sorted_a_dict:
			res += [ele] * freq
		return res


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		h = {}
		for i in a:
			if i in h:
				h[i] += 1
			else:
				h[i] = 1
		a.sort(key=lambda x: (-h[x], x))
		return a


class Solution:

	def sortByFreq(self, a, n):
		count = dict()
		for x in a:
			if count.get(x) == None:
				count[x] = 1
			else:
				count[x] += 1
		a.sort(key=lambda e: [count[e], -e])
		return a[::-1]


class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		l = []
		for (i, j) in d.items():
			l.append([i, j])
		l.sort(key=lambda x: (-x[1], x[0]))
		res = []
		for i in l:
			for j in range(i[1]):
				res.append(i[0])
		return res


from collections import OrderedDict

class Solution:

	def sortByFreq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		a.sort(key=lambda x: (-d[x], x))
		return a


from collections import OrderedDict

class Solution:

	def sortByFreq(self, a, n):
		d = OrderedDict()
		l = []
		a.sort()
		for i in a:
			d[i] = 0
		for i in a:
			d[i] += 1
		d = OrderedDict(sorted(d.items(), reverse=True, key=lambda x: x[1]))
		for i in d:
			for j in range(d[i]):
				l.append(i)
		return l


from collections import defaultdict

class Solution:

	def sortByFreq(self, a, n):
		freq = defaultdict(int)
		for num in a:
			freq[num] += 1
		sorted_freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)
		ans = []
		n = len(sorted_freq)
		i = 0
		while i < n:
			temp = []
			curr_freq = sorted_freq[i][1]
			while i < n and curr_freq == sorted_freq[i][1]:
				temp.extend([sorted_freq[i][0]] * curr_freq)
				i += 1
			temp.sort()
			ans.extend(temp)
		return ans


class Solution:

	def sortByFreq(self, a, n):
		hashmap = {}
		for i in a:
			if i in hashmap:
				hashmap[i] += 1
			else:
				hashmap[i] = 1
		a.sort(key=lambda x: (-hashmap[x], x))
		return a


from collections import Counter

class Solution:

	def sortByFreq(self, a, n):
		c = Counter(a)
		result = []
		most = c.most_common()
		most.sort()
		most.sort(key=lambda x: x[1], reverse=True)
		for item in most:
			result += [item[0]] * item[1]
		return result


class Solution:

	def sortByFreq(self, a, n):
		hash = dict()
		for i in range(n):
			hash[a[i]] = hash.get(a[i], 0) + 1
		arr = []
		for (key, val) in sorted(hash.items(), key=lambda x: (-x[1], x[0])):
			for i in range(val):
				arr.append(key)
		return arr