Single Element in Sorted Array

🎯

Single Element in Sorted Array

mediumBINARY_SEARCHAmazonFacebookGoogle

Imagine you have a sorted list of product IDs where every product appears exactly twice except one unique product that appears only once. You want to find that unique product efficiently.

💡 This problem is a classic example of using binary search in a modified way. Beginners often struggle because the array is sorted but the uniqueness condition breaks the usual binary search assumptions. Understanding how to leverage the parity of indices and pairs is key.

📋

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 must run in O(log n) time and O(1) space. Input: A sorted integer array nums. Output: The single element that appears only once.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^9nums is sorted in ascending orderEvery element appears exactly twice except for one element which appears once

💡

Example

Input"[1,1,2,3,3,4,4,8,8]"

Output2

All elements except 2 appear twice. 2 is the single element.

Input"[3,3,7,7,10,11,11]"

Output10

10 is the only element that appears once.

• Single element array [5] → 5
• Single element at the start [2,3,3,4,4] → 2
• Single element at the end [1,1,2,2,3] → 3
• Large array with single element in the middle

⚠️

Common Mistakes

Not handling the last element correctly in brute force

May cause index out of range error or miss the single element at the end

✅ Add a return statement for the last element after loop ends

Using mid without floor division in languages like Python 3

mid becomes float causing index errors

✅ Use integer division (//) to get integer mid index

Incorrect parity check logic (confusing even and odd cases)

Binary search may discard wrong half, leading to wrong answer or infinite loop

✅ Carefully implement parity logic as per the problem's pairing pattern

Not updating low or high correctly after comparisons

Infinite loop or missing the single element

✅ Ensure low and high pointers move correctly to shrink search space

Assuming XOR approach is always allowed without clarifying constraints

May lose points if interviewer expects parity-based solution

✅ Ask interviewer if XOR is allowed or preferred before using it

🧠

Brute Force (Linear Scan)

💡 This approach exists to establish a baseline and confirm understanding of the problem. It is simple but inefficient, helping beginners grasp the problem before optimizing.

Intuition

Since every element except one appears twice, scanning the array and checking neighbors will reveal the single element by finding the one that doesn't have a duplicate adjacent to it.

Algorithm

1. Iterate through the array from start to end.
2. For each element, check if it is equal to the next element.
3. If equal, skip the next element as it forms a pair.
4. If not equal, return the current element as the single element.

💡 The challenge is to carefully check pairs and handle the last element without going out of bounds.

</>

Code

def singleNonDuplicate(nums):
    n = len(nums)
    i = 0
    while i < n - 1:
        if nums[i] != nums[i + 1]:
            return nums[i]
        i += 2
    return nums[-1]

# Driver code
if __name__ == "__main__":
    print(singleNonDuplicate([1,1,2,3,3,4,4,8,8]))  # Output: 2

Line Notes

n = len(nums)Store length to avoid repeated calls

while i < n - 1Loop until second last element to safely check pairs

if nums[i] != nums[i + 1]Check if current element is not paired with next

return nums[-1]If no mismatch found, last element is single

public class Solution {
    public static int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int i = 0;
        while (i < n - 1) {
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
            i += 2;
        }
        return nums[n - 1];
    }

    public static void main(String[] args) {
        int[] nums = {1,1,2,3,3,4,4,8,8};
        System.out.println(singleNonDuplicate(nums)); // Output: 2
    }
}

Line Notes

int n = nums.length;Cache array length for efficiency

while (i < n - 1)Loop until second last index to check pairs

if (nums[i] != nums[i + 1])Detect unpaired element by mismatch

return nums[n - 1];Return last element if no mismatch found

#include <iostream>
#include <vector>
using namespace std;

int singleNonDuplicate(vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n - 1) {
        if (nums[i] != nums[i + 1]) {
            return nums[i];
        }
        i += 2;
    }
    return nums[n - 1];
}

