Given an input stream of N integers (alongwith the operation on these integers), the task is to print the number of the distinct elements in the stream after each operation.
The array is will be having positive and negative values. Positive value meaning you have to append it into your database and Negative value means you have to remove it from your database if present and at every step you have to count the number of distinct character in your database.
Example 1:
Input: A[] = {5, 5, 7, -5, -7, 1, 2, -2}
Output: 1 1 2 2 1 2 3 2
Explanation:
Here you can see we have an array of integer as 
stated that positive number means we will adding 
it to our database and negative means we will be 
deleting one occurence of that number from our database.
So, [5, 5, 7, -5, -7, 1, 2, -2] 
Add 5, Unique Value in Data Base is 1 -> [5]
Add 5, Unique Value in Data Base is 1 -> [5, 5]
Add 7, Unique Value in Data Base is 2 -> [5, 5, 7]
Removing 5, Unique Value in Data Base is 2 -> [5, 7]
Removing 7, Unique Value in Data Base is 1 -> [5]
Add 1, Unique Value in Data Base is 2 -> [5, 1]
Add 2, Unique Value in Data Base is 3 -> [5, 1, 2]
Removing 2, Unique Value in Data Base is 2 -> [5, 1]
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 maxDistinctNum() that takes an array (arr), sizeOfArray (n), and return the number of unique value at every instance. The driver code takes care of the printing.
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
 
Input:
First line of the input contains an integer T denoting the number of test cases. Then T test case follows. First line of each test case contains an integer N denoting the number of operations to be performed on a stream. Next N lines two space separated elements, the operation to be performed and the key element.
Constraints:
1 ≤ N ≤ 10^{6}
-10^{6} ≤ A[] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



def maxDistinctNum (self, arr,  n) : 

    # Complete the function

Solutions:
class Solution:

	def maxDistinctNum(self, arr, n):
		d = {}
		a = set()
		l = []
		for i in arr:
			if i >= 0:
				if i not in d:
					d[i] = 1
					a.add(i)
				else:
					d[i] += 1
					a.add(i)
			elif -i in d:
				if d[-i] > 0:
					d[-i] -= 1
					if d[-i] == 0:
						a.discard(-i)
				else:
					a.discard(-i)
			l.append(len(a))
		return l


class Solution:

	def maxDistinctNum(self, arr, n):
		count = []
		cou = 0
		di = {}
		for i in arr:
			if i < 0:
				if -i in di:
					di[-i] -= 1
					if di[-i] == 0:
						cou -= 1
						del di[-i]
						count.append(cou)
					else:
						count.append(cou)
				else:
					count.append(cou)
			elif i not in di:
				di[i] = 1
				cou += 1
				count.append(cou)
			else:
				di[i] += 1
				count.append(cou)


class Solution:

	def maxDistinctNum(self, arr, n):
		hm = {}
		ans = []
		for i in arr:
			x = abs(i)
			if x not in hm and i < 0:
				pass
			elif x in hm and i > 0:
				hm[x] += 1
			elif x in hm and i < 0:
				hm[x] -= 1
				if hm[x] == 0:
					del hm[x]
			else:
				hm[x] = 1
			ans.append(len(hm))
		return ans


class Solution:

	def maxDistinctNum(self, arr, n):
		pos_dict = {}
		count = 0
		res = []
		for elem in arr:
			abs_elem = abs(elem)
			if elem > 0:
				val = pos_dict.get(elem, 0)
				pos_dict.update({elem: val + 1})
				count += 1 if pos_dict[elem] == 1 else 0
			elif pos_dict.get(abs_elem, 0):
				pos_dict.update({abs_elem: pos_dict.get(abs_elem, 0) - 1})
				count -= 1 if not pos_dict.get(abs_elem, 0) else 0
			res.append(count)
		return res


class Solution:

	def maxDistinctNum(self, arr, n):
		a = []
		d = {}
		b = []
		c = 0
		for i in range(n):
			if arr[i] in d:
				d[arr[i]] = d[arr[i]] + 1
			elif arr[i] >= 0:
				d[arr[i]] = 1
				c = c + 1
			elif arr[i] < 0 and -arr[i] in d:
				if d.get(-arr[i]) == 1:
					d.pop(-arr[i])
					c = c - 1
				else:
					d[-arr[i]] = d[-arr[i]] - 1
			b.append(c)
		return b


