Competitive Programming Guide - Searching and Sorting #1

I didn't discuss running time during the video, so let me do it here. Because N is up to 200,000, an O(N^2) solution would be too slow. The two solutions I showed in the video are both O(N log N).

An example of a solution that would be too slow is a "manually implemented" set, where you store a vector of "distinct numbers so far", and compare each element to each of the "distinct numbers so far" every time. In the worst case where all the numbers are distinct, you would end up comparing all pairs of numbers which is 20 billion comparisons, which is too slow.