Single Element in Sorted Array

▶

Steps

setup

Initialize pointers

Set low to 0 and high to the last index of the array to start the binary search over the entire array.

💡 Initialization defines the full search space before any comparisons.

Line:

low, high = 0, len(nums) - 1

💡 The entire array is considered initially as the possible location of the single element.

compare

Calculate mid index

Calculate mid as the floor of (low + high) / 2, which is 4. Mid is even.

💡 Mid divides the current search space to check pairs for elimination.

Line:

mid = (low + high) // 2

💡 Mid index is the pivot for pair comparison.

compare

Compare nums[mid] and nums[mid+1] since mid is even

Compare nums[4] = 3 with nums[5] = 4. They are not equal, so the single element must be at or before mid.

💡 If nums[mid] != nums[mid+1] when mid is even, the single element is on the left side including mid.

Line:

if nums[mid] == nums[mid + 1]:
    low = mid + 2
else:
    high = mid

💡 We eliminate the right half beyond mid because pairs are disrupted here.

compare

Calculate new mid index

Calculate mid as floor((0 + 4) / 2) = 2. Mid=2 is even.

💡 Recalculate mid to continue narrowing the search space.

Line:

mid = (low + high) // 2

💡 Mid is the new pivot for pair comparison in the reduced search space.

compare

Compare nums[mid] and nums[mid+1] since mid is even

Compare nums[2] = 2 with nums[3] = 3. They are not equal, so the single element is at or before mid.

💡 If nums[mid] != nums[mid+1] at even mid, the single element is on the left side including mid.

Line:

if nums[mid] == nums[mid + 1]:
    low = mid + 2
else:
    high = mid

💡 We eliminate the right half beyond mid again.

compare

Calculate new mid index

Calculate mid as floor((0 + 2) / 2) = 1. Mid=1 is odd.

💡 Mid recalculated to continue binary search in smaller range.

Line:

mid = (low + high) // 2

💡 Mid is odd, so comparison will be with nums[mid-1].

compare

Compare nums[mid] and nums[mid-1] since mid is odd

Compare nums[1] = 1 with nums[0] = 1. They are equal, so the single element is after mid.

💡 If nums[mid] == nums[mid-1] at odd mid, the single element is on the right side.

Line:

if nums[mid] == nums[mid - 1]:
    low = mid + 1
else:
    high = mid - 1

💡 We eliminate the left half including mid-1 and mid.

prune

Check if low equals high

Now low = 2 and high = 2, so the search space is a single element.

💡 When low equals high, the single element is found.

Line:

while low < high:
    ...
return nums[low]

💡 The unique element is at index 2.

prune

Confirm the single element found

The single element is confirmed at index low = 2 with value 2.

💡 This step explicitly confirms the final answer before returning.

Line:

answer = nums[low]

💡 Confirming the final element ensures clarity before returning.

prune

Return the single element

Return nums[low] which is nums[2] = 2 as the single non-duplicate element.

💡 The final answer is the element at the converged pointer.

Line:

return nums[low]

💡 The algorithm successfully found the unique element using parity-based binary search.

def singleNonDuplicate(nums):
    low, high = 0, len(nums) - 1  # STEP 1
    while low < high:  # STEP 8 condition check
        mid = (low + high) // 2  # STEP 2,4,6
        if mid % 2 == 0:  # STEP 2,4,6 parity check
            if nums[mid] == nums[mid + 1]:  # STEP 3,5,7 compare right pair
                low = mid + 2  # STEP 3,5 decision
            else:
                high = mid  # STEP 3,5 decision
        else:
            if nums[mid] == nums[mid - 1]:  # STEP 7 compare left pair
                low = mid + 1  # STEP 7 decision
            else:
                high = mid - 1  # STEP 7 decision
    return nums[low]  # STEP 10 final return

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

📊

Single Element in Sorted Array - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and comparison helps you understand how parity and pair matching guide the binary search, which is not obvious from code alone.

lo

1

0

1

1

2

2

3

3

3

4

4

5

4

6

8

7

hi

8

8

Next: lo=0 hi=8

lo

1

0

1

1

2

2

3

3

mid

3

4

4

5

4

6

8

7

hi

8

8

mid[4]=3 - mid is even

Next: lo=0 hi=8

lo

1

0

1

1

2

2

3

3

mid

3

4

4

5

4

6

8

7

hi

8

8

mid[4]=3 - nums[mid] != nums[mid+1], move high to mid

Next: lo=0 hi=4

lo

1

0

1

1

mid

2

2

3

3

hi

3

4

4

5

4

6

8

7

8

8

mid[2]=2 - mid is even

