EquiLeader

28 Apr, 2021

Problem

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N − 1] have leaders of the same value.

For example, given array A such that:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

we can find two equi leaders:

0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4. The goal is to count the number of equi leaders.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2

the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];
each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

My Solution

failed

function solution(A) {
	let cnt = 0;

	for (let i = 1; i < A.length; i++) {
		let gr1 = A.slice(0, i);
		let gr2 = A.slice(i, A.length);

		let [map1, map2] = [{}, {}];
		let [lead1, lead2] = [0, 0];

		for (let j = 0; j < i; j++) {
			let key = gr1[j];
			map1[key] = key in map1 ? map1[key] + 1 : 1;

			if (map1[key] > gr1.length / 2) lead1 = key;
		}

		for (let k = 0; k < gr2.length; k++) {
			let key = gr2[k];
			map2[key] = key in map2 ? map2[key] + 1 : 1;

			if (map2[key] > gr2.length / 2) lead2 = key;
		}

		if (lead1 === lead2) cnt++;
	}

	return cnt;
}

success O(N)

function solution(A) {
	if (A.length === 1) return 0;

	let maxRepetition = 1;
	let maxIndex = -1;
	let occurance = {};

	for (let i = 0; i < A.length; i++) {
		if (occurance.hasOwnProperty(A[i])) {
			occurance[A[i]][0]++;

			if (
				occurance[A[i]][0] > maxRepetition &&
				occurance[A[i]][0] > A.length / 2
			) {
				maxRepetition = occurance[A[i]][0];
				maxIndex = occurance[A[i]][1];
			}
		} else {
			occurance[A[i]] = [];
			occurance[A[i]][0] = 1;
			occurance[A[i]][1] = i;
		}
	}

	leader = A[maxIndex];

	let equiLeader = 0;
	let stack = [];
	let stackIndex = -1;
	for (let i = 0; i < A.length; i++) {
		if (
			stack.length > Math.floor(i / 2) &&
			maxRepetition - stack.length > Math.floor((A.length - i) / 2)
		) {
			equiLeader++;
		}
		if (A[i] === leader) stack.push(i);
	}

	return equiLeader;
}