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. Consider the following Python code using bisect to count occurrences of a target in a sorted array. What is the output when nums = [1, 2, 2, 3] and target = 2?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace bisect_left for target=2

   bisect_left(nums, 2) returns index 1 (first 2 in array).

2. Step 2: Trace bisect_left for target+1=3

   bisect_left(nums, 3) returns index 3 (first 3 in array).

3. Step 3: Calculate count

   Count = right - left = 3 - 1 = 2 occurrences.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Indices 1 and 2 are 2's in array [OK]

Hint: bisect_left finds first occurrence index [OK]

Common Mistakes:

• Confusing bisect_left with bisect_right
• Off-by-one errors in index subtraction
• Using bisect_right for target+1 incorrectly

2. The following code attempts to find the median of two sorted arrays using binary search on the smaller array. Identify the line containing the subtle bug that can cause incorrect median calculation for even total length arrays.

medium

A. Line: if (m + n) % 2 == 0: return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2

B. Line: if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1

C. Line: partitionY = (m + n) // 2 - partitionX

D. Line: while low <= high:

Solution

1. Step 1: Understand partition calculation

   partitionY must be total left half minus partitionX to split arrays correctly.

2. Step 2: Identify off-by-one bug

   Using (m + n) // 2 instead of (m + n + 1) // 2 causes incorrect partition when total length is odd, leading to wrong median.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Partition calculation off-by-one breaks median correctness [OK]

Hint: Partition indices must sum to half total length exactly, using (m+n+1)//2 for correct odd/even handling [OK]

Common Mistakes:

• Swapping arrays incorrectly
• Wrong median formula for even length
• Loop boundary off-by-one

3. 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

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 the problem is modified so that the traveler can reuse the same speed for multiple trips (i.e., multiple independent journeys with the same speed constraint). Which modification to the binary search approach is necessary to handle this scenario correctly?

hard

A. Perform binary search separately for each trip and take the maximum minimum speed

B. Use a single binary search over speed and check feasibility across all trips combined

C. Switch to a brute force linear search since binary search no longer applies

D. Use dynamic programming to store feasibility states for each trip and speed

Solution

1. Step 1: Understand the reuse scenario

   All trips must be completed at the same speed, so feasibility must be checked collectively.

2. Step 2: Adapt binary search feasibility check

   Perform binary search on speed and verify if all trips can be completed on time at that speed combined.

3. Step 3: Reject separate searches or brute force

   Separate searches ignore the single speed constraint; brute force is inefficient; DP is unnecessary.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Single binary search with combined feasibility check handles reuse [OK]

Hint: Single binary search with combined feasibility check [OK]

Common Mistakes:

• Binary searching each trip separately
• Switching to brute force unnecessarily