This algorithm finds the single non-duplicate element in a sorted array where every other element appears exactly twice.
Steps
- Use binary search between left (
l) and right (r) - At each mid (
m): - If
arr[m] === arr[m - 1], count elements on the left - If that count is odd → single lies left →
r = m - 2 - If count is even → single lies right →
l = m + 1 - Same logic applies if
arr[m] === arr[m + 1] - If neither left nor right match → return
arr[m]
Dry Run
Input: [1,1,2,3,3,4,4,5,5,8,8] → Output: 2
Input: [3,3,7,7,10,11,11] → Output: 10
Time & Space Complexity
- Time: O(log n)
- Space: O(1)
var singleNonDuplicate = function(arr) {
let l = 0;
let r = arr.length - 1;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (arr[m] === arr[m - 1]) {
let leftCount = m - l;
if (leftCount % 2 === 1) {
r = m - 2;
} else {
l = m + 1;
}
} else if (arr[m] === arr[m + 1]) {
let leftCount = m - l;
if (leftCount % 2 === 1) {
r = m - 1;
} else {
l = m + 2;
}
} else {
return arr[m];
}
}
return arr[l];
};
int singleNonDuplicate(vector& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] == arr[m - 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 2;
else
l = m + 1;
} else if (arr[m] == arr[m + 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 1;
else
l = m + 2;
} else {
return arr[m];
}
}
return arr[l];
}
int singleNonDuplicate(int* arr, int arrSize) {
int l = 0, r = arrSize - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] == arr[m - 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 2;
else
l = m + 1;
} else if (arr[m] == arr[m + 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 1;
else
l = m + 2;
} else {
return arr[m];
}
}
return arr[l];
}
public int singleNonDuplicate(int[] arr) {
int l = 0, r = arr.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (m > 0 && arr[m] == arr[m - 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 2;
else
l = m + 1;
} else if (m < arr.length - 1 && arr[m] == arr[m + 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 1;
else
l = m + 2;
} else {
return arr[m];
}
}
return arr[l];
}
def singleNonDuplicate(arr):
l, r = 0, len(arr) - 1
while l < r:
m = l + (r - l) // 2
if arr[m] == arr[m - 1]:
leftCount = m - l
if leftCount % 2 == 1:
r = m - 2
else:
l = m + 1
elif arr[m] == arr[m + 1]:
leftCount = m - l
if leftCount % 2 == 1:
r = m - 1
else:
l = m + 2
else:
return arr[m]
return arr[l]
public int SingleNonDuplicate(int[] arr) {
int l = 0, r = arr.Length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (arr[m] == arr[m - 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 2;
else
l = m + 1;
} else if (arr[m] == arr[m + 1]) {
int leftCount = m - l;
if (leftCount % 2 == 1)
r = m - 1;
else
l = m + 2;
} else {
return arr[m];
}
}
return arr[l];
}
