May 13, 2020

Description:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.

 

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

 

Note: Your solution should run in O(log n) time and O(1) space.

 

Solution:

# https://leetcode.com/problems/single-element-in-a-sorted-array/

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        size = len(nums)
        if (not size):
            return None
        start = 0
        end = size
        mid = (end - start) // 2
        
        # Iterate until the condition fails
        while (start <= mid < end):
            # number of elements in the array after mid element
            right_chunk_size = end - mid - 1
            if (mid + 1 < size and nums[mid] == nums[mid + 1]):
                # if mid and mid+1 elements are same and
                # even num of elements present after mid point
                # then non-duplicate is present in right half
                if (right_chunk_size % 2 == 0):
                    start = mid + 2
                else:
                    end = mid
                    
            elif (mid - 1 >= 0 and nums[mid] == nums[mid - 1]):
                # if mid and mid-1 elements are same and
                # even num of elements are present right side of mid
                # then non-duplicate element is on the left of mid
                if (right_chunk_size % 2 == 0):
                    end = mid - 1
                else:
                    start = mid + 1
                    
            else:
                return nums[mid]

            mid = start + (end - start) // 2

        # Only single element is remaining
        return nums[start]

 

Explanation:

When ever we're given a problem with 'searching' , 'sorted array' and 'O(log n) complexity' we can go for binary search algorithm with eyes closed. There is a slight difference in the given problem compared to the classic binary search. Instead of searching for a given element, we've to find the element that appears exactly once where every other element appears twice. This clearly shows that the array size should be odd.

The strategy that I've followed is, get the middle element of the array and compare it with it's neighbours (right element and left element). If any one of them is same as middle elements then based on the size of the right/left half of the array decide whether we've to go for the left half or right half in the next iteration.

  • Step 1: Find middle element.
  • Step 2: Compare with left and right elements to it.
    • if (nums[mid] == nums[mid - 1])
      • Check the size of right half of the array is even/odd
      • If the size is even proceed with the search on left half of the array
      • else, proceed with the search on right half of the array
      • eg. [1,1,2,3,3,4,4,8,8], here right half size is even so we repeat the process on the left half.
    • if (nums[mid] == nums[mid + 1])
      • Check the size of right half of the array is even/odd
      • If the size is even proceed with the search on right half of the array
      • else, proceed with the search on left half of the array
      • eg. [1,1,2,2,3,3,4,8,8], here right half size is even so we repeat the process on the right half.
    • else, return the middle element.

 

Evaluation: