##### Short Problem Definition:

Find an index of an array such that its value occurs at more than half of indices in the array.

##### Link

##### Complexity:

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

expected worst-case space complexity is O(1)

##### Execution:

As explained in the training material…

##### 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 -1 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 last_idx return -1

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