algoadvance

Leetcode 540. Single Element in a Sorted Array

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.

You must implement a solution with a logarithmic runtime complexity.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

Constraints:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5

Clarifying Questions

1. Can we assume the input array ‘nums’ is non-empty and always contains exactly one single element with the rest being pairs?
   • Yes, the problem guarantees the conditions mentioned.
2. Is it guaranteed that the length of the array is odd?
   • Yes, since there is exactly one element that appears only once and every other element appears exactly twice, the length of the array would indeed be odd.

Strategy

To achieve a logarithmic runtime complexity, we can utilize a binary search approach. The main insight is that if we observe the paired elements, we can determine the side on which the single element lies:

1. If mid is even and nums[mid] == nums[mid+1] OR if mid is odd and nums[mid] == nums[mid-1], then the single element is toward the right.
2. Otherwise, the single element is toward the left.

Using this strategy, we can adjust our binary search bounds until we zero in on the single element.

Code

Here is the C++ code to solve the problem using binary search:

#include <vector>
using namespace std;

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (mid % 2 == 1) mid--; // Ensure mid is even
            
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2; // Move right
            } else {
                right = mid; // Move left
            }
        }
        
        return nums[left];
    }
};

Time Complexity

The time complexity for the binary search solution is:

• Time complexity: (O(\log n)) because we’re halving the search space with each iteration.
• Space complexity: (O(1)) since we’re only using a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?