Skip to main content

Binary Search

Single Element in a Sorted Array Solution In C++/Java/Python/JS

Problem Description:

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.

Examples:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
Explanation: The unique element is 2, which appears only once while all other elements appear twice.

Input: nums = [3,3,7,7,10,11,11]
Output: 10
Explanation: The unique element is 10, which appears only once while all other elements appear twice.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Brute Force Approach

Okay, so here's the thought process:

What comes to mind after reading the problem statement?

We need to find the single element that appears only once in the given sorted array where every other element appears exactly twice.

To approach this problem, we need to consider both the sequence of elements and their pattern of occurrence. Here's a simple and systematic approach.

First, observe the pattern of pairs in the given array. For instance, in the array [1, 1, 2, 3, 3, 4, 4, 8, 8], the element 2 appears only once, while every other element appears twice. Similarly, in the array [3, 3, 7, 7, 10, 11, 11], the unique element is 10.

One straightforward solution is to linearly traverse the array and compare adjacent elements. Since the array is sorted, the unique element will be the first element that is different from its previous and next neighbor (considering boundary conditions carefully).

To find the single non-duplicate element efficiently, we can iterate through the array step by step.

Starting from index 0, we can efficiently identify the unique element by stepping 2 indices at a time. Since every element (except the unique one) appears exactly twice, this step size allows us to directly compare pairs and skip unnecessary checks.

The reason this works is that in a properly sorted array with paired elements, every pair will naturally appear side by side. By moving in steps of 2, we can efficiently jump over pairs and focus only on the points where a mismatch might occur — which is exactly where the unique element will be found.

For example, consider the array [1, 1, 2, 3, 3, 4, 4, 8, 8]. Starting at index 0, we compare nums[0] with nums[1]. Since they are equal, we move to index 2. At this point, nums[2] is 2, and nums[3] is 3. Since they are different, we immediately know that 2 is the unique element.

Similarly, in the array [3, 3, 7, 7, 10, 11, 11], we start at index 0 and find that nums[0] equals nums[1], so we move forward. The same happens at index 2. But at index 4, we find nums[4] is 10 and nums[5] is 11, meaning 10 is the unique element.

By stepping 2 indices at a time, we effectively minimize unnecessary comparisons and quickly zero in on the point where the pairing pattern breaks — revealing the unique element. This approach leverages the sorted order to work efficiently and ensures we solve the problem in optimal time.

This method effectively identifies the unique element in O(n) time with O(1) space by simply traversing the array.

💡
Try it Yourself!

Let's understand with an example:

Single Element in a Sorted Array Example:

Concise Dry Run for Input: nums = [3, 3, 7, 7, 10, 11, 11]

  1. Start at index 0:
    • nums[0] == nums[1] → Both are 3, continue.
  3. Move to index 2:
    • nums[2] == nums[3] → Both are 7, continue.
  5. Move to index 4:
    • nums[4] != nums[5] → Found the unique element: 10

Output: 10

How to code it up:

  • Initialize Variables:
    • Start with i = 0 and iterate through the array in steps of 2.
  • Traverse the Array:
    • For each pair, check if nums[i] != nums[i + 1].
      • If true, nums[i] is the unique element — return it immediately.
  • Handle Edge Cases:
    • If no mismatch is found during the loop, the unique element must be the last element in the array.
  • Return the Unique Element.

Single Element in a Sorted Array Solution

Code Implementation / Single Element in a Sorted Array leetcode solution
1. Single Element in a Sorted Array Leetcode Solution C++ Try on Compiler 
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {

        // Traverse the array in steps of 2 to check pairs
        for (int i = 0; i < nums.size() - 1; i += 2) {
            // If the current element is not equal to the next one, it's the
            // unique element
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        
        // If no mismatch found in pairs, the unique element is the last one
        return nums.back();
    }
};

2. Single Element in a Sorted Array Leetcode Solution Java Try on Compiler 
class Solution {
    public int singleNonDuplicate(int[] nums) {

        // Traverse the array in steps of 2 to check pairs
        for (int i = 0; i < nums.length - 1; i += 2) {
            
            // If the current element is not equal to the next one, it's the unique element
            if (nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }

        // If no mismatch found in pairs, the unique element is the last one
        return nums[nums.length - 1];
    }
}

3. Single Element in a Sorted Array Leetcode Solution Python Try on Compiler 
class Solution:
    def singleNonDuplicate(self, nums):

