---
# System prepended metadata

title: '#array 13'
tags: [Medium, Array]

---

# #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
```javascript
nums = [1,3,4,2,2]
```

### Sample Output
```javascript
2
```

<br>

<hr/>

## Solutions

### Official 
```javascript=

```
<br>

---

### Everyone's

:::spoiler YC
```javascript=
/*
  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
```javascript=
/*
  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 東
```javascript=
// 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];
}
```

```javascript=
// 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;
}
```

```javascript=
// 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
```javascript=
/**
 * 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)  |