$T(n) = O(nlogn), S(n) = O(1)$

class Solution {
    public int duplicateInArray(int[] nums) {
        int l = 1, r = nums.length - 1;

        while (l < r) {
            int mid = l + r >> 1;
            int count = 0;

            for (int num : nums) {
                if (num >= l && num <= mid) {
                    count++;
                }
            }

            if (count > mid - l + 1) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }

        return r;
    }
}