Encuentra un duplicado en una matriz de enteros

Esta fue una pregunta de entrevista.

Me dieron una serie den+1 enteros del rango[1,n]. La propiedad de la matriz es que tienek (k>=1) duplicados, y cada duplicado puede aparecer más de dos veces. La tarea consistía en encontrar un elemento de la matriz que ocurriera más de una vez en la mejor complejidad de tiempo y espacio posible.

Después de una lucha significativa, orgullosamente se me ocurrióO(nlogn) solución que llevaO(1) espacio. Mi idea era dividir el rango.[1,n-1] en dos mitades y determinar cuál de las dos mitades contiene más elementos de la matriz de entrada (estaba usando el principio de Pigeonhole). El algoritmo continúa de forma recursiva hasta que alcanza el intervalo.[X,X] dóndeX ocurre dos veces y eso es un duplicado.

El entrevistador estaba satisfecho, pero luego me dijo que existeO(n) solución con espacio constante. Él generosamente ofreció algunas pistas (¿algo relacionado con las permutaciones?), Pero no tenía idea de cómo llegar a tal solución. Suponiendo que no estaba mintiendo, ¿alguien puede ofrecer pautas? He buscado SO y he encontrado pocas variaciones (más fáciles) de este problema, pero no esta específica. Gracias.

EDITAR: para complicar aún más las cosas, el entrevistador mencionó que la matriz de entrada no debe modificarse.