Solution
Approach 1: Count
Intuition and Algorithm
Let's count the number of elements. We can use a HashMap
or an array  here, we use a HashMap
.
After, the element with a count larger than 1 must be the answer.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Approach 2: Compare
Intuition and Algorithm
If we ever find a repeated element, it must be the answer. Let's call this answer the major element.
Consider all subarrays of length 4. There must be a major element in at least one such subarray.
This is because either:
 There is a major element in a length 2 subarray, or;
 Every length 2 subarray has exactly 1 major element, which means that a length 4 subarray that begins at a major element will have 2 major elements.
Thus, we only have to compare elements with their neighbors that are distance 1, 2, or 3 away.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.