Marc Lester Tan

This medium problem can be solved easily by few lines of code with O(n) time complexity.

class Solution {
    fun singleNonDuplicate(nums: IntArray): Int {        
        var temp = nums.first()        
        (1 until nums.size).forEach {
            temp = temp xor nums[it]
        }
        
        return temp        
    }
}

Runtime: 232 ms, faster than 8.33% of Kotlin online submissions for Single Element in a Sorted Array.
Memory Usage: 37.7 MB, less than 100.00% of Kotlin online submissions for Single Element in a Sorted Array.

But the challenging part is this note:

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

So we can’t use the solution above and obviously we have to use binary search to get an O(log n) time complexity.

class Solution {
    fun singleNonDuplicate(nums: IntArray): Int {        
        var low = 0
        var high = nums.size - 1
        
        if(nums.size == 1) return nums[0]
        
        while(low < high){
            val mid = low + (high - low)/2
            if(mid > 0 && nums[mid - 1] != nums[mid] 
               && nums[mid] != nums[mid + 1]) return nums[mid]
            else if(mid == 0 && nums[mid] != nums[mid + 1]) return nums[mid]
            
            if(nums[mid] != nums[mid - 1]){
                if(mid % 2 == 0) low = mid + 1 else high = mid - 1
            }else if((mid + 1) % 2 == 0) low = mid + 1 else high = mid -1
        }
        
        return nums[low]
    }
}

Runtime: 200 ms, faster than 45.83% of Kotlin online submissions for Single Element in a Sorted Array.
Memory Usage: 35.8 MB, less than 100.00% of Kotlin online submissions for Single Element in a Sorted Array.