540: Time 93.53%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n- Initialize two pointers left and right to point to the first and last e
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n- Initialize two pointers left and right to point to the first and last element of the array respectively.\n- Implement binary search until left and right point to the same element.\n- Compute the mid index as the average of left and right.\n- Check if the element at the mid index is the single element.\n- If the element at the mid index is not equal to the elements adjacent to it, return it as the single element.\n- Check if the single element is on the left side of the array.\n- If the element at mid is equal to the element at mid-1, then the single element is on the left side.\n- Compute the distance between left and mid and check if it is even or odd.\n- If it is even, then the single element is to the left of mid. Update right to mid-2.1\n- If it is odd, then the single element is to the right of mid. Update left to mid+1.\n- Check if the single element is on the right side of the array.\n- If the element at mid is equal to the element at mid+1, then the single element is on the right side.\n- Compute the distance between mid and right and check if it is even or odd.\n- If it is even, then the single element is to the right of mid. Update left to mid+2.\n- If it is odd, then the single element is to the left of mid. Update right to mid-1.\n- If we reach here, the single element is at the left index. Return it.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def singleNonDuplicate(self, nums: List[int]) -> int:\n        # Initialize pointers\n        left, right = 0, len(nums) - 1\n        \n        # Binary search\n        while left < right:\n            mid = (left + right) // 2\n            \n            # Check if mid is the single element\n            if nums[mid] != nums[mid-1] and nums[mid] != nums[mid+1]:\n                return nums[mid]\n            \n            # Check if the single element is on the left side\n            if nums[mid] == nums[mid-1]:\n                if (mid - left) % 2 == 0:\n                    right = mid - 2\n                else:\n                    left = mid + 1\n            \n            # Check if the single element is on the right side\n            elif nums[mid] == nums[mid+1]:\n                if (right - mid) % 2 == 0:\n                    left = mid + 2\n                else:\n                    right = mid - 1\n        \n        # If we reach here, the single element is at the last index\n        return nums[left]\n\n```
['Array', 'Binary Search', 'Python', 'Python3']