Thinking process

since I can't use extra space and the runtime complexity should be less than quadratic, what can I do?

• faster than quadratic, binary search OR divide and conquer

I am given a range,

• Maybe I can do binary search with search space is a range

What I can do with the median? Can I find something to reduce the range?

• count all the numbers in input that are smaller or equal to the median
• if the count is more than median, then the duplicates should be in the range [1, median]

Time Complexity

O(n log n)

public class Solution {
    private int count (int mid, int[] nums) {
        int total = 0;

        for (int i : nums) {
            if (i <= mid) {
                total++;
            }
        }

        return total;
    }

    public int findDuplicate(int[] nums) {
        if (nums.length == 0) return 0;

        int left = 1;
        int right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (count(mid, nums) > mid) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (count(left, nums) > left) {
            return left;
        }

        return right;
    }
}