Given a list of integers, return the nth smallest integer in the list. **Only distinct elements should be considered** when calculating the answer. `n` will always be positive (`n > 0`)

If the nth small integer doesn't exist, return `-1` (C++) / `None` (Python) / `nil` (Ruby) / `null` (JavaScript).

Notes:
* "indexing" starts from 1
* huge lists (of 1 million elements) will be tested

## Examples

```python
nth_smallest([1, 3, 4, 5], 7)        ==> None  # n is more than the size of the list
nth_smallest([4, 3, 4, 5], 4)        ==> None  # 4th smallest integer doesn't exist
nth_smallest([45, -10, 4, 5, 4], 4)  ==> 45    # 4th smallest integer is 45
```

If you get a timeout, just try to resubmit your solution. However, if you ***always*** get a timeout, review your code.

Difficulty: introductory

Starter code:

def nth_smallest(arr, n):
	

Solutions:
def nth_smallest(arr, n):
    s = set(arr)
    return sorted(s)[n-1] if n<=len(s) else None

def nth_smallest(arr, n):
    try:
        return sorted(set(arr))[n-1]
    except:
        pass

import random

def partition(vector, left, right, pivotIndex):
    pivotValue = vector[pivotIndex]
    vector[pivotIndex], vector[right] = vector[right], vector[pivotIndex]  # Move pivot to end
    storeIndex = left
    for i in range(left, right):
        if vector[i] < pivotValue:
            vector[storeIndex], vector[i] = vector[i], vector[storeIndex]
            storeIndex += 1
    vector[right], vector[storeIndex] = vector[storeIndex], vector[right]  # Move pivot to its final place
    return storeIndex

def select(vector, left, right, k):
    "Returns the k-th smallest, (k >= 0), element of vector within vector[left:right+1] inclusive."
    if k < len(vector):
        while True:
            pivotIndex = random.randint(left, right)     # select pivotIndex between left and right
            pivotNewIndex = partition(vector, left, right, pivotIndex)
            pivotDist = pivotNewIndex - left
            if pivotDist == k:
                return vector[pivotNewIndex]
            elif k < pivotDist:
                right = pivotNewIndex - 1
            else:
                k -= pivotDist + 1
                left = pivotNewIndex + 1

def nth_smallest(arr, n):
    unique = list(set(arr))
    return select(unique, 0, len(unique)-1, n-1)

def nth_smallest(arr,k):
   
    if len(set(arr)) == 1:
        return arr[0]
    else:
        if len(set(arr)) < k:
            return None

    pivot = arr[0]
    lesser = list(set([x for x in arr[1:] if x < pivot]))
    greater = list(set([x for x in arr[1:] if x > pivot]))

    if len(lesser) >= k:
        return nth_smallest(lesser,k)
    
    elif len(lesser) == k-1:
        return pivot
    
    else:
        return nth_smallest(greater, k-len(lesser)-1)


def nth_smallest(arr, n):
    s = set(arr)
    return None if len(s) < n else sorted(s)[n-1]

def nth_smallest(arr, n):
    s = set(arr)
    if n <= len(s):
        return sorted(s)[n-1]

from heapq import *
def nth_smallest(arr, n):
    arr = list(set(arr))
    heapify(arr)

    if n > len(arr):
        return None

    x = 0
    for i in range(n):
        x = heappop(arr)
    return x

def nth_smallest(arr, n):
    x = list(dict.fromkeys(arr))
    x.sort(key=int)
    return None if n > len(x) else x[n-1]

nth_smallest = lambda a,n: None if len(set(a))<n else list(sorted(set(a)))[n-1]

def nth_smallest(arr, n):
    sorted_arr = sorted(set(arr))
    if n <= len(sorted_arr):
        return sorted_arr[n - 1]

def nth_smallest(arr, n):
    arr=sorted(list(set(arr)))
    if n > len(arr):
        return None
    return arr[n-1]