Given an array arr[] of size N, the task is to check whether it is possible to obtain an array having distinct neighboring elements by swapping two neighboring array elements.
Example 1:
Input: N = 3, arr[] = {1, 1, 2}
Output:  YES
Explanation: Swap 1 (second last element) 
and 2 (last element), to obtain 1 2 1,
which has distinct neighbouring elements.
Example 2:
Input: N = 4, arr[] = {7, 7, 7, 7}
Output: NO
Explanation: We can't swap to obtain 
distinct elements in neighbor .
Your Task:
You don't need to read input or print anything. You just need to complete the function distinctAdjacentElement() that takes array arr[]  and its size N as input parameters and returns a boolean value denoting if distinct neighbours are possible or not. 
Note: The generated output is YES or NO according to the returned value.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Constraints:
2 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def distinctAdjacentElement(self,arr, n): 

        # code here 

Solutions:
from collections import Counter

class Solution:

	def distinctAdjacentElement(self, arr, n):
		k = {}
		kis = []
		for i in arr:
			if i not in k:
				k[i] = 1
			else:
				k[i] += 1
		for i in k:
			kis.append(k[i])
		m = max(kis)
		if m <= (n + 1) // 2:
			return 'YES'


from collections import Counter

class Solution:

	def distinctAdjacentElement(self, arr, n):
		a = Counter(arr)
		max1 = max(a.values())
		if max1 <= (n + 1) // 2:
			return 1
		else:
			return 0


class Solution:

	def distinctAdjacentElement(self, arr, n):
		a = {}
		for i in arr:
			if i not in a:
				a[i] = 1
			else:
				a[i] += 1
		maxq = max(a.values())
		if maxq <= int(n + 1) / 2:
			return 1
		else:
			return 0


class Solution:

	def distinctAdjacentElement(self, arr, n):
		freq = {}
		for i in arr:
			if i not in freq:
				freq[i] = 0
			freq[i] += 1
		dif = 0
		j = 0
		for i in freq:
			if j % 2 == 0:
				dif += freq[i]
			else:
				dif -= freq[i]
			j += 1
		m = 0
		for i in freq:
			m = max(m, freq[i])
		if m > (n + 1) // 2:
			return False
		return True


class Solution:

	def distinctAdjacentElement(self, arr, n):
		count = {}
		for item in arr:
			if item not in count:
				count[item] = 1
			else:
				count[item] += 1
		maximum = -1
		for value in count.values():
			if value > maximum:
				maximum = value
		if maximum <= int((n + 1) / 2):
			return True
		else:
			return False


class Solution:

	def distinctAdjacentElement(self, arr, n):
		dict_ = {}
		for elem in arr:
			dict_.update({elem: dict_.get(elem, 0) + 1})
		return max(dict_.values()) <= (n + 1) // 2


class Solution:

	def distinctAdjacentElement(self, arr, n):
		if n == 2 and arr[0] == arr[1]:
			return False
		dict_ = {}
		for elem in arr:
			dict_[elem] = dict_[elem] + 1 if elem in dict_ else 1
		return max(dict_.values()) <= (n + 1) // 2


class Solution:

	def distinctAdjacentElement(self, arr, n):
		arr.sort()
		count = 1
		m = 0
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				count += 1
			else:
				m = max(count, m)
				count = 1
		m = max(count, m)
		if n % 2 == 0:
			if m <= n // 2:
				return True
			else:
				return False
		elif m <= (n + 1) // 2:
			return True
		else:
			return False


class Solution:

	def distinctAdjacentElement(self, arr, n):
		k = {}
		kis = []
		for i in arr:
			if i not in k:
				k[i] = 1
			else:
				k[i] += 1
		for i in k:
			kis.append(k[i])
		m = max(kis)
		if m <= (n + 1) // 2:
			return 'YES'


class Solution:

	def distinctAdjacentElement(self, arr, n):
		ele = arr[0]
		f = 0
		for i in range(0, len(arr)):
			if arr[i] == ele:
				f = 1
			else:
				f = -1
				break
		if f == 1:
			return False
		else:
			sz = (n + 1) // 2
			freq = 0
			m = 0
			f = 0
			list1 = []
			for i in range(0, len(arr)):
				if arr[i] not in list1:
					list1.append(arr[i])
					c = arr.count(arr[i])
					if f == 0:
						m = c
						f = 1
					elif c > m:
						m = c
			if m <= sz:
				return True
			else:
				return False