Next: lo=0 hi=4

lo

1

0

1

1

mid

2

2

3

3

hi

3

4

4

5

4

6

8

7

8

8

mid[2]=2 - nums[mid] != nums[mid+1], move high to mid

Next: lo=0 hi=2

lo

1

0

mid

1

1

hi

2

2

3

3

3

4

4

5

4

6

8

7

8

8

mid[1]=1 - mid is odd

Next: lo=0 hi=2

lo

1

0

mid

1

1

hi

2

2

3

3

3

4

4

5

4

6

8

7

8

8

mid[1]=1 - nums[mid] == nums[mid-1], move low to mid+1

Next: lo=2 hi=2

1

0

1

1

lo/hi

2

2

3

3

3

4

4

5

4

6

8

7

8

8

Next: lo=2 hi=2

1

0

1

1

lo/hi

2

2

3

3

3

4

4

5

4

6

8

7

8

8

Next: lo=2 hi=2

1

0

1

1

lo/hi

2

2

3

3

3

4

4

5

4

6

8

7

8

8

Next: lo=2 hi=2

Key Takeaways

✓ Parity of the mid index determines which adjacent element to compare, enabling efficient halving of the search space.

This parity-based logic is subtle and not obvious from code alone; visualization clarifies why even and odd mid indices are handled differently.

✓ When nums[mid] equals its pair element, the single element lies beyond the pair; otherwise, it lies before or at mid.

Understanding this pattern helps grasp how the algorithm eliminates half the array each iteration.

✓ The algorithm converges when low equals high, pinpointing the unique element without scanning the entire array.

This stopping condition is critical and shows the power of binary search in this problem.

Practice

1. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a greedy approach by repeatedly picking the smallest element from the matrix without extra data structures.

B. Flatten the matrix into a list, sort it, and return the kth element.

C. Apply dynamic programming to build a table of smallest elements up to k.

D. Use a min-heap to merge the sorted rows, extracting the smallest elements until the kth is found.

Solution

1. Step 1: Understand problem constraints

   The matrix rows and columns are sorted, so each row is sorted and each column is sorted independently.

2. Step 2: Identify the optimal approach

   Using a min-heap to merge sorted rows efficiently extracts the smallest elements in ascending order, achieving O(k log n) time, better than flattening and sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges sorted lists optimally [OK]

Hint: Min-heap merges sorted rows efficiently [OK]

Common Mistakes:

• Assuming flatten and sort is optimal
• Confusing DP with this problem
• Thinking greedy without data structures works

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. What is the time complexity of the optimal solution that uses binary search on the answer space combined with prefix sums and binary search for feasibility checks in the Split Array Largest Sum problem?

medium

A. O(n log(sum(nums))) since binary search is done only on sums without extra binary searches

B. O(n^m) due to exploring all splits recursively

C. O(n^2 log(sum(nums))) because feasibility check scans all subarrays linearly

D. O(n log n log(sum(nums))) because each binary search iteration uses binary search on prefix sums

Solution

1. Step 1: Identify outer binary search on answer space

   Binary search on possible sums takes O(log(sum(nums))) iterations.

2. Step 2: Analyze feasibility check using binary search on prefix sums

   Each feasibility check uses binary search (O(log n)) for each subarray, repeated up to n times -> O(n log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested binary searches yield O(n log n log(sum(nums))) [OK]

Hint: Feasibility check uses binary search inside binary search [OK]

Common Mistakes:

• Assuming feasibility check is O(n) ignoring binary search
• Confusing n and m in complexity
• Ignoring log factor from binary search on sums

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 rotated sorted array may contain duplicate elements. Which modification to the pivot-finding algorithm is necessary to correctly find the pivot in O(log n) time in the worst case?

hard

A. Add a linear scan fallback when nums[mid] == nums[high] to reduce high by one.

B. Use a hash map to store visited indices to avoid infinite loops.

C. No modification needed; the existing pivot-finding algorithm works unchanged.

D. Switch to linear search for pivot since duplicates break binary search.

Solution

1. Step 1: Understand duplicates impact

   Duplicates can cause nums[mid] == nums[high], making it unclear which half is sorted.

2. Step 2: Modify pivot search

   When nums[mid] == nums[high], reduce high by one to shrink search space safely.

3. Step 3: Complexity consideration

   This modification keeps worst-case complexity close to O(n) but often better than linear scan.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Reducing high on equality handles duplicates correctly [OK]

Hint: Handle nums[mid]==nums[high] by decrementing high [OK]

Common Mistakes:

• Assuming no duplicates
• Switching to linear search unnecessarily