        # Traverse the array in steps of 2 to check pairs
        for i in range(0, len(nums) - 1, 2):
            # If the current element is not equal to the next one, it's the unique element
            if nums[i] != nums[i + 1]:
                return nums[i]
        
        # If no mismatch found in pairs, the unique element is the last one
        return nums[-1]

4. Single Element in a Sorted Array Leetcode Solution Javascript Try on Compiler 
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function (nums) {

    // Traverse the array in steps of 2 to check pairs
    for (let i = 0; i < nums.length - 1; i += 2) {
        // If the current element is not equal to the next one, it's the unique element
        if (nums[i] !== nums[i + 1]) {
            return nums[i];
        }
    }

    // If no mismatch found in pairs, the unique element is the last one
    return nums[nums.length - 1];
};

Complexity Analysis for Single Element in a Sorted Array LeetCode Solution

Time Complexity: O(n)

The loop iterates through the array in steps of 2.

In the given solution:

  • The loop iterates with i += 2, meaning it checks every second element.
  • This may seem like only half the elements are visited.
  • However, when analyzing time complexity, we focus on asymptotic behavior — that is, how the algorithm scales with the input size.
  • Whether we take n steps or n/2 steps, the behavior is still linear — the algorithm's performance scales directly with the array size.
  • Big-O only cares about the dominant term, and since n/2 is proportional to n, we simplify it to O(n).

In the worst case, the unique element might be the last element, meaning the loop runs through the entire array.

Space Complexity: O(n)

Auxiliary Space Complexity: O(1 )
Explanation: We are only using a few integer variables — such as i (loop counter) — to track the array traversal. No additional data structures like arrays, lists, or hash maps are used.
Thus, the auxiliary space complexity is O(1) since only a constant amount of extra space is required.

Total Space Complexity: O(n)
Explanation: The input array nums is provided as an argument, and its size contributes to the total space usage. However, since this space is not created by the algorithm itself (it's part of the input), we do not count it under auxiliary space but still acknowledge it as part of the total space complexity.
Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution with O(n) time complexity, the approach efficiently handles the given constraints.

Since the maximum possible value for n (array length) is 10⁵, the solution may require up to 10⁵ steps in the worst case.

In competitive programming environments, problems typically handle up to 10⁶ operations per test case. With a maximum of 10⁵ steps, the solution comfortably fits within these limits.

Therefore, the O(n) time complexity ensures the solution works efficiently within the given problem constraints and will not result in Time Limit Exceeded (TLE) errors, even when handling maximum input values.

Can we optimize it?

Let's look at optimizing the solution further.

In our previous solution, we iterated through the array to identify the element that appears only once. While this approach worked, it had a time complexity of O(n). Now, we want to make this process more efficient.

In this problem, we are given a sorted array where every element appears exactly twice except for one element that appears only once. By analyzing the pattern of pairs, we can make some useful observations:

  1. Before the unique element: Each pair starts at an even index and its duplicate appears at the next odd index. Example: In [1, 1, 3, 3, 4, 4, 8, 8], the number 1 appears at index 0 and 1, and 3 appears at index 2 and 3, following the expected pattern of pairs.
  2. After the unique element: Each pair starts at an odd index and its duplicate appears at the next even index. Example: In [3, 4, 4, 8, 8], 4 appears at index 2 and 3, and 8 appears at index 4 and 5, indicating that a unique number must have appeared before index 2 to shift this pattern.
  3. The unique element itself: Appears at an even index, and there’s no corresponding duplicate. Example: In [1, 1, 2, 3, 3, 4, 4, 8, 8], the number 2 appears at index 2, but no duplicate exists, making it the unique number in the array.

In addition to these observations, we can also determine whether the unique element lies in the left or right part of the array based on the index pattern.

If we are at a certain index x:

  • If x is even and nums[x] == nums[x + 1], the unique element is in the right half.
    Example:     In [1, 1, 2, 3, 3, 4, 4, 8, 8], at x = 0, we have nums[0] = 1 and nums[1] = 1, which forms a valid pair. Similarly, at x = 2, nums[2] = 2 and nums[3] = 3 are different, meaning the pattern is broken. Since x = 0 and x = 2 are even and the pairs are intact at x = 0, the unique element must be somewhere in the right half.
  • If x is even and nums[x] != nums[x + 1], the unique element is in the left half, including the current element at x.
    Example:     In [1, 1, 2, 3, 3, 4, 4, 8, 8], at x = 2, nums[2] = 2 and nums[3] = 3 are different. This mismatch indicates that the unique element has disturbed the normal pattern, meaning it must be at x = 2 or in the left half of the array.

Let's make a few more observations based on this insight to refine our search strategy further.

To solve the problem efficiently, we can identify some key properties of the array and the single non-duplicate number:

  1. The Array is Sorted: ➔ Since the array is sorted, the unique element must disrupt the pattern of consecutive pairs.
  2. The Search Space is Monotonic: ➔ As we move through the array, if the current index follows the correct pattern (pairs starting at even indices), the unique element must be further ahead. Conversely, if the pattern breaks, the unique element must be in the left side.
    For example, consider the array [1, 1, 2, 3, 3, 4, 4].
    At index 0, nums[0] == nums[1], so the unique element is further ahead.
    At index 2, nums[2] != nums[3], which breaks the pattern, confirming the unique element is at index 2 or earlier.
  3. The Middle Element Helps Minimize the Search Space: For any element nums[mid], if mid is odd, we adjust it to be even (because pairs ideally start at even indices).
    If nums[mid] != nums[mid + 1], it means the pattern is broken, and the unique element lies in the left half.
    If nums[mid] == nums[mid + 1], the pattern holds, and the unique element must be in the right half.

Remember, these properties align perfectly with the conditions for applying binary search. Since the array is sorted, exhibits a monotonic pattern, and allows us to make directional decisions based on conditions, binary search is the ideal technique here.

💡
Check how binary search works!

Single Element in a Sorted Array Binary Search Algorithm

We will use binary search to efficiently locate the unique element. Starting with low = 0 and high = nums.size() - 1, we repeatedly check the middle element. If mid is odd, we decrement it by one to ensure we're checking an even index. From there:

  • If nums[mid] == nums[mid + 1], the unique element must be in the right half, so we move low = mid + 2.
  • If nums[mid] != nums[mid + 1], the unique element must be in the left half, so we move high = mid. The loop continues until low and high converge, and the unique element will be at nums[low].

Once the binary search concludes, the low pointer will point directly to the unique element. This happens because during the search, each step eliminates half of the search space based on the pattern of pairs.

Since the unique element disrupts this pattern, the search space will eventually shrink to a single element — the unique number itself. At this point, the low pointer will be pointing directly to that element.

This approach efficiently identifies the unique element with O(log n) time complexity and O(1) space, leveraging the predictable pattern of pairs in the sorted array.

Let us understand this with a video.

0:00
/1:26
💡
Try it Yourself!

Understand with an example:

Single Element in a Sorted Array Example:

Concise Dry Run for Input: nums = [3, 3, 7, 7, 10, 11, 11]

We'll follow the binary search approach outlined earlier.

  1. Initial Pointers:
    • low = 0, high = 6 (last index)
  3. Step 1: Calculate mid
    • mid = (0 + 6) / 2 = 3
    • Since mid is odd, decrement it to ensure we are on an even index → mid = 2
    • nums[mid] = 7 and nums[mid + 1] = 7 → This means the unique element is in the right half
    • low = mid + 2 = 4
  5. Step 2: Calculate mid again
    • mid = (4 + 6) / 2 = 5
    • Since mid is odd, decrement it to ensure an even index → mid = 4
    • nums[mid] = 10 and nums[mid + 1] = 11 → This means the pattern is broken, and the unique element is in the left half
    • high = mid = 4
  7. Step 3: low = high = 4
    • At this point, both pointers converge at index 4, which holds the unique element.

Final Answer: 10

How to code it up?

  1. Initialize Pointers:
    • Set low = 0 and high = nums.size() - 1.
  3. Binary Search Loop:
    • Continue the loop while low < high.
  5. Calculate Midpoint:
    • Compute mid = (low + high) / 2.
    • Since pairs ideally start at even indices, if mid is odd, decrement it by 1 to ensure mid points to an even index.
  7. Check for Broken Pattern:
    • If nums[mid] ≠ nums[mid + 1], the unique element must be in the left half → Update high = mid.
    • Otherwise, if the pattern holds (nums[mid] == nums[mid + 1]), the unique element must be in the right half → Update low = mid + 2.
  9. Return Result:
    • Once the loop ends, low will point to the single non-duplicate element.
    • Return nums[low].

Single Element in a Sorted Array Solution

Code Implementation / Single Element in a Sorted Array Leetcode Solution
1. Single Element in a Sorted Array Leetcode Solution C++ Try on Compiler 
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        // Initialize the search space
        int low = 0;
        int high = nums.size() - 1;

        // Perform binary search to locate the unique element
        while (low < high) {
            // Calculate mid index
            int mid = (low + high) / 2;

            // Ensure mid points to an even index (pairs should start at even indices)
            if (mid % 2 == 1)
                mid--;

            // Check if the pattern breaks at this point
            if (nums[mid] != nums[mid + 1])
                // Unique element lies in the left half (including mid)
                high = mid;
            else
                // Unique element lies in the right half
                low = mid + 2;
        }

        // Return the unique element found at the 'low' pointer
        return nums[low];
    }
};