class Solution:

	def distinctAdjacentElement(self, arr, n):
		di = {}
		m = 0
		for i in arr:
			if i not in di:
				di[i] = 1
			else:
				di[i] += 1
		for i in di:
			if m < di[i]:
				m = di[i]
		if m > (n + 1) // 2:
			return 0
		else:
			return 1


class Solution:

	def distinctAdjacentElement(self, arr, n):
		d = dict()
		list1 = []
		for i in arr:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
		for j in d:
			list1.append(d[j])
		mx = max(list1)
		if mx <= (n + 1) // 2:
			return 'YES'


class Solution:

	def distinctAdjacentElement(self, arr, n):
		m = {}
		for i in arr:
			m[i] = m.get(i, 0) + 1
			if m[i] > (n + 1) // 2:
				return 0
		return 1


class Solution:

	def distinctAdjacentElement(self, arr, n):
		d = {}
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		count = 0
		for i in d:
			count = max(count, d[i])
		if n % 2 == 0:
			if count <= n // 2:
				return True
			return False
		else:
			if count <= (n + 1) // 2:
				return True
			return False


class Solution:

	def distinctAdjacentElement(self, arr, n):
		dis = {}
		for x in arr:
			if x in dis:
				dis[x] += 1
			else:
				dis[x] = 1
		mx = max([x for x in dis.values()])
		return False if mx > (n + 1) // 2 else True


class Solution:

	def distinctAdjacentElement(self, arr, n):
		size = 10 ** 6 + 1
		count = [0] * size
		for i in range(n):
			count[arr[i]] += 1
		max_val = max(count)
		if n % 2 == 0:
			if max_val <= n // 2:
				return True
		if n % 2 == 1:
			if max_val <= (n + 1) // 2:
				return True
		return False


class Solution:

	def distinctAdjacentElement(self, arr, n):
		arr.sort()
		count = 1
		m = 0
		for i in range(n - 1):
			if arr[i] == arr[i + 1]:
				count += 1
			else:
				m = max(count, m)
				count = 1
		m = max(count, m)
		if n % 2 == 0:
			if m <= n // 2:
				return True
			else:
				return False
		elif m <= (n + 1) // 2:
			return True
		else:
			return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		if ob.distinctAdjacentElement(arr, n):
			print('YES')
		else:
			print('NO')


class Solution:

	def distinctAdjacentElement(self, arr, n):
		mp = {}
		for i in arr:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		x = -1
		for i in mp.values():
			x = max(x, i)
		return x <= (n + 1) // 2


class Solution:

	def distinctAdjacentElement(self, arr, n):
		from collections import defaultdict
		d = defaultdict(int)
		maxx = 0
		for i in arr:
			d[i] += 1
			maxx = max(d[i], maxx)
		if maxx > (n + 1) // 2:
			return False
		else:
			return True


class Solution:

	def distinctAdjacentElement(self, a, n):
		m = dict()
		for i in range(n):
			if a[i] in m:
				m[a[i]] += 1
			else:
				m[a[i]] = 1
		mx = 0
		for i in range(n):
			if mx < m[a[i]]:
				mx = m[a[i]]
		if mx > (n + 1) // 2:
			return False
		else:
			return True


class Solution:

	def distinctAdjacentElement(self, arr, n):
		mp = dict()
		for i in range(n):
			if arr[i] in mp:
				mp[arr[i]] += 1
			else:
				mp[arr[i]] = 1
		for i in range(n):
			if mp[arr[i]] > (n + 1) / 2:
				return False
		return True


class Solution:

	def distinctAdjacentElement(self, arr, n):
		freqs = {}
		for el in arr:
			if el in freqs:
				freqs[el] += 1
			else:
				freqs[el] = 1
		max_freq = 0
		for v in freqs.values():
			if v > max_freq:
				max_freq = v
		if max_freq <= (n + 1) // 2:
			return True
		return False


from collections import Counter

class Solution:

	def distinctAdjacentElement(self, arr, n):
		s = Counter(arr)
		for i in s:
			if s[i] > (n + 1) // 2:
				return False
		return True


class Solution:

	def distinctAdjacentElement(self, arr, n):
		dict1 = {}
		for i in range(n):
			if arr[i] in dict1:
				dict1[arr[i]] += 1
			else:
				dict1[arr[i]] = 1
		val = sorted(dict1.items(), key=lambda x: x[1], reverse=True)[0][1]
		if val <= (n + 1) / 2:
			return True
		else:
			return False