algoadvance

Leetcode 540. Single Element in a Sorted Array

Problem Statement

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.

Your solution should 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

Clarifying Questions

  1. Are the inputs always going to be valid sorted arrays following the given constraints?
    • Yes, assume the inputs are always valid as per the problem constraints.
  2. Is there a specific range for the elements within the array? Does it contain only integers?
    • The problem merely states integers without specific range bounds.
  3. Should we implement any specific error handling for inputs?
    • No need, assume inputs are valid according to the problem constraints.

Strategy

Given that the array is sorted and every element except one appears twice, a binary search approach can be utilized to achieve the O(log n) time complexity requirement. Here’s an approach to solve the problem:

  1. Binary Search Setup:
    • Define two pointers (left and right) to perform binary search on the array.
  2. Partition the Array:
    • Calculate the middle index of the current subarray.
    • Determine if the middle index is even or odd:
      • If mid is even, then the single element could be on the left side if the pair is broken at this point or to the right if the middle element continues the pattern of pairs.
      • If mid is odd, adjust the mid to check the element pairs correctly.
  3. Adjust the Search Range:
    • Depending on the comparison of mid element with its adjacent elements, adjust the left or right pointers to narrow down the area where the single element could be located.
  4. Stop Condition:
    • The loop continues until left is equal to right, at which point the position will be located at the single element.

Code

public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            // Ensure the mid is even for proper comparison with next element
            if (mid % 2 == 1) {
                mid--;
            }

            // Check if this breaks the pair property
            if (nums[mid] == nums[mid + 1]) {
                // Single element must be on the right side
                left = mid + 2;
            } else {
                // Single element must be on the left side
                right = mid;
            }
        }

        // left should be at the single element's position
        return nums[left];
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI