Python's built-in set uses hashing to support $\mathcal{O}(1)$ insertion, deletion, and searches. Some operations on a Python set named s include:

• s.add(x): adds element x to s if not already present
• s.remove(x): removes an element x from set if present
• x in s: checks whether s contains the element x

Copy
s = set()
s.add(1)  # {1}
s.add(4)  # {1, 4}
s.add(2)  # {1, 4, 2}
s.add(1)  # {1, 4, 2}
# the add method did nothing because 1 was already in the set
print(1 in s)  # True
s.remove(1)  # {4, 2}
print(5 in s)  # False
s.remove(0)  # {4, 2}
# if the element to be removed does not exist, nothing happens

Copy
n = int(input())  # unused
nums = [int(x) for x in input().split()]
distinct_nums = set(nums)
print(len(distinct_nums))

Or we can do this more concisely by skipping the creation of the list, and use a set comprehension directly:

Copy
n = int(input())  # unused
distinct_nums = {int(x) for x in input().split()}
print(len(distinct_nums))

However, it is possible to construct a test case that causes the above solution to run in $\Theta(N^2)$ time, so this solution does not receive full credit.

One way to get around this with high probability is to incorporate randomness; see this comment for more information.

Copy
import random

RANDOM = random.randrange(2**62)


def Wrapper(x):
	return x ^ RANDOM


n = int(input())  # unused
distinct_nums = {Wrapper(int(x)) for x in input().split()}
print(len(distinct_nums))

Another (less efficient) way is to use strings instead of integers since the hash function for strings is randomized.

Copy
n = int(input())  # unused
distinct_nums = set(input().split())
print(len(distinct_nums))

Colloquially, hashmaps are referred to as dicts in python.

Copy
d = {}
d[1] = 5  # {1: 5}
d[3] = 14  # {1: 5, 3: 14}
d[2] = 7  # {1: 5, 2: 7, 3: 14}
del d[2]  # {1: 5, 3: 14}
print(d[1])  # 5
print(7 in d)  # False
print(1 in d)  # True

To iterate over dicts, there are three options, all of which involve for loops. Dicts will be returned in the same order of insertion in Python 3.6+. You can iterate over the keys:

Copy
for key in d:
	print(key)

Over the values:

Copy
for value in d.values():
	print(value)

And even over key-value pairs:

Copy
for key, value in d.items():
	print(key, value)

It's also possible to change the values while iterating over the keys (or over the values themselves, if they're mutable):

Copy
for key in d:
	d[key] = 1234  # Change all values to 1234

Modifying a Collection (Set, Map, etc.) in the middle of a for-each loop will cause a ConcurrentModificationException. See the following snippet for an example:

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

for (int key : m.keySet()) {
	m.remove(key);  // ConcurrentModificationException thrown!!
}

One work-around is to use Iterator and the .remove() method to remove elements while looping over them, like in the next code snippet:

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

Iterator<Map.Entry<Integer, Integer>> iter = m.entrySet().iterator();
while (iter.hasNext()) {
	int key = iter.next().getKey();
	if (key == 0 || key == 2) { iter.remove(); }

However, Iterator is outside the scope of this module.

The easiest option (in most cases) if you want to remove/insert multiple entries at once is to use your Container's .addAll(c) or .removeAll(c) methods. That means that you should put all the elements you want to remove (or add) in a new Collection, and then use that new Collection as the parameter of the .addAll(c) or .removeAll(c) method that you call on your original Collection. See the following code snippet for an example (it works equivalently to the code above):

Copy
Map<Integer, Integer> m = new TreeMap<>();
// m starts as {0: 0, 1: 1, 2: 2}
m.put(0, 0);
m.put(1, 1);
m.put(2, 2);

Set<Integer> keysToRemove = new TreeSet<>();
for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
	int key = entry.getKey();
	if (key == 0 || key == 2) { keysToRemove.add(key); }

Unfortunately, the straightforward solution fails a few tests specifically designed to make Python dicts run slowly:

Copy
a = dict()  # Dictionary to store assigned indices
for _ in range(int(input())):
	nums = list(map(int, input().split()))
	if nums[0] == 0:
		a[nums[1]] = nums[2]
	elif nums[0] == 1:
		# Print a[k] if present, else 0
		print(a.get(nums[1], 0))

To pass all the tests, we can use one of the workarounds mentioned for set.

Copy
import random

RANDOM = random.randrange(2**62)


def wrap(x):
	return x ^ RANDOM


a = dict()  # Dictionary to store assigned indices