##### Short Problem Definition:

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

##### Link

EquiLeader

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

Get the leader as in the training material. Afterwards check every position if both sides have enough leader occurrences.

##### Solution:

def solution(A):
candidate_ele = ''
candidate_cnt = 0
for value in A:
if candidate_ele == '':
candidate_ele = value
candidate_cnt = 1
else:
if value != candidate_ele:
candidate_cnt -= 1
if candidate_cnt == 0:
candidate_ele = ''
else:
candidate_cnt += 1
if candidate_cnt == 0:
return 0
cnt = 0
last_idx = 0
for idx, value in enumerate(A):
if value == candidate_ele:
cnt += 1
last_idx = idx
if cnt < len(A)//2:
return 0
equi_cnt = 0
cnt_to_the_left = 0
for idx, value in enumerate(A):
if value == candidate_ele:
cnt_to_the_left +=1
if cnt_to_the_left > (idx + 1)//2 and \
cnt - cnt_to_the_left > (len(A) - idx - 1) //2:
equi_cnt += 1
return equi_cnt

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.