Single Element in a Sorted Array

Share

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

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2
Input: nums = [3,3,7,7,10,11,11]
Output: 10
Constraints:

Contents

Solution 1 - Using binary search

As per the problem statement, every element in input array appeared twice except one element, that means the input array must be an odd length array, and this is the key to solve this problem. In this approach we will apply binary search algorithm to find that unique element.

We will create two pointers left and right to point to left and right end of array, then we will compute the mid index left + right /2, based on the element found at mid index, we can draw three conclusions.

  • Check if the element at mid index is not equal to its neighbours, then return the mid element.
  • If the mid element is not unique, that means either left neighbor or right neighbour element value also same, so after ignoring current b-v and one of its neighbour which has same value, get the reamining array length on left side and right sides, and one of these arrays must be odd length, because if every element appeared two times except one element, that side of array must be odd length.
  • If left side of array is odd length, then we will update right pointer to mid-1.
  • If right side of array is odd length, then we will update left pointer to mid+1.
Java
public class SingleElementInSortedArray {

    static int singleNonDuplicate(int[] nums) {

        int left = 0;
        int right = nums.length -1;

        while(left <= right) {
            int mid  = left + (right - left) /2;
            if((mid-1<0 || nums[mid] != nums[mid-1])
                    && (mid+1 == nums.length || nums[mid] != nums[mid+1])) {
                return nums[mid];
            }

            // Now, we need to decide which side of array to eliminate
            // if the current element duplicate is on left side or right, we will get remaining array sizes on left anf right sides
            // and check which side has odd length array, because if there is only one element appeared once, that side of array should be odd length

            int leftSideLength = mid;  // mid is already 0 indexed, from length wise it represents correct.
                                        //  assuming right side element to mid is same
            if(mid-1>=0 && nums[mid] == nums[mid-1]) { // if left side element and current are same
                leftSideLength = mid-1;
            }

           if(leftSideLength % 2 == 0) { // if left side array is odd length
               left = mid+1;
           } else {
               right = mid -1;
           }

        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(singleNonDuplicate(new int[]{1,1,2,3,3,4,4,8,8}));
        System.out.println(singleNonDuplicate(new int[]{3,3,7,7,10,11,11}));
        System.out.println(singleNonDuplicate(new int[]{1,2,2}));
        System.out.println(singleNonDuplicate(new int[]{1,1,2}));
    }
}
Complexity Analysis:

Time complexity: Above code runs in O(log n) time where n is the length of input array nums.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code