Given an array of elements. The task is to calculate the cumulative frequency of each element of the array.
Note :- Cumulative frequency should be taken according to the sorted order of elements.
Example 1:
Input : Arr[] = {1, 2, 2, 1, 3, 4}
Output : 2 4 5 6
Explanation:
Here we have an array arr[] = [1, 3, 2, 
                               1, 2, 4]
Output :1->2
        2->4
        3->5
        4->6
So, the return array will have [2, 4, 5, 6] 
as an output.
Example 2:
Input : Arr[] = {1, 2, 1, 2, 1, 2}
Output : 3 6
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function countfreq() that takes an array (arr), sizeOfArray (n) and return the array of cumulative frequency values. The driver code takes care of the printing.
Expected Time Complexity: O(NLOG(N)).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Data structures

Starter code: #User function Template for python3



class Solution:

    def countFreq(self, a, n):

        #Complete the function

Solutions:
class Solution:

	def countFreq(self, a, n):
		a.sort()
		arr = []
		count = 1
		for i in range(1, n):
			if a[i] != a[i - 1]:
				arr.append(count)
			count += 1
		arr.append(count)
		return arr


class Solution:

	def countFreq(self, arr, n):
		mp = {}
		for i in range(n):
			if arr[i] not in mp.keys():
				mp[arr[i]] = 1
			else:
				mp[arr[i]] += 1
		count = 0
		freq_arr = []
		for i in mp:
			freq_arr.append([i, mp[i]])
		freq_arr.sort()
		ans = []
		for i in range(len(freq_arr)):
			ans.append(freq_arr[i][1])
		for i in range(1, len(ans)):
			ans[i] += ans[i - 1]
		return ans


class Solution:

	def countFreq(self, a, n):
		a.sort()
		d = {}
		for i in range(n):
			d[a[i]] = d.get(a[i], 0) + 1
		res = []
		freq = 0
		for i in range(n):
			freq += d[arr[i]]
			if d[arr[i]] > 0:
				res.append(freq)
			d[arr[i]] = 0
		return res


from collections import Counter

class Solution:

	def countFreq(self, a, n):
		b = Counter(a)
		out = []
		cf = 0
		out = list(set(arr))
		out.sort()
		for i in range(len(out)):
			cf += b[out[i]]
			out[i] = cf
		return out


from collections import Counter

class Solution:

	def countFreq(self, a, n):
		li = []
		di = Counter(a)
		a = list(di.keys())
		a.sort()
		cf = 0
		for i in range(len(di)):
			cf += di[a[i]]
			li.append(cf)
		return li


from collections import Counter

class Solution:

	def countFreq(self, a, n):
		c = Counter(a)
		summa = 0
		result = []
		for item in sorted(c.keys()):
			summa += c[item]
			result.append(summa)
		return result


class Solution:

	def countFreq(self, a, n):
		a.sort()
		res = []
		c = 1
		for i in range(1, n):
			if a[i] != a[i - 1]:
				if res == []:
					res.append(c)
				else:
					res.append(c + res[-1])
				c = 1
			else:
				c += 1
		if res == []:
			res.append(c)
		else:
			res.append(c + res[-1])
		return res


class Solution:

	def countFreq(self, a, n):
		dict1 = {}
		for i in range(n):
			dict1[a[i]] = dict1.get(a[i], 0) + 1
		new_array = list(set(a))
		new_array.sort()
		result = []
		sum = 0
		for i in range(len(new_array)):
			sum += dict1[new_array[i]]
			result.append(sum)
		return result


class Solution:

	def countFreq(self, a, n):
		dic = {}
		k = 0
		l = []
		a.sort()
		for i in range(len(a)):
			if a[i] in dic:
				dic[a[i]] += 1
			else:
				dic[a[i]] = 1
				l.append(a[i])
		lis = []
		for i in l:
			k += dic[i]
			lis.append(k)
		return lis


class Solution:

	def countFreq(self, a, n):
		a.sort()
		val = 1
		lst = []
		for i in range(1, n):
			if a[i] == a[i - 1]:
				val += 1
			else:
				lst.append(val)
				val += 1
		lst.append(val)
		return lst


class Solution:

	def countFreq(self, a, n):
		a.sort()
		Hash = dict()
		for i in range(n):
			if a[i] in Hash:
				Hash[a[i]] += 1
			else:
				Hash[a[i]] = 1
		key_list = [key for key in Hash]
		key_list.sort()
		res = []
		res.append(Hash[key_list[0]])
		sum = Hash[key_list[0]]
		for i in range(len(key_list) - 1):
			sum += Hash[key_list[i + 1]]
			res.append(sum)
		return res


class Solution:

	def countFreq(self, a, n):
		a.sort()
		res = []
		d = {}
		count = 0
		for i in a:
			if i not in d:
				d[i] = 0
			d[i] += 1
		for key in sorted(d.keys()):
			count += d[key]
			res.append(count)
		return res


class Solution:

	def countFreq(self, a, n):
		a.sort()
		res = []
		d = {}
		count = 0
		for i in a:
			if i not in d:
				d[i] = 0
			d[i] += 1
		for i in a:
			if i in d:
				count += d[i]
				res.append(count)
				del d[i]
		return res


class Solution:

	def countFreq(self, a, n):
		m = {}
		for i in a:
			if i in m:
				m[i] += 1
			else:
				m[i] = 1
		b = []
		for i in m:
			b.append([i, m[i]])
		b.sort(key=lambda x: x[0])
		s = 0
		g = []
		for i in b:
			s += i[1]
			g.append(s)
		return g


class Solution:

	def countFreq(self, a, n):
		d = {}
		for i in range(n):
			if a[i] not in d:
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		lst = sorted(d.items(), key=lambda x: x[0])
		ans = []
		prev = 0
		for (k, v) in lst:
			ans.append(v + prev)
			prev = v + prev
		return ans


from collections import OrderedDict

class Solution:

	def countFreq(self, a, n):
		a.sort()
		hm = OrderedDict()
		for i in range(n):
			if a[i] not in hm:
				hm[a[i]] = 1
			else:
				hm[a[i]] = hm[a[i]] + 1
		l1 = list(hm.keys())
		k = len(l1)
		for i in range(k):
			if i == k - 1:
				break
			hm[l1[i + 1]] = hm[l1[i + 1]] + hm[l1[i]]
		return list(hm.values())


class Solution:

	def countFreq(self, a, n):
		dic = dict()
		a.sort()
		for i in range(n):
			dic[a[i]] = dic.get(a[i], 0) + 1
		sum = 0
		l = []
		for i in range(n):
			sum += dic[a[i]]
			if dic[a[i]] > 0:
				l.append(sum)
				dic[a[i]] = 0
		return l


class Solution:

	def countFreq(self, a, n):
		k = [0]
		s = 0
		c = 1
		a = sorted(a)
		for i in range(n - 1):
			if a[i] == a[i + 1]:
				c += 1
			else:
				k.append(k[-1] + c)
				c = 1
		if c >= 1:
			k.append(k[-1] + c)
		return k[1:]
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.countFreq(arr, n)
	print(*v)


class Solution:

	def countFreq(self, a, n):
		dca = {}
		for i in a:
			if i in dca.keys():
				dca[i] = dca[i] + 1
			else:
				dca[i] = 1
		rslt = []
		st = list(dca.keys())
		st.sort()
		idx = 0
		for i in st:
			if idx == 0:
				rslt.append(dca[i])
			else:
				rslt.append(dca[i] + rslt[idx - 1])
			idx = idx + 1
		return rslt
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.countFreq(arr, n)
	print(*v)


class Solution:

	def countFreq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		ans = []
		count = 0
		x = sorted(set(a))
		for i in x:
			ans.append(count + d[i])
			count += d[i]
		return ans


from bisect import bisect_left as BL

class Solution:

	def countFreq(self, a, n):
		a.sort()
		s = 1
		res = []
		for i in range(n - 1):
			if a[i] != a[i + 1]:
				res.append(s)
			s += 1
		return res + [s]


from bisect import bisect_left as BL

