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