Max Count of Pairs into Table

Problem

Codeforces Contest Round 1075 Div 2 A. https://codeforces.com/contest/2189/problem/A

First approach

asked to maximize occurring freq of pairs selected from an input array

could use a map to determine all possible pairs select k pairs (n / 2) that will add 1 to the table

not a dp problem bc as long as pair coordinates go into the grid, it will add a constant factor of 1

issues: $O(n^2)$ map build time

Second Approach

Map is overkill can just loop $O(n)$ from the start

i tried to form pairs and increment that way by traversing but instead can just look through and find 2k ⇐ n elements that would fit in the table, and then return k

using three vector subarrays to classify the n elements (can probably improve space optimization) into 3 cats - fit row, fit col, or fit both then traverse through fit both and fill row and col cats return minimum between row and col vectors (the num of pairs)