class Solution:

	def countFreq(self, a, n):
		a.sort(reverse=True)
		d = {}
		for e in a:
			d[e] = 1 + d.get(e, 0)
		res = [0] * n
		z = []
		for (i, e) in reversed(list(enumerate(a))):
			z.insert(BL(z, e), e)
			res[i] = BL(z, e) + d[e]
		return sorted(list(set(res)))


class Solution:

	def countFreq(self, a, n):
		a.sort()
		res = []
		s = 1
		for i in range(0, n - 1):
			if arr[i] != arr[i + 1]:
				res.append(s)
			s += 1
		res.append(s)
		return res


class Solution:

	def countFreq(self, a, n):
		d = {}
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		at = set(a)
		at = list(at)
		at.sort()
		r = [0] * len(at)
		for i in range(len(at)):
			if i == 0:
				r[i] = d[at[i]] + r[i - 1]
			else:
				r[i] = d[at[i]] + r[i - 1]
		return r


class Solution:

	def countFreq(self, a, n):
		feq = {}
		c_sum = []
		sm = 0
		for i in range(0, n):
			if a[i] in feq:
				feq[a[i]] += 1
			else:
				feq[a[i]] = 1
		for key in sorted(feq.keys()):
			sm += feq[key]
			c_sum.append(sm)
		return c_sum


class Solution:

	def countFreq(self, a, n):
		v = []
		a.sort()
		for i in range(1, n):
			if a[i] != a[i - 1]:
				v.append(i)
		v.append(n)
		return v


import collections

class Solution:

	def countFreq(self, a, n):
		hm = {}
		for i in range(0, n):
			hm[a[i]] = hm.get(a[i], 0) + 1
		st = set()
		for x in hm:
			st.add((x, hm[x]))
		cumul = []
		s = 0
		for x in sorted(st):
			s += x[1]
			cumul.append(s)
		return cumul


class Solution:

	def countFreq(self, a, n):
		hash_map = {}
		for i in a:
			if i not in hash_map:
				hash_map[i] = 1
			else:
				hash_map[i] = hash_map[i] + 1
		a = list(set(a))
		a.sort()
		count = 0
		for i in range(len(a)):
			count = count + hash_map[a[i]]
			a[i] = count
		return a


class Solution:

	def countFreq(self, a, n):
		freqs = {}
		for ai in a:
			if ai not in freqs:
				freqs[ai] = 1
			else:
				freqs[ai] += 1
		keys = sorted(freqs.keys())
		_sum = 0
		_sums = []
		for keyi in keys:
			_sum += freqs[keyi]
			_sums.append(_sum)
		return _sums


from collections import Counter

class Solution:

	def countFreq(self, a, n):
		arr.sort()
		l = []
		x = a[0]
		c = 1
		for i in range(1, n):
			if x == a[i]:
				c += 1
			else:
				l.append(c)
				x = a[i]
				c += 1
		l.append(c)
		return l


class Solution:

	def countFreq(self, a, n):
		from collections import OrderedDict
		inc = 0
		counter = {}
		for i in a:
			counter.setdefault(i, 0)
			counter[i] += 1
		counters = OrderedDict(sorted(counter.items()))
		res = []
		for key in counters:
			inc += counters[key]
			res.append(inc)
		return res


class Solution:

	def countFreq(self, a, n):
		dic = {}
		for i in range(n):
			dic[a[i]] = dic.get(a[i], 0) + 1
		s = set()
		for x in dic:
			s.add((x, dic[x]))
		cumul = 0
		ls = []
		for x in sorted(s):
			cumul += x[1]
			ls.append(cumul)
		return ls


class Solution:

	def countFreq(self, a, n):
		a.sort()
		dic = {}
		for i in range(n):
			if a[i] not in dic:
				dic[a[i]] = 1
			else:
				dic[a[i]] += 1
		ls = []
		temp = 0
		i = 0
		while i < n - 1:
			if a[i] != a[i + 1]:
				ls.append(temp + dic[a[i]])
				temp = temp + dic[a[i]]
			i += 1
		if n > 1:
			ls.append(temp + dic[a[-1]])
		else:
			ls.append(1)
		return ls


