LeetCode 540: Single Element in a Sorted Array Solution

Master LeetCode problem 540 (Single Element in a Sorted Array), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

540. Single Element in a Sorted Array

Medium

Array Binary Search

Problem Explanation

Explanation

To find the single element in a sorted array with elements appearing twice except for one element, we can utilize the property of the array being sorted. We can perform a binary search to efficiently find the single element.

We start by initializing two pointers, low and high, to the beginning and end of the array respectively.
We calculate the middle index mid.
We check if the middle element is the single element or if it is on the left or right side.
If the middle element is not the single element, we check if the single element lies on the left or right side based on the following conditions:
- If mid is even and mid + 1 element is equal to mid element, then the single element is on the right side, so we move low to mid + 2.
- If mid is odd and mid - 1 element is equal to mid element, then the single element is on the right side, so we move low to mid + 1.
- Otherwise, the single element is on the left side, so we move high to mid - 1.
Repeat the above steps until low and high converge, then return the element at low.

The time complexity of this approach is O(log n) as we are reducing the search space by half in each iteration, and the space complexity is O(1) as we are using constant space.

Solution Code

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (mid % 2 == 1) {
                mid--; // Ensure mid is always on even index
            }
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 540 (Single Element in a Sorted Array)?

This page provides optimized solutions for LeetCode problem 540 (Single Element in a Sorted Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 540 (Single Element in a Sorted Array)?

The time complexity for LeetCode 540 (Single Element in a Sorted Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 540 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 540 in Java, C++, or Python.

Back to LeetCode Solutions