# CARDSWIPE - Editorial

Author: notsoloud
Tester: satyam_343
Editorialist: iceknight1093

1172

None

# PROBLEM:

You’re given a sequence of N swipe-ins and swipe-outs to a building.
Find the maximum number of people in it, at any point of time.

# EXPLANATION:

Let \texttt{cur} denote the number of people currently in the building.
Initially, \texttt{cur} = 0.

Then, for each 1 \leq i \leq N:

• If A_i is not inside the building, this is an in-swipe.
So, \texttt{cur} will increase by 1.
• Otherwise, A_i was already inside the building, and this is an out-swipe.
\texttt{cur} will decrease by 1.

The final answer is the maximum value of \texttt{cur} across the entire process.

We only need to quickly check whether A_i is already inside the building or not.
This can be done, for example, with a mark array.

That is, keep an array mark of length N, where mark[x] = 1 means person x is inside the building, and mark[x] = 0 otherwise.
Then,

• When person A_i enters, set mark[a[i]] = 1.
• When person A_i exits, set mark[a[i]] = 0.

Each enter/exit is handled in \mathcal{O}(1) time, for a solution in \mathcal{O}(N) overall.

# TIME COMPLEXITY

\mathcal{O}(N) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = *(n + 1)
inside, ans = 0, 0
for x in map(int, input().split()):
if a[x] == 1: inside -= 1
a[x] ^= 1
if a[x] == 1: inside += 1
ans = max(ans, inside)
print(ans)

3 Likes
for i in range(int(input())):
length = int(input())
entry_logs = list(map(int, input().split()))
emps = [0 for i in range(2*(10**5))]
max_people, people = 0, 0
for i in range(length):
if emps[entry_logs[i]]:
people -= 1
emps[entry_logs[i]] = 0
else:
people += 1
emps[entry_logs[i]] = 1
if people>max_people:
max_people = people
print(max_people)