class Solution:

	def maxDistinctNum(self, arr, n):
		freq = {}
		dist = 0
		res = []
		for i in arr:
			if i > 0:
				if i not in freq or freq[i] == 0:
					freq[i] = 0
					dist += 1
				freq[i] += 1
			elif i < 0:
				i = abs(i)
				if i in freq:
					if freq[i] > 0:
						if freq[i] == 1:
							dist -= 1
						freq[i] -= 1
			res.append(dist)
		return res


class Solution:

	def maxDistinctNum(self, arr, n):
		hashmap = {}
		start = 0
		unique = [0] * n
		for item in arr:
			if item >= 0:
				if item in hashmap:
					hashmap[item] += 1
				else:
					hashmap[item] = 1
			elif item < 0:
				if -1 * item in hashmap:
					hashmap[-1 * item] -= 1
				if -1 * item in hashmap and hashmap[-1 * item] <= 0:
					del hashmap[-1 * item]
			unique[start] = len(hashmap)
			start += 1
		return unique


class Solution:

	def maxDistinctNum(self, arr, n):
		distinct = set()
		count = [0] * (10 ** 6 + 1)
		unique = [0] * n
		start = 0
		for item in arr:
			if item >= 0:
				count[item] += 1
				distinct.add(item)
			elif item < 0:
				if count[-1 * item] != 0:
					count[-1 * item] -= 1
				if count[-1 * item] == 0 and -1 * item in distinct:
					distinct.remove(-1 * item)
			unique[start] = len(distinct)
			start += 1
		return unique


class Solution:

	def maxDistinctNum(self, arr, n):
		s = set()
		stream = {}
		li = []
		for i in arr:
			if i >= 0:
				if i not in stream:
					stream[i] = 1
				else:
					stream[i] += 1
				s.add(i)
			elif -i in stream:
				if stream[-i] > 0:
					stream[-i] -= 1
					if stream[-i] == 0:
						s.discard(-i)
				else:
					s.discard(-i)
			li.append(len(s))
		return li


class Solution:

	def maxDistinctNum(self, arr, n):
		r = []
		d = {}
		c = 0
		for j in arr:
			if j > 0:
				if j not in d:
					d[j] = 1
					c += 1
				else:
					d[j] += 1
				r.append(c)
			else:
				if j * -1 in d:
					d[j * -1] -= 1
					if d[j * -1] == 0:
						c -= 1
						del d[j * -1]
				r.append(c)
		return r


class Solution:

	def maxDistinctNum(self, arr, n):
		count = 0
		elems = []
		H = {}
		for i in range(n):
			count += 1
			if arr[i] < 0:
				if -1 * arr[i] in H.keys() and H[-1 * arr[i]] > 0:
					H[-1 * arr[i]] -= 1
					if count > 0 and H[-1 * arr[i]] == 0:
						count -= 2
					elif count > 0 and H[-1 * arr[i]] != 0:
						count -= 1
				elif -1 * arr[i] not in H.keys():
					count -= 1
				elif -1 * arr[i] in H.keys() and H[-1 * arr[i]] == 0:
					count -= 1
			if arr[i] >= 0:
				H[arr[i]] = H.get(arr[i], 0) + 1
				if H[arr[i]] > 1:
					count -= 1
			elems.append(count)
		return elems


class Solution:

	def maxDistinctNum(self, arr, n):
		d = {}
		result = []
		for item in arr:
			if item > 0:
				if item in d:
					d[item] += 1
				else:
					d[item] = 1
			elif -item in d:
				d[-item] -= 1
				if d[-item] == 0:
					del d[-item]
			result.append(len(d))
		return result


class Solution:

	def maxDistinctNum(self, arr, n):
		count = 0
		l = []
		l1 = []
		d = {}
		for i in arr:
			if i > 0:
				if i not in d:
					d[i] = 1
					count += 1
				else:
					d[i] += 1
			elif -i in d:
				d[-i] -= 1
				if d[-i] == 0:
					del d[-i]
					count -= 1
			l1.append(count)
		return l1


