Jobs

Interviews

Discussions

Single Element in a Sorted Array

Medium

Zomato

3 views

Topics:

ArraysBinary Search

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:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Single Element in a Sorted Array

Medium

Zomato

3 views

Topics:

ArraysBinary Search

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:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the array?
Is the input array guaranteed to always have an odd number of elements and a single unique element?
Can the input array be empty or null? If so, what should I return?
Are all elements guaranteed to appear exactly twice, *except* for the single element? Or could other elements appear a different number of times?
Is the input *strictly* sorted in non-decreasing order? Could there be unsorted sections?

Brute Force Solution

Approach

The goal is to find the single number that appears only once in a sorted list where every other number appears exactly twice. The brute force strategy involves checking each number individually to see if it's the unique one.

Here's how the algorithm would work step-by-step:

Start by looking at the very first number in the list.
Compare it to the number right next to it.
If they are different, the first number is the one we're looking for, so we're done.
If they are the same, move to the third number (skip the second since we already checked it).
Repeat the comparison process: compare this number to the number next to it.
Keep doing this, jumping ahead two numbers each time, until you find a number that is different from the one following it.
That unique number is the answer.

Code Implementation

def single_non_duplicate(numbers):
    list_length = len(numbers)
    index = 0

    while index < list_length - 1:
        # Check if current element is different from the next.
        if numbers[index] != numbers[index + 1]:
            return numbers[index]

        # Skip the next element since it's a duplicate.
        index += 2

    # If the unique element is at the end of the list.
    return numbers[list_length - 1]

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through the input array of size n, comparing each element with its neighbor. The loop increments by two in each step, effectively processing n/2 elements in the worst case. Thus, the time complexity is directly proportional to the input size n, resulting in a linear time complexity.

Space Complexity

O(1) – The algorithm described iterates through the array using a loop, comparing adjacent elements. It does not create any auxiliary data structures like lists, hash maps, or sets. The only extra space used is for a few variables to keep track of the current position during the iteration. Since the number of variables remains constant regardless of the input array size N, the space complexity is O(1).

Optimal Solution

Approach

The key to solving this efficiently lies in recognizing the sorted nature of the list. Instead of checking each number individually, we can use a divide-and-conquer approach to quickly narrow down the search to the unique element.

Here's how the algorithm would work step-by-step:

Think of the list as being split into two halves. The unique number will be on one side of the middle.
Check if the middle number is the same as the number next to it. This tells you if the unique number is before or after this middle section.
If the number is the same as its neighbor, the unique number is on the other half of this section. Discard this half.
Keep splitting the remaining half and checking the middle number until you are left with only one number, which must be the unique one.

Code Implementation

def find_single_element(numbers):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Ensure middle_index is even to compare pairs correctly.
        if middle_index % 2 != 0:
            middle_index -= 1

        # Unique element is in the right half.
        if numbers[middle_index] != numbers[middle_index + 1]:

            right_index = middle_index

        # Unique element is in the left half.
        else:

            left_index = middle_index + 2

    return numbers[left_index]

Big(O) Analysis

Time Complexity

O(log n) – The provided solution utilizes a divide-and-conquer approach similar to binary search. In each step, the search space is halved by checking the middle element. The cost is driven by repeatedly dividing the input array of size n. Therefore, the number of operations grows logarithmically with the input size, resulting in a time complexity of O(log n).

Space Complexity

O(log N) – The provided solution uses a divide-and-conquer approach, which is typically implemented recursively or iteratively with a stack. In the worst-case scenario, where the single element is located at the extreme end of the array, the recursion depth will be proportional to the number of times the array is halved, resulting in a maximum call stack depth of log N, where N is the size of the input array. Each recursive call adds a new frame to the call stack, thus the auxiliary space used is proportional to the call stack depth. Therefore, the space complexity is O(log N).

Edge Cases

Case	How to Handle
Null or empty array	Return an appropriate error value (e.g., -1) or throw an exception indicating invalid input.
Array with only one element	Return the single element directly as it must be the unique element.
Array with only two elements (both different)	Return the first element since only one unique element can exist, and the array cannot be valid according to the problem description.
Single element at the beginning of the array	The binary search condition needs to handle the boundary condition where the single element is at index 0.
Single element at the end of the array	The binary search condition needs to handle the boundary condition where the single element is at the last index.
Array with all elements being the same except for one at either end	Binary search needs to correctly narrow the search space when encountering long sequences of the same number.
Large input array to test for performance (time complexity)	Binary search ensures logarithmic time complexity, even for large arrays.
Integer overflow when calculating mid in binary search	Calculate mid as low + (high - low) / 2 to prevent potential integer overflow.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the array?
Is the input array guaranteed to always have an odd number of elements and a single unique element?
Can the input array be empty or null? If so, what should I return?
Are all elements guaranteed to appear exactly twice, *except* for the single element? Or could other elements appear a different number of times?
Is the input *strictly* sorted in non-decreasing order? Could there be unsorted sections?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the very first number in the list.
Compare it to the number right next to it.
If they are different, the first number is the one we're looking for, so we're done.
If they are the same, move to the third number (skip the second since we already checked it).
Repeat the comparison process: compare this number to the number next to it.
Keep doing this, jumping ahead two numbers each time, until you find a number that is different from the one following it.
That unique number is the answer.

Code Implementation

def single_non_duplicate(numbers):
    list_length = len(numbers)
    index = 0

    while index < list_length - 1:
        # Check if current element is different from the next.
        if numbers[index] != numbers[index + 1]:
            return numbers[index]

        # Skip the next element since it's a duplicate.
        index += 2

    # If the unique element is at the end of the list.
    return numbers[list_length - 1]

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Think of the list as being split into two halves. The unique number will be on one side of the middle.
Check if the middle number is the same as the number next to it. This tells you if the unique number is before or after this middle section.
If the number is the same as its neighbor, the unique number is on the other half of this section. Discard this half.
Keep splitting the remaining half and checking the middle number until you are left with only one number, which must be the unique one.

Code Implementation

def find_single_element(numbers):
    left_index = 0
    right_index = len(numbers) - 1

    while left_index < right_index:
        middle_index = (left_index + right_index) // 2

        # Ensure middle_index is even to compare pairs correctly.
        if middle_index % 2 != 0:
            middle_index -= 1

        # Unique element is in the right half.
        if numbers[middle_index] != numbers[middle_index + 1]:

            right_index = middle_index

        # Unique element is in the left half.
        else:

            left_index = middle_index + 2

    return numbers[left_index]

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty array	Return an appropriate error value (e.g., -1) or throw an exception indicating invalid input.
Array with only one element	Return the single element directly as it must be the unique element.
Array with only two elements (both different)	Return the first element since only one unique element can exist, and the array cannot be valid according to the problem description.
Single element at the beginning of the array	The binary search condition needs to handle the boundary condition where the single element is at index 0.
Single element at the end of the array	The binary search condition needs to handle the boundary condition where the single element is at the last index.
Array with all elements being the same except for one at either end	Binary search needs to correctly narrow the search space when encountering long sequences of the same number.
Large input array to test for performance (time complexity)	Binary search ensures logarithmic time complexity, even for large arrays.
Integer overflow when calculating mid in binary search	Calculate mid as low + (high - low) / 2 to prevent potential integer overflow.