SDE - 2

As the array was sorted we can make use of this information to use Binary Search.


// EXPLANATION:-
// Suppose array is [1, 1, 2, 2, 3, 3, 4, 5, 5]
// we can observe that for each pair, 
// first element takes even position and second element takes odd position
// for example, 1 is appeared as a pair,
// so it takes 0 and 1 positions. similarly for all the pairs also.

// this pattern will be missed when single element is appeared in the array.

// From these points, we can implement algorithm.
// 1. Take left and right pointers . 
// left points to start of list. right points to end of the list.
// 2. find mid.
// if mid is even, then it's duplicate should be in next index.
// or if mid is odd, then it's duplicate should be in previous index.
// check these two conditions, 
// if any of the conditions is satisfied,
// then pattern is not missed, 
// so check in next half of the array. i.e, left = mid + 1
// if condition is not satisfied, then the pattern is missed.
// so, single number must be before mid.
// so, update end to mid.
// 3. At last return the nums[left]

// Time: - O(logN)
// space:- O(1)

Tip 1 : Ask clarification questions
Tip 2 : Try and think in terms of brute force and then gradually optimize your solution
Tip 3 : Ensure to check for edge cases
Tip 4 : Ensure to be thorough with data structures, algorithms and system design concepts.

Ensure that you are thorough with the design of your project at your current organization.