Single Element In Sorted Array

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.

Source

package questions


import _utils.UseCommentAsDocumentation
import utils.shouldBe

/**
 * 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.
 *
 * [Source](https://leetcode.com/problems/single-element-in-a-sorted-array/)
 */
@UseCommentAsDocumentation
private fun singleNonDuplicate(nums: IntArray): Int {

    /**
     * Theorem:
     *
     * If no single element exists till index i such that nums[i] == nums[i + 1], then i must be even.
     * i.e. starting index must always be even.
     *
     *  0  1   2   3   4   5   6   7   8
     * _________________________________
     *  1  1   2   2   3   3   4   4  (5)
     * (1) 2   2   3   3   4   4   5   5
     * 
     * Using this fact, do binary search
     */
    fun findSingleNonDuplicate(low: Int, high: Int): Int {
        if (high == low && high > nums.lastIndex) {
            return nums.last()
        }
        if (low < 0) {
            return nums.first()
        }
        val midIndex = (low + high) / 2
        val rightElemIndex = midIndex + 1
        val leftElemIndex = midIndex - 1
        if (nums[midIndex] == nums.getOrNull(rightElemIndex)) { // is mid == right element?
            val startingIndex = midIndex // if yes, mid is the starting element
            if (startingIndex % 2 == 0) { // if mid is even, then single element is at its right
                return findSingleNonDuplicate(startingIndex + 2, high)
            } else {
                return findSingleNonDuplicate(low, startingIndex - 1) // else at its left
            }
        } else if (nums.getOrNull(leftElemIndex) == nums[midIndex]) { // if left is the starting index
            val startingIndex = leftElemIndex
            if (startingIndex % 2 == 0) { // is starting index even?
                return findSingleNonDuplicate(startingIndex + 2, high) // if yes, then no single element at left
            } else {
                return findSingleNonDuplicate(low, startingIndex - 1) // single element must exists at left
            }
        } else {
            return nums[midIndex] // found the single element
        }
    }
    return findSingleNonDuplicate(0, nums.size)
}


fun main() {
    singleNonDuplicate(nums = intArrayOf(1, 1, 2, 2, 3, 3, 4, 4, 5)) shouldBe 5
    singleNonDuplicate(nums = intArrayOf(3, 3, 7, 7, 10, 11, 11)) shouldBe 10

    singleNonDuplicate(nums = intArrayOf(1, 1, 2, 3, 3, 4, 4, 8, 8)) shouldBe 2
    singleNonDuplicate(nums = intArrayOf(3, 3, 7, 10, 10, 11, 11)) shouldBe 7
    singleNonDuplicate(nums = intArrayOf(3, 3, 7, 7, 10, 10, 11, 11, 12)) shouldBe 12
    singleNonDuplicate(nums = intArrayOf(1, 3, 3, 7, 7, 10, 10, 11, 11)) shouldBe 1
}

---

View on GitHub

Updated on 2021-11-21