Single Element in Sorted Array

📋

Problem

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.

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

Edge cases: Single element array [5] → 5Single element at the start [2,3,3,4,4] → 2Single element at the end [1,1,2,2,3] → 3

</>

IDE

def singleNonDuplicate(nums: list[int]) -> int:public int singleNonDuplicate(int[] nums)int singleNonDuplicate(vector<int> &nums)function singleNonDuplicate(nums)

def singleNonDuplicate(nums):
    # Write your solution here
    pass

class Solution {
    public int singleNonDuplicate(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int singleNonDuplicate(vector<int> &nums) {
    // Write your solution here
    return 0;
}

function singleNonDuplicate(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Always returning the first element without checking pairs or parity.✅ Implement binary search with parity checks to find the single element instead of returning nums[0].

Wrong: 3Returning the middle element without verifying if it is single or part of a pair.✅ Check if nums[mid] equals nums[mid+1] or nums[mid-1] and adjust search boundaries accordingly.

Wrong: 2Off-by-one error causing incorrect mid calculation or boundary update.✅ Use mid = low + (high - low) // 2 and update low or high carefully based on parity and pair checks.

Wrong: last element or out of bounds errorNot handling single-element or boundary cases properly, causing index errors or wrong returns.✅ Add base cases for single-element arrays and check boundaries before accessing nums[mid+1].

Wrong: Timeout or no outputUsing linear scan or exponential approach instead of binary search.✅ Implement O(log n) binary search using parity-based halving to avoid TLE.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly before moving on.

Review your binary search logic for off-by-one and parity errors.

Ensure your solution is optimized to O(log n) to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,1,2,3,3,4,4,8,8]}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Use binary search to exploit the sorted property and pairs.

💡 Check the parity of the index and compare with the next element to decide search direction.

💡 Adjust search boundaries based on whether pairs start at even or odd indices.

Why it failed: Returned wrong element or index. Likely incorrect parity check or boundary update in binary search. Fix by ensuring mid index parity is used to decide which half to discard.

✓ Correctly identified the single element using parity-based binary search.

t1_02basic

Input{"nums":[3,3,7,7,10,11,11]}

Expected10

⏱ Performance - must finish in 2000ms

10 is the single element appearing once; all others appear twice.

💡 Focus on the halves where the single element must lie based on pair alignment.

💡 Use index parity to determine if the single element is on left or right side.

💡 If mid is even and nums[mid] == nums[mid+1], search right; else left.

Why it failed: Incorrectly returned a duplicate element. Possibly failed to handle the case where single element is in the middle. Fix by carefully checking pair alignment and adjusting search boundaries accordingly.

✓ Successfully located the single element in the middle of the array.

t2_01edge

Input{"nums":[5]}

Expected5

⏱ Performance - must finish in 2000ms

Single element array; the only element is the single element.

💡 Consider the smallest input size possible.

💡 Check if your code handles arrays with length 1 without errors.

💡 Return the only element immediately if array length is 1.

Why it failed: Fails on single-element input by accessing out-of-bound indices or not returning the element. Fix by adding a base case for length 1 arrays.

✓ Correctly handles single-element arrays.

t2_02edge

Input{"nums":[2,3,3,4,4]}

Expected2

⏱ Performance - must finish in 2000ms

Single element is at the start of the array.

💡 Check if your binary search handles single element at the start correctly.

💡 Verify boundary conditions when the single element is at index 0.

💡 If mid is 0 and nums[mid] != nums[mid+1], return nums[mid].

Why it failed: Fails to detect single element at start due to incorrect boundary checks or assumptions about pairs. Fix by explicitly checking start boundary conditions.

✓ Correctly identifies single element at the start.

t2_03edge

Input{"nums":[1,1,2,2,3]}

Expected3

⏱ Performance - must finish in 2000ms

Single element is at the end of the array.

💡 Ensure your binary search handles the single element at the last index.

💡 Check if your code correctly returns the last element if no single element found earlier.

💡 If loop ends without finding, return nums[-1].

Why it failed: Fails to detect single element at end due to loop termination conditions or missing final return. Fix by returning last element if no single element found earlier.

✓ Correctly identifies single element at the end.

t3_01corner

Input{"nums":[1,1,2,2,3,4,4,5,5]}

Expected3

⏱ Performance - must finish in 2000ms

Single element 3 is in the middle; tests off-by-one errors in binary search.

💡 Beware of off-by-one errors when updating mid and boundaries.

💡 Check if mid is even or odd before comparing pairs.

💡 Adjust low and high pointers carefully to avoid infinite loops.

Why it failed: Off-by-one error causes infinite loop or wrong element returned. Fix by correctly calculating mid and updating low/high with mid+1 or mid-1 as appropriate.

✓ Handles off-by-one boundary updates correctly.

t3_02corner

Input{"nums":[1,1,2,3,3,4,4,5,5]}

Expected2

⏱ Performance - must finish in 2000ms

Single element 2 is just after a pair; tests greedy approach trap.

💡 Greedy approach may fail by always choosing left or right half without parity checks.

💡 Use parity-based binary search to decide which half to discard.

💡 Check if mid is even and nums[mid] == nums[mid+1] to decide direction.

Why it failed: Greedy approach fails by ignoring parity and pair alignment. Fix by implementing parity-based binary search logic.

✓ Avoids greedy trap by using parity-based halving.

t3_03corner

Input{"nums":[1,1,2,2,3,3,4,5,5]}

Expected4

⏱ Performance - must finish in 2000ms

Single element 4 is just before a pair; tests confusion between 0/1 and unbounded knapsack style indexing.

💡 Do not confuse 0/1 indexing with unbounded or repeated elements.

💡 Pairs are always two consecutive elements; single element breaks this pattern.

💡 Use binary search to find the first index where pair pattern breaks.

Why it failed: Confuses indexing leading to wrong mid calculation or pair checks. Fix by carefully using zero-based indexing and checking pairs at mid and mid+1.

✓ Correctly distinguishes pair boundaries and single element.

t4_01performance

Input{"nums":[1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16,17,17,18,18,19,19,20,20,21,21,22,22,23,23,24,24,25,25,26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,49,49,50]}

Expectednull

⏱ Performance - must finish in 2000ms

n=101 with one single element at the end (50). Algorithm must run in O(log n) time within 2 seconds.

💡 Brute force O(n) may be too slow for large n.

💡 Use binary search with parity checks to achieve O(log n).

💡 Avoid linear scans; focus on halving search space each step.

Why it failed: Algorithm exceeds time limit due to linear or exponential complexity. Fix by implementing O(log n) binary search using parity-based halving.

✓ Algorithm runs within time limit using O(log n) complexity.

Practice

1. You need to find the minimum speed to travel through a series of distances within a given total time, where each segment except the last must be completed in whole hours (rounded up). Which algorithmic approach guarantees finding the minimum feasible speed efficiently?

easy

A. Binary search on the speed range (answer space) combined with a feasibility check

B. Brute force linear search incrementing speed until the time constraint is met

C. Dynamic programming to store minimum speeds for subproblems

D. Greedy approach by always choosing the fastest possible speed for each segment

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the minimum speed that satisfies a time constraint with rounding up travel times for all but the last segment.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (speed) efficiently narrows down the minimum feasible speed by checking feasibility at midpoints, unlike greedy or DP which do not fit the problem structure.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on answer space is standard for optimization problems with monotonic feasibility [OK]

Hint: Binary search on answer space fits monotonic feasibility [OK]

Common Mistakes:

• Thinking greedy or DP can solve this efficiently
• Using brute force linear search without pruning

2. Consider the following code snippet that searches for a target in a 2D matrix by performing binary search on each row. Given the matrix = [[1,3,5],[7,9,11],[13,15,17]] and target = 9, what is the return value of the function searchMatrix(matrix, target)?

easy

A. True

B. Returns None

C. Raises an exception

D. False

Solution

1. Step 1: Trace binary search on second row [7,9,11]

