##### 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.

##### 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.

• thonic

In my opinion the line:
if cnt < len(A)//2:
should be:
if cnt <= len(A)//2:

• Mikhail Manukhin

Agree. Moreover, these lines are redundant:
if cnt 0 then it must be a leader.

• Hmm. I will have to look into this challenge again. Solved it too long ago…