2. Single Element in a Sorted Array Leetcode Solution Java Try on Compiler 
// Java Code Implementation
class Solution {
    public int singleNonDuplicate(int[] nums) {
        
        // Initialize the search space
        int low = 0;
        int high = nums.length - 1;

        // Perform binary search to locate the unique element
        while (low < high) {
            // Calculate mid index
            int mid = (low + high) / 2;

            // Ensure mid points to an even index (pairs should start at even indices)
            if (mid % 2 == 1)
                mid--;

            // Check if the pattern breaks at this point
            if (nums[mid] != nums[mid + 1])
                // Unique element lies in the left half (including mid)
                high = mid;
            else
                // Unique element lies in the right half
                low = mid + 2;
        }

        // Return the unique element found at the 'low' pointer
        return nums[low];
    }
}

3. Single Element in a Sorted Array Leetcode Solution Python Try on Compiler 
# Python Code Implementation
class Solution:
    def singleNonDuplicate(self, nums):

        # Initialize the search space
        low = 0
        high = len(nums) - 1

        # Perform binary search to locate the unique element
        while low < high:
            
            # Calculate mid index
            mid = (low + high) // 2

            # Ensure mid points to an even index (pairs should start at even indices)
            if mid % 2 == 1:
                mid -= 1

            # Check if the pattern breaks at this point
            if nums[mid] != nums[mid + 1]:
                # Unique element lies in the left half (including mid)
                high = mid
            else:
                # Unique element lies in the right half
                low = mid + 2

        # Return the unique element found at the 'low' pointer
        return nums[low]

