Константа во всем: одна простая задача за O(1)

Тоже решал это на литкоде. В целом, задача сводится к поиску пары, при распределении чисел у нас есть всего несколько вариантов:

• Элемент повторяется один за другим [1,2,3,3]

• Рядом стоят не повторяющиеся элементы

  • [1,3,2,3]

  • [3,1,2,3]

  • [3,1,3,2]

С первым случаем все понятно, сравниваем пары чисел и если одинаковые - выходим. Дальше идут два случая, когда повторяющийся элемент последний. И последний случай - это когда наш искомый элемент предпоследний.

def repeatedNTimes(nums: List[int]) -> int:
    prev = last = nums.pop()
    for cur in nums:
        if cur == prev or cur == last:
            return cur
        else:
            prev = cur
    return prev

Здесь cur == prev это проверка на повторяющиеся подряд, cur == last проверяем, что повторяющийся элемент последний и return prev как наш последний вариант, когда повторяющийся элемент предпоследний.

Можно было тоже самое считать с первыми элементами, но с последними мне показалось проще.