class Solution:

	def maxDistinctNum(self, arr, n):
		hashMap = {}
		ans = []
		count = 0
		for i in range(n):
			if arr[i] < 0:
				if -arr[i] in hashMap:
					hashMap[-arr[i]] -= 1
				if hashMap.get(-arr[i]) == 0:
					del hashMap[-arr[i]]
			elif arr[i] in hashMap:
				hashMap[arr[i]] += 1
			else:
				hashMap[arr[i]] = 1
			ans.append(len(hashMap))
		return ans


class Solution:

	def maxDistinctNum(self, arr, n):
		dis = {}
		res = []
		count = 0
		for x in arr:
			if x in dis:
				dis[x] += 1
			elif abs(x) in dis:
				dis[abs(x)] -= 1
				if dis[abs(x)] == 0:
					del dis[abs(x)]
					count -= 1
			elif x > 0:
				dis[x] = 1
				count += 1
			res.append(count)
		return res


class Solution:

	def maxDistinctNum(self, arr, n):
		freq = {}
		new_arr = []
		for i in range(n):
			if arr[i] > 0:
				if arr[i] in freq:
					freq[arr[i]] += 1
				else:
					freq[arr[i]] = 1
			else:
				val = abs(arr[i])
				if val in freq:
					freq[val] -= 1
					if freq[val] == 0:
						del freq[val]
			new_arr.append(len(freq))
		return new_arr


class Solution:

	def maxDistinctNum(self, arr, n):
		s = {}
		l = []
		for i in arr:
			if i > 0:
				if i in s:
					s[i] += 1
				else:
					s[i] = 1
			elif -i in s:
				s[-i] -= 1
				if s[-i] == 0:
					del s[-i]
			l.append(len(s))
		return l
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Solution().maxDistinctNum(arr, n)
	print(*res)


class Solution:

	def maxDistinctNum(self, arr, n):
		new_arr = {}
		size_arr = []
		val = 0
		for i in range(0, n):
			if arr[i] > 0:
				if arr[i] in new_arr:
					new_arr[arr[i]] += 1
				else:
					new_arr[arr[i]] = 1
			else:
				val = abs(arr[i])
				if val in new_arr:
					new_arr[val] -= 1
					if new_arr[val] == 0:
						del new_arr[val]
			size_arr.append(len(new_arr))
		return size_arr
for _ in range(0, int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	res = Solution().maxDistinctNum(arr, n)
	print(*res)


class Solution:

	def maxDistinctNum(self, arr, n):
		count = {}
		l = []
		for element in arr:
			x = abs(element)
			if element > 0 and x in count:
				count[x] += 1
			elif element < 0 and x not in count:
				pass
			elif x in count and element < 0:
				count[x] -= 1
				if count[x] == 0:
					del count[x]
			else:
				count[x] = 1
			l.append(len(count))
		return l


class Solution:

	def maxDistinctNum(self, arr, n):
		from collections import defaultdict
		s = defaultdict(int)
		ans = []
		for i in arr:
			if i < 0:
				s[abs(i)] -= 1
				if s[abs(i)] <= 0:
					s.pop(abs(i))
			else:
				s[i] += 1
			ans.append(len(s))
		return ans


class Solution:

	def maxDistinctNum(self, arr, n):
		m = {}
		c = []
		for i in arr:
			if i < 0 and abs(i) in m:
				m[abs(i)] = m[abs(i)] - 1
				if m[abs(i)] == 0:
					m.pop(abs(i))
					no = len(m)
			elif i in m:
				m[i] = m[i] + 1
			elif i < 0:
				no = len(m)
			else:
				m[i] = 1
				no = len(m)
			c.append(no)
		return c


class Solution:

	def maxDistinctNum(self, arr, n):
		d = {}
		ans = []
		for x in arr:
			if x > 0:
				d[x] = d.get(x, 0) + 1
			elif abs(x) in d:
				num = abs(x)
				d[num] = d.get(num) - 1
				if d[num] == 0:
					del d[num]
			ans.append(len(d))
		return ans