educative.io

Educative

There maybe another solution

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

Hi @Sergey2
Thank you for the suggestion. It is great seeing our users thinking out of the box and coming up with betterments. We’ll look into it. Your feedback is much appreciated!

1 Like