4. Single Element in a Sorted Array Leetcode Solution Javascript Try on Compiler 
// JavaScript Code Implementation
var singleNonDuplicate = function(nums) {

    // Initialize the search space
    let low = 0;
    let high = nums.length - 1;

    // Perform binary search to locate the unique element
    while (low < high) {
        
        // Calculate mid index
        let mid = Math.floor((low + high) / 2);

        // Ensure mid points to an even index (pairs should start at even indices)
        if (mid % 2 === 1)
            mid--;

        // Check if the pattern breaks at this point
        if (nums[mid] !== nums[mid + 1])
            // Unique element lies in the left half (including mid)
            high = mid;
        else
            // Unique element lies in the right half
            low = mid + 2;
    }

    // Return the unique element found at the 'low' pointer
    return nums[low];
};

Complexity Analysis for Single Element in a Sorted Array LeetCode Solution

Time Complexity: O(log n)

  • Binary Search Iterations:
    In each iteration, the search space is reduced by half. This is the defining property of binary search.
  • Suppose the array has n elements. Initially, the search space spans the entire array (from index 0 to n-1).
  • After one iteration, the search space is halved to n/2.
  • After two iterations, it becomes n/4.
  • This halving process continues until only one element remains — the unique element.
  • The number of times we can halve the array until one element remains is O(log n).

Space Complexity: O(n)

Auxiliary Space Complexity: O(1)
Explanation: The space complexity of this solution is O(1) because we only use a few variables such as low, high, and mid to store intermediate results. No additional data structures are used that grow with the size of the input.

Total Space Complexity: O(n)
Explanation: The input array nums is provided as an argument, and no extra space is allocated for new data structures during execution.
Therefore, the total space used by the algorithm is O(n).

Similar Problems

Working with sorted arrays allows for efficient searching and processing of elements. To find common elements in 3 sorted arrays, we can use a two-pointer or three-pointer approach to traverse the arrays simultaneously, ensuring an optimal solution. When dealing with unordered data, we may need to sort elements in an array first to enable efficient searching and merging. A common problem in sorted arrays is to find a single element appearing once in a sorted array, where every other element appears twice. This can be solved efficiently using Binary Search, leading to an optimized solution for the single element in a sorted array using binary search approach. By leveraging sorting, searching, and pointer-based techniques, we can solve these problems efficiently.

Now that we have successfully tackled this problem, let's try similar problems.

1. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.You must write an algorithm with O(log n) runtime complexity.

2. Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8