LeetCode 540: Single Element in a Sorted Array
LeetCode 540 Solution 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,
lowandhigh, 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
midis even andmid + 1element is equal tomidelement, then the single element is on the right side, so we movelowtomid + 2. - If
midis odd andmid - 1element is equal tomidelement, then the single element is on the right side, so we movelowtomid + 1. - Otherwise, the single element is on the left side, so we move
hightomid - 1.
- If
- Repeat the above steps until
lowandhighconverge, then return the element atlow.
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.
LeetCode 540 Solutions in Java, C++, Python
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];
}
}Interactive Code Editor for LeetCode 540
Improve Your LeetCode 540 Solution
Use the editor below to refine the provided solution for LeetCode 540. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...