class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        if(!n) return -1;
        for(auto x:nums)
            if(x < 0 || x >= n) return -1;
        for(int i = 0; i < n;++i){
            while(nums[i] != i && nums[i] != nums[nums[i]]) swap(nums[nums[i]],nums[i]);
            if(nums[i] != i) return nums[i];
        }
        return -1;

        /*int n = nums.size();
        if(!n) return -1;
        for(auto x:nums)
            if(x < 0 || x >= n) return -1;

        unordered_map<int,int> cnt;
        for(int i = 0;i < n;++i){
            cnt[nums[i]]++;
            if(cnt[nums[i]] > 1) return nums[i];
        }
        return -1;*/
    }
};