# #array 13

###### tags:`Array` `Medium`

## Problem
[leetcode 287]
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.

==You must solve the problem without modifying the array nums and uses only constant extra space.==

### Sample Input

nums = [1,3,4,2,2]

### Sample Output

2

<br>

<hr/>

## Solutions

### Official

<br>

---

### Everyone's

:::spoiler YC

/*
  time: O(n) - where n is the length of the given array
  space: O(1)
*/
function firstDuplicateValue(array) {
  const record = new Array(array.length).fill(false);
  for(let i = 0; i < array.length; i++){
    const num = array[i]
    const index = array[i] - 1;
    if(record[index]){
      return num;
    }
    else{
      record[index] = true;
    }
  }
  return -1;
}

:::

<br>

:::spoiler 月
- Negative Marking

/*
  time: O(n), space: O(1)
  n is the length of array.
*/
var findDuplicate = function(array) {
    for(let i = 0; i < array.length; i+=1){
        const x = Math.abs(array[i]);
        if(array[x] < 0) return x;
        array[x] = -array[x];
    }
    return -1
};

:::

<br>

:::spoiler 東

// Time O(n^2) | Space O(1) - n is the length of input array
function firstDuplicateValue(array) {
  let minIdx = array.length;
  for(let i = 0; i < array.length; i++){
    for(let j = i + 1; j < array.length; j++){
      if(array[i] === array[j] && j < minIdx) minIdx = j;
    }
  }
  return minIdx === array.length ? -1 : array[minIdx];
}

// Time O(n) | Space O(n) - n is the length of input array
function firstDuplicateValue(array) {
  const map = {};
  for(const num of array){
    if(map[num]){
      return num;
    }
    map[num] = true;
  }
  return -1;
}

// Time O(n) | Space O(1) - n is the length of input array
function firstDuplicateValue(array) {
  for(const num of array) {
    if(array[Math.abs(num) - 1] < 0) return Math.abs(num);
    array[Math.abs(num) - 1] *= -1;
  }
  return -1;
}

:::

<br>

:::spoiler Hao

/**
 * Time complexity: O(n) where n stands for array.length
 * Space complexity: O(1)
 */

function firstDuplicateValue(array) {
    let res = -1;
    const values = {};

    for (let i = 0; i < array.length; i += 1) {
        const cur = array[i];

        if (values[cur] === undefined) values[cur] = true;
        else {
            res = cur;
            break;
        }
    }

    return res;
}

:::

<br>

<br>

---

## Supplement / Discussion

https://leetcode.com/problems/find-the-duplicate-number/solutions/127594/find-the-duplicate-number/

| solution | time | space |
| ------------------ | -------- | ----- |
| sort | O(nlogn) | O(1) |
| hash map | O(n) | O(n) |
| marking | O(n) | O(1) |
| binary search | O(nlogn) | O(1) |
| linked list cycle | O(n) | O(1) |
| Bit by bit | O(nlogn) | O(1) |