Hi there!

Recently completed the lesson.

In the solution section there is only a brute-force approach.

However, it seems there is another way to solve this problem which has a “nlogn” time complexity.

Could you please check the code below and tell me whether it is really have “nlogn” time complexity and could be used as a faster way of solving this task rather than using “Brute force” approach.

# O(1)

def check_near_cells(lst, ind):

el = lst[ind]

right_ind = ind + 1

left_ind = ind -1

is_alone = True

if right_ind < len(lst) and el == lst[right_ind]:

is_alone = False

if left_ind >= 0 and el == lst[left_ind]:

is_alone = False

return is_alone

#O(logn)

def binary_search(lst, k):

left = 0

right = len(lst) - 1

ind = -1

is_found = False

while left <= right and not is_found:

mid = (left + right) // 2

if lst[mid] == k:

if check_near_cells(lst, mid):

ind = mid

is_found = True

elif lst[mid] < k:

left = mid + 1

else:

right = mid -1

return ind

def find_first_unique(lst):

tmp = sorted(lst) #O(nlogn)

for el in lst: #O(n)

ind = binary_search(tmp, el) #O(logn)

if ind != -1:

return el

#O(2nlogn) = O(nlogn)

Course: Educative: Interactive Courses for Software Developers

Lesson: Educative: Interactive Courses for Software Developers