class Solution:

	def countFreq(self, a, n):
		maxEle = max(a)
		frequency = [0] * maxEle
		fNoZero = []
		for num in a:
			frequency[num - 1] += 1
		for num in frequency:
			if num == 0:
				continue
			fNoZero.append(num)
		for index in range(1, len(fNoZero)):
			fNoZero[index] = fNoZero[index - 1] + fNoZero[index]
		return fNoZero


class Solution:

	def countFreq(self, a, n):
		freq = dict()
		l = []
		c = 0
		for i in a:
			freq[i] = freq.get(i, 0) + 1
		a = list(set(a))
		a.sort()
		for i in a:
			c = c + freq[i]
			l.append(c)
		return l


class Solution:

	def countFreq(self, a, n):
		a.sort()
		m = []
		d = {}
		c = 0
		for i in a:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
				m.append(c)
			c += 1
		m.append(c)
		return m[1:]


class Solution:

	def countFreq(self, arr, n):
		arr.sort()
		first = 0
		for i in range(1, n):
			if arr[i - 1] != arr[i]:
				arr[first] = i
				first += 1
		arr[first] = n
		return arr[:first + 1]


class Solution:

	def countFreq(self, a, n):
		dic = {}
		for i in a:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		li = sorted(list(dic.keys()))
		a = 0
		lis = []
		for i in li:
			a += dic[i]
			lis += [a]
		return lis


class Solution:

	def countFreq(self, a, n):
		a.sort()
		t = a[0]
		l = []
		c = 0
		for i in range(n):
			if a[i] == t:
				c += 1
			else:
				l.append(c)
				t = a[i]
				c += 1
		l.append(c)
		return l


class Solution:

	def countFreq(self, a, n):
		a.sort()
		from collections import OrderedDict
		myMap = OrderedDict()
		for i in range(n):
			if a[i] in myMap:
				myMap[a[i]] += 1
			else:
				myMap[a[i]] = 1
		output = []
		curr_ele = 0
		for val in myMap.values():
			curr_ele += val
			output.append(curr_ele)
		return output


import collections

class Solution:

	def countFreq(self, a, n):
		mp = {}
		for i in a:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		k = 0
		l = []
		od = collections.OrderedDict(sorted(mp.items()))
		for (i, v) in od.items():
			l.append(v + k)
			k += v
		return l


class Solution:

	def countFreq(self, a, n):
		from collections import defaultdict
		b = defaultdict(lambda : 0)
		for i in a:
			b[i] = b[i] + 1
		k = 0
		c = []
		for i in range(0, max(a) + 2):
			if b[i] > 0:
				k = k + b[i]
				c.append(k)
		return c


class Solution:

	def countFreq(self, a, n):
		a = sorted(a)
		ans = []
		for i in range(n):
			if i != n - 1 and a[i + 1] != a[i]:
				ans.append(i + 1)
			elif i == n - 1:
				ans.append(i + 1)
		return ans


class Solution:

	def countFreq(self, a, n):
		from collections import Counter
		c = Counter(a)
		M = len(c)
		lis = c.most_common(M)
		lis.sort()
		s = 0
		res = []
		for i in range(len(lis)):
			s += lis[i][1]
			res.append(s)
		return res


from collections import OrderedDict

class Solution:

	def countFreq(self, a, n):
		a.sort()
		dic = OrderedDict()
		for i in range(n):
			if a[i] not in dic:
				dic[a[i]] = 1
			else:
				dic[a[i]] += 1
		answer = []
		solv = 0
		for i in dic:
			solv += dic[i]
			answer.append(solv)
		return answer


from collections import OrderedDict

class Solution:

	def countFreq(self, a, n):
		a.sort()
		hash1 = OrderedDict()
		for i in a:
			if i in hash1:
				hash1[i] += 1
			else:
				hash1[i] = 1
		arr = []
		count = 0
		for i in hash1:
			count += hash1[i]
			arr.append(count)
		return arr


class Solution:

	def countFreq(self, a, n):
		d = {}
		for e in a:
			if e not in d:
				d[e] = 1
			else:
				d[e] += 1
		res = list(set(a))
		res.sort()
		ans = [d[res[0]]]
		a1 = d[res[0]]
		for i in range(1, len(res)):
			a1 += d[res[i]]
			ans.append(a1)
		return ans