## 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.