<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 containsDuplicate(self, nums: List[int]) -> bool:
         i = 1
         for num in nums:
            for num1 in nums[i:]:
                if (num == num1):
                    return True
            i = i + 1
         return False
'''


class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        arr = nums
        
        #MergeSort
        def merge_sort(arr):
            if len(arr) <= 1:
                return arr
    
            # Step 1: Divide the array into two halves
            mid = len(arr) // 2
            left_half = merge_sort(arr[:mid])
            right_half = merge_sort(arr[mid:])
    
            # Step 2: Conquer by merging the sorted halves
            return merge(left_half, right_half)

        def merge(left, right):
            sorted_array = []
            i = j = 0
    
            # Step 3: Merge the two halves
            while i < len(left) and j < len(right):
                if left[i] < right[j]:
                    sorted_array.append(left[i])
                    i += 1
                else:
                    sorted_array.append(right[j])
                    j += 1
   
            # Append any remaining elements
            sorted_array.extend(left[i:])
            sorted_array.extend(right[j:])
    
            return sorted_array

        sorted_arr = merge_sort(arr)
        print(sorted_arr)

        #Check neighbor
        i = 1
        for num in sorted_arr[:len(sorted_arr)-1]:
            if (num == sorted_arr[i]):
                return True
            if(i < len(sorted_arr)-1):
                i += 1
        return False



'''
class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        duplicate_arr = []
        for num in nums:
            if num not in duplicate_arr:
                duplicate_arr.append(num)
            else:
                return True
        return False
'''
29700