int main() {
    vector<int> nums = {1,1,2,3,3,4,4,8,8};
    cout << singleNonDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int n = nums.size();Store size once for loop condition

while (i < n - 1)Loop to safely check pairs without overflow

if (nums[i] != nums[i + 1])Identify the single element by mismatch

return nums[n - 1];Return last element if no mismatch found

function singleNonDuplicate(nums) {
    const n = nums.length;
    let i = 0;
    while (i < n - 1) {
        if (nums[i] !== nums[i + 1]) {
            return nums[i];
        }
        i += 2;
    }
    return nums[n - 1];
}

// Test
console.log(singleNonDuplicate([1,1,2,3,3,4,4,8,8])); // Output: 2

Line Notes

const n = nums.length;Cache length for performance

while (i < n - 1)Loop until second last element to check pairs

if (nums[i] !== nums[i + 1])Check if current element is unpaired

return nums[n - 1];Return last element if no unpaired found earlier

⏱

Complexity

TimeO(n)

SpaceO(1)

We scan the array once, checking pairs, so time is linear. Space is constant as no extra data structures are used.

💡 For n=100,000 elements, this means 100,000 operations which is slow compared to logarithmic solutions.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large inputs. It is useful to show understanding before optimizing.

🧠

Binary Search Using Index Parity

💡 This approach introduces the key insight that pairs start at even indices before the single element and at odd indices after it. It leverages this to perform a binary search, reducing time complexity drastically.

Intuition

Because the array is sorted and pairs appear consecutively, the single element disrupts the pattern. By checking the parity of the mid index and comparing with neighbors, we can decide which half to discard.

Algorithm

1. Initialize low and high pointers at start and end of array.
2. While low < high, find mid index.
3. Check if mid is even or odd.
4. If mid is even and nums[mid] == nums[mid + 1], move low to mid + 2; else move high to mid.
5. If mid is odd and nums[mid] == nums[mid - 1], move low to mid + 1; else move high to mid - 1.
6. When low == high, return nums[low] as the single element.

💡 The parity check helps decide which half contains the single element, halving the search space each iteration.

</>

Code

def singleNonDuplicate(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if mid % 2 == 0:
            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid
        else:
            if nums[mid] == nums[mid - 1]:
                low = mid + 1
            else:
                high = mid - 1
    return nums[low]

# Driver code
if __name__ == "__main__":
    print(singleNonDuplicate([1,1,2,3,3,4,4,8,8]))  # Output: 2

Line Notes

low, high = 0, len(nums) - 1Initialize search boundaries

while low < high:Loop until search space reduces to one element

mid = (low + high) // 2Find middle index to check

if mid % 2 == 0:Check parity of mid to decide pairing logic

if nums[mid] == nums[mid + 1]:If pair is intact, single element is after mid

low = mid + 2Discard left half including mid and its pair

else: high = midSingle element is at mid or before

return nums[low]When low meets high, single element found

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

    public static void main(String[] args) {
        int[] nums = {1,1,2,3,3,4,4,8,8};
        System.out.println(singleNonDuplicate(nums)); // Output: 2
    }
}

Line Notes

int low = 0, high = nums.length - 1;Initialize binary search bounds

while (low < high)Continue until search space is one element

int mid = (low + high) / 2;Calculate middle index

if (mid % 2 == 0)Check if mid is even to apply pairing logic

if (nums[mid] == nums[mid + 1])If pair intact, single element is right

low = mid + 2;Discard left half including pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element found

#include <iostream>
#include <vector>
using namespace std;

int singleNonDuplicate(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (mid % 2 == 0) {
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (nums[mid] == nums[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return nums[low];
}

int main() {
    vector<int> nums = {1,1,2,3,3,4,4,8,8};
    cout << singleNonDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int low = 0, high = nums.size() - 1;Set initial binary search range

while (low < high)Loop until narrowed to one element

int mid = (low + high) / 2;Calculate midpoint index

if (mid % 2 == 0)Use parity to check pair alignment

if (nums[mid] == nums[mid + 1])If pair intact, single element is right

low = mid + 2;Move low pointer past the pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element found

function singleNonDuplicate(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (mid % 2 === 0) {
            if (nums[mid] === nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (nums[mid] === nums[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return nums[low];
}

// Test
console.log(singleNonDuplicate([1,1,2,3,3,4,4,8,8])); // Output: 2

Line Notes

let low = 0, high = nums.length - 1;Initialize binary search boundaries

while (low < high)Loop until search space is one element

let mid = Math.floor((low + high) / 2);Calculate midpoint index

if (mid % 2 === 0)Check parity of mid index

if (nums[mid] === nums[mid + 1])If pair intact, single element is right

low = mid + 2;Discard left half including pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element found

⏱

Complexity

TimeO(log n)

SpaceO(1)

Binary search halves the search space each iteration, leading to logarithmic time. Space is constant as no extra data structures are used.

💡 For n=100,000 elements, this means about 17 operations, which is extremely efficient.

Interview Verdict: Accepted and optimal

This is the preferred approach in interviews due to its efficiency and elegance.

🧠

Binary Search Without Using XOR (Parity Based Halving)

💡 This approach is a variant of the binary search that avoids using bitwise XOR operations, relying solely on parity checks and comparisons. It is useful when XOR is not allowed or to demonstrate understanding of parity-based logic.

Intuition

Pairs start at even indices before the single element and at odd indices after it. By comparing mid with its neighbor and checking parity, we decide which half to search next.

Algorithm

1. Set low and high pointers at array bounds.
2. While low < high, compute mid.
3. If mid is even, compare nums[mid] with nums[mid + 1].
4. If equal, move low to mid + 2; else move high to mid.
5. If mid is odd, compare nums[mid] with nums[mid - 1].
6. If equal, move low to mid + 1; else move high to mid - 1.
7. Return nums[low] when low == high.

💡 This method carefully uses parity and neighbor comparisons to halve the search space without XOR.

</>

Code

def singleNonDuplicate(nums):
    low, high = 0, len(nums) - 1
    while low < high:
        mid = (low + high) // 2
        if mid % 2 == 0:
            if nums[mid] == nums[mid + 1]:
                low = mid + 2
            else:
                high = mid
        else:
            if nums[mid] == nums[mid - 1]:
                low = mid + 1
            else:
                high = mid - 1
    return nums[low]

# Driver code
if __name__ == "__main__":
    print(singleNonDuplicate([1,1,2,3,3,4,4,8,8]))  # Output: 2

Line Notes

low, high = 0, len(nums) - 1Initialize binary search boundaries

while low < high:Loop until narrowed to one element

mid = (low + high) // 2Calculate midpoint index

if mid % 2 == 0:Check parity of mid index

if nums[mid] == nums[mid + 1]:If pair intact, single element is right

low = mid + 2Discard left half including pair

else: high = midSingle element is at or before mid

return nums[low]Return the single element found

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

    public static void main(String[] args) {
        int[] nums = {1,1,2,3,3,4,4,8,8};
        System.out.println(singleNonDuplicate(nums)); // Output: 2
    }
}

Line Notes

int low = 0, high = nums.length - 1;Initialize search boundaries

while (low < high)Loop until one element remains

int mid = (low + high) / 2;Calculate midpoint

if (mid % 2 == 0)Check parity of mid

if (nums[mid] == nums[mid + 1])If pair intact, single element is right

low = mid + 2;Discard left half including pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element

#include <iostream>
#include <vector>
using namespace std;

int singleNonDuplicate(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    while (low < high) {
        int mid = (low + high) / 2;
        if (mid % 2 == 0) {
            if (nums[mid] == nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (nums[mid] == nums[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return nums[low];
}

int main() {
    vector<int> nums = {1,1,2,3,3,4,4,8,8};
    cout << singleNonDuplicate(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int low = 0, high = nums.size() - 1;Initialize binary search range

while (low < high)Loop until one element remains

int mid = (low + high) / 2;Calculate midpoint

if (mid % 2 == 0)Check parity of mid

if (nums[mid] == nums[mid + 1])If pair intact, single element is right

low = mid + 2;Discard left half including pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element

function singleNonDuplicate(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (mid % 2 === 0) {
            if (nums[mid] === nums[mid + 1]) {
                low = mid + 2;
            } else {
                high = mid;
            }
        } else {
            if (nums[mid] === nums[mid - 1]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }
    return nums[low];
}

// Test
console.log(singleNonDuplicate([1,1,2,3,3,4,4,8,8])); // Output: 2

Line Notes

let low = 0, high = nums.length - 1;Initialize search boundaries

while (low < high)Loop until narrowed to one element

let mid = Math.floor((low + high) / 2);Calculate midpoint

if (mid % 2 === 0)Check parity of mid

if (nums[mid] === nums[mid + 1])If pair intact, single element is right

low = mid + 2;Discard left half including pair

else high = mid;Single element is at or before mid

return nums[low];Return the single element

⏱

Complexity

TimeO(log n)

SpaceO(1)

Same as previous binary search approach, halving search space each iteration.

💡 This approach is just as efficient but avoids XOR, which some interviewers prefer.

Interview Verdict: Accepted and optimal

This approach is equally good and shows flexibility in problem solving.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, you should code the binary search with parity checks (Approach 2 or 3) because it is optimal and elegant. Brute force is only for initial explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Linear Scan)	O(n)	O(1)	No	N/A	Mention only - never code unless asked for brute force
2. Binary Search Using Index Parity	O(log n)	O(1)	No	N/A	Code this as optimal solution
3. Binary Search Without XOR (Parity Based Halving)	O(log n)	O(1)	No	N/A	Code this if XOR is disallowed or to show parity mastery

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimal binary search solution with parity logic. Practice coding and testing edge cases.

How to Present

Step 1: Clarify the problem constraints and input-output format.Step 2: Describe the brute force linear scan approach and its inefficiency.Step 3: Introduce the binary search approach using parity to halve the search space.Step 4: Write clean, bug-free code for the binary search solution.Step 5: Test with edge cases and explain the reasoning.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of binary search modifications, handling of edge cases, and ability to optimize from brute force to logarithmic time.

Common Follow-ups

• What if the array is not sorted? → Cannot use binary search, fallback to hash or linear scan.
• Can you solve using XOR? → Yes, XOR all elements; the result is the single element.

💡 These follow-ups test your adaptability and knowledge of related techniques.

🔍

Pattern Recognition

When to Use

1) Array is sorted, 2) Every element appears twice except one, 3) Need O(log n) time, 4) Single unique element disrupts pair pattern

Signature Phrases

'every element appears twice except for one''find the single element in O(log n) time'

NOT This Pattern When

Problems where elements appear once but array is unsorted or no pairing pattern exist

Similar Problems

Find Minimum in Rotated Sorted Array - also uses modified binary searchSearch in Rotated Sorted Array - binary search with condition checksMedian of Two Sorted Arrays - binary search on partition indices

Practice

1. Consider the following Python code implementing an integer square root using Newton's method. What is the value of guess after the first iteration of the while loop when x = 8?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize variables for x=8

   Initial guess = 8 // 2 = 4.

2. Step 2: First iteration update

   Check 4*4=16 > 8, so update guess = (4 + 8 // 4) // 2 = (4 + 2) // 2 = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First guess update correctly computes to 3 [OK]

Hint: Initial guess halves x; update uses integer division [OK]

Common Mistakes:

• Off-by-one in guess update
• Confusing integer division with float
• Miscomputing initial guess

2. What is the worst-case time complexity of the optimal binary search algorithm that handles duplicates in a rotated sorted array?

medium

A. O(n) because duplicates can force linear scanning in worst case

B. O(log n) because binary search halves the search space each iteration

C. O(n log n) due to repeated duplicate skipping combined with binary search

D. O(1) since duplicates are skipped quickly

Solution

1. Step 1: Analyze binary search with duplicates

   Duplicates at boundaries can cause the algorithm to skip only one element per iteration, degrading to linear scan.

2. Step 2: Conclude worst-case complexity

   In worst case (all elements equal), the algorithm behaves like linear search -> O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicates break binary halving, causing linear worst-case [OK]

Hint: Duplicates can degrade binary search to linear time [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case
• Thinking duplicate skipping is constant time

3. Suppose Koko can eat bananas from multiple piles simultaneously each hour (i.e., she can split her eating speed across piles). How does this change the approach to find the minimum eating speed to finish within h hours?

hard

A. Feasibility check simplifies to total bananas ≤ speed * h, so minimum speed = ceil(total / h)

B. We must use dynamic programming to consider all pile combinations per hour

C. The original binary search with feasibility check still applies without changes

D. Binary search is invalid; a greedy approach is required instead

Solution

1. Step 1: Understand the new eating model

   Koko can split speed across piles simultaneously, so total bananas eaten per hour equals speed.

2. Step 2: Simplify feasibility condition

   To finish in h hours, total bananas ≤ speed * h, so minimum speed = ceil(total bananas / h).

3. Step 3: Conclude algorithm change

   No binary search needed; direct calculation suffices.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Splitting speed removes per-pile constraints, simplifying problem [OK]

Hint: Splitting speed means total bananas divided by hours [OK]

Common Mistakes:

• Applying original binary search blindly
• Overcomplicating with DP

4. Suppose the problem is modified so that the multiplication table allows repeated use of the same row and column indices (i.e., infinite repetitions of each product). Which of the following changes to the algorithm is correct to find the k-th smallest number under this new condition?

hard

A. Use the same binary search with the counting function unchanged, since repetition doesn't affect counts.

B. Switch to generating all products up to k and sorting them, since binary search no longer applies.

C. Use a min-heap to generate products in ascending order with duplicates allowed, extracting k elements.

D. Modify the counting function to remove the cap by n, counting all multiples less than or equal to x for each i.

Solution

1. Step 1: Understand the new problem condition

   Allowing infinite repetitions means the multiplication table is conceptually infinite, so counting by rows capped at n no longer applies.

2. Step 2: Analyze algorithmic implications

   Binary search with counting function fails because counts become infinite or undefined; generating all values is impossible.

3. Step 3: Use a min-heap approach

   A min-heap can generate products in ascending order with duplicates allowed, extracting the k-th smallest efficiently.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap approach handles infinite repetitions correctly [OK]

Hint: Infinite repetitions break counting; use min-heap [OK]

Common Mistakes:

• Assuming counting function unchanged
• Trying to generate all values

5. Suppose now you want to make bouquets but flowers can be reused multiple times (i.e., each flower can be counted multiple times for different bouquets). Which modification to the algorithm is correct?

hard

A. Keep the same binary search and feasibility check, but remove resetting flowers count to zero on encountering a flower that blooms after the day.

B. Binary search is no longer applicable; instead, use a greedy approach to pick flowers repeatedly until bouquets are formed.

C. Use binary search on days, but feasibility must count bouquets by grouping any flowers bloomed by day, allowing reuse by not resetting flowers count.

D. Modify feasibility to count total flowers bloomed by day and check if total flowers >= m * k, ignoring adjacency.

Solution

1. Step 1: Understand reuse changes adjacency constraint

   If flowers can be reused multiple times, adjacency no longer matters; only total count of bloomed flowers by day matters.

2. Step 2: Modify feasibility check

   Feasibility reduces to checking if total bloomed flowers by day >= m * k, ignoring adjacency and resetting.

3. Step 3: Binary search remains valid

   Binary search on days still applies, but feasibility is simplified to total count check.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Counting total bloomed flowers matches reuse scenario. [OK]

Hint: Reuse removes adjacency; feasibility counts total bloomed flowers [OK]

Common Mistakes:

• Ignoring adjacency but still resetting flowers count
• Removing binary search unnecessarily