   Mid index 1 has value 9 which equals target, so binary_search returns True.

2. Step 2: searchMatrix returns True immediately after finding target

   Since binary_search returns True for second row, searchMatrix returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Target found in second row at mid index 1 [OK]

Hint: Binary search returns True when target found [OK]

Common Mistakes:

• Off-by-one errors in mid calculation
• Returning False prematurely
• Confusing return values

3. What is the time complexity of the optimal binary search approach to find the kth positive missing number in a sorted array of length n?

medium

A. O(log n)

B. O(k + n)

C. O(n log k)

D. O(n)

Solution

1. Step 1: Identify the binary search loop

   The algorithm performs binary search on the array indices, halving the search space each iteration.

2. Step 2: Analyze loop iterations

   Binary search runs in O(log n) time, independent of k, since it only searches within the array length.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step -> O(log n) [OK]

Hint: Binary search on array indices -> O(log n) [OK]

Common Mistakes:

• Confusing with brute force O(k + n)
• Assuming dependence on k
• Thinking recursion stack adds complexity

4. Identify the bug in the following modified code snippet for the Minimum Days to Make m Bouquets problem:

medium

A. The feasibility function does not reset flowers count correctly.

B. Binary search boundaries are incorrectly set from 0 instead of min bloom day.

C. The initial check for m * k > n is missing, causing unnecessary computation.

D. Early stopping in feasibility function is missing, causing slower runtime.

Solution

1. Step 1: Check initial conditions

   The code lacks the check if m * k > n, which means it's impossible to make required bouquets.

2. Step 2: Consequences of missing check

   Without this, the code runs unnecessary binary search and feasibility checks, possibly returning wrong answers or timing out.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Adding the initial impossible case check fixes the bug. [OK]

Hint: Always check if total flowers suffice before processing [OK]

Common Mistakes:

• Forgetting impossible case check
• Misresetting flowers count in feasibility

5. Suppose the problem is modified so that the matrix rows are sorted but columns are not guaranteed to be sorted. Which approach would correctly find the kth smallest element efficiently?

hard

A. Use the min-heap approach merging rows as before, since rows remain sorted.

B. Flatten the matrix and sort it, then return the kth element.

C. Use binary search on the value range with a counting function scanning the entire matrix.

D. Use a min-heap merging columns instead of rows.

Solution

1. Step 1: Analyze matrix properties

   Rows are sorted but columns are not, so min-heap merging rows only partially orders elements.

2. Step 2: Evaluate approaches

   Min-heap merging rows assumes columns sorted for correctness; binary search counting requires sorted rows and columns for efficient counting; flatten and sort works regardless.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flatten and sort is the fallback when only rows sorted [OK]

Hint: Partial sorting breaks heap and binary search assumptions [OK]

Common Mistakes:

• Assuming min-heap merging rows still works
• Using binary search counting without full sorting
• Ignoring matrix sorting properties