<p>Given an integer array <code>nums</code>, return <code>true</code> if any value appears <strong>at least twice</strong> in the array, and return <code>false</code> if every element is distinct.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>

<p><strong>Explanation:</strong></p>

<p>The element 1 occurs at the indices 0 and 3.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,2,3,4]</span></p>

<p><strong>Output:</strong> <span class="example-io">false</span></p>

<p><strong>Explanation:</strong></p>

<p>All elements are distinct.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,1,1,3,3,4,3,2,4,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">true</span></p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:

    def quickSort(self, arr: List[int]) -> List[int]:
        if len(arr) <= 1:
            return arr

        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]

        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]

        return self.quickSort(left) + middle + self.quickSort(right) 


    def containsDuplicate(self, nums: List[int]) -> bool:
        """
        1. Sort the array with QuickSort: O(NlogN)
        2. Iterate over the sorted array to find duplicates: O(n)
        """

        nums_size = len(nums)
        if nums_size == 1:
            return False

        sorted_nums = self.quickSort(nums)

        for index in range(1, nums_size):
            if sorted_nums[index] == sorted_nums[index - 1]:
                return True
            
        return False
29300