DEV Community

Aroup Goldar Dhruba
Aroup Goldar Dhruba

Posted on

LeetCode: Single Element in a Sorted Array

#leetcode #datastructure #algorithms #binarysearch

Problem Statement

You are 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.

Example 1:

Input: [1,1,2,3,3,4,4,8,8] Output: 2
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: [3,3,7,7,10,11,11] Output: 10
Enter fullscreen mode Exit fullscreen mode

Note: Your solution should run in O(log n) time and O(1) space.

Solution 

class Solution { public: int singleNonDuplicate(vector<int>& nums) { int L=0, U=nums.size()-1; int result; while(L<=U) { if(L==U) { result = nums[L]; break; } int M = L+(U-L)/2; int consideredLength = M-L+1; if(consideredLength%2 == 1) { if(M-1>=0 && nums[M] == nums[M-1]) { U = M-2; } else if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) { L = M+2; } else { result = nums[M]; break; } } else { if(M+1<= nums.size()-1 && nums[M] == nums[M+1]) { U = M-1; } else if(M-1>=0 && nums[M] == nums[M-1]) { L = M+1; } else { result = nums[M]; break; } } } return result; } };
Enter fullscreen mode Exit fullscreen mode

Solution Thought Process

I solved this problem using binary search. First, we get the middle element of the range using low and high.

We get the length considered by calculating:

consideredLength = M-L+1
Enter fullscreen mode Exit fullscreen mode
  1. Let's consider if this length is odd. 
nums 1 1 2 2 3 idx 0 1 2 3 4 L = 0, U = 4 M = 0 + (4-0)/2 = 2
Enter fullscreen mode Exit fullscreen mode

So[L, M] is odd in length. If this is the case, if nums[M] == nums[M+1], it means that the element can be found from element index M+2. So we make L=M+2

Let's see another case,

nums 1 2 2 3 3 idx 0 1 2 3 4 L = 0, U = 4 M = 0 + (4-0)/2 = 2
Enter fullscreen mode Exit fullscreen mode

So [L, M] is odd in length. If nums[M] == nums[M-1] , it means that the element can be found before element index M-2 , included.

If those are not the case, then nums[M] is the result and we break the loop.

  1. Let's consider if the considered length is even. 
nums 1 1 2 3 3 5 5 idx 0 1 2 3 4 5 6 L = 0, U = 6 M = 0 + (6-0)/2 = 3
Enter fullscreen mode Exit fullscreen mode

So [L, M] is even in length. If nums[M] == nums[M+1], it means that the element can be found before element index M-1, included . So we make U = M-1

nums 1 1 2 2 3 5 5 idx 0 1 2 3 4 5 6 L = 0, U = 6 M = 0 + (6-0)/2 = 3
Enter fullscreen mode Exit fullscreen mode

So [L, M] is even in length. If nums[M]==nums[M-1], it means that the element can be found from element index M+1. So we make L=M+1.

If we have got L and U as the same element, we return the element as the result.

Complexity

Time Complexity: O(logn), we are making the consideration space half in every iteration.

Space Complexity: O(1)

Top comments (0)