Lessons from codility.com

01 - BinaryGap.js

// https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

function solution(N) {
	return N.
		toString(2).
		split(/1+|1*0*$/g).
		reduce((acc, cur) => Math.max(acc, cur.length), 0);

		// const str = N.toString(2);
		// let maxGap = 0;
		// let gap = 0;
		// for (let i = 0; i < str.length; i++) {
		// 	if (str[i] === "0") {
		// 		gap++;
		// 	} else {
		// 		maxGap = Math.max(gap, maxGap);
		// 		gap = 0;
		// 	}
		// }
		// return maxGap;
}

02 - CyclicRotation.js

// https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

function solution(A, K) {
	for (let i = 0, steps = A.length > 0 ? K : 0; i < steps; i++) {
		A.unshift(A.pop());
	}
	return A;
}

02 - OddOccurrencesInArray.js

// https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

function solution(A) {
	return A.reduce((acc, cur) => acc ^ cur)
}

03 - FrogJmp.js

// https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/

function solution(X, Y, D) {
	return Math.ceil((Y - X) / D)
}

03 - PermMissingElem.js

// https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

function solution(A) {
	return A.reduce((acc, cur, index) => acc + index + 1 - cur, A.length + 1)
}

03 - TapeEquilibrium.js

// https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

function solution(A) {
	const sum = A.reduce((acc, cur) => acc + cur, 0);
	let sumLeft = 0;
	let minDiff = 0;
	let i, diff;
	for (i = 0; i < A.length - 1; i++) {
		sumLeft += A[i];
		diff = Math.abs(sum - 2 * sumLeft);
		if (i === 0 || diff < minDiff) {
			minDiff = diff;
		}
	}
	return minDiff;
}

04 - FrogRiverOne.js

// https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

function solution(X, A) {
	const leaves = new Array(X);

	for (let remaining = X, i = 0; i < A.length; i++) {
		const pos = A[i];
		if (pos < 1 || pos > X || leaves[pos - 1]) {
			continue;
		}

		leaves[pos - 1] = 1;
		remaining -= 1;
		
		if (remaining === 0) {
			return i;
		}
	}
	
	return -1;
}

04 - MaxCounters.js

// https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/

function solution(N, A) {
	// O(N+M)
	const counters = new Array(N).fill(0);
	let maxCounter = 0;
	let minValue = 0;
	A.forEach(k => {
		if (k <= N) {
			counters[k - 1] = Math.max(minValue, counters[k - 1]) + 1;
			maxCounter = Math.max(maxCounter, counters[k - 1]);
		} else {
			minValue = maxCounter;
		}
	});
	counters.forEach((v, i) => counters[i] = Math.max(v, minValue));
	return counters;

	// // O(N*M)
	// const counters = new Array(N).fill(0);
	// let maxCounter = 0;
	// A.forEach(k => {
	// 	if (k <= N) {
	// 		maxCounter = Math.max(maxCounter, ++counters[k - 1]);
	// 	} else {
	// 		counters.fill(maxCounter);
	// 	}
	// });
	// return counters;    
}

04 - MissingInteger.js

// https://app.codility.com/programmers/lessons/4-counting_elements/missing_integer/

function solution(A) {
	const N = A.length;

	const seen = new Array(N);
	A.forEach(val => val >= 1 && val <= N && (seen[val - 1] = 1));

	const res = seen.findIndex(v => !v);
	return (res !== -1 ? res : N) + 1;
}

04 - PermCheck.js

// https://app.codility.com/programmers/lessons/4-counting_elements/perm_check/

function solution(A) {
	const vals = new Array(A.length);
	for (let val of A) {
		if (val < 1 || val > A.length || vals[val-1]) {
			return 0;
		}
		vals[val - 1] = 1;
	}
	return 1;
}

05 - CountDiv.js

// https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/

function solution(A, B, K) {
	return Math.trunc(B / K) - 
		(A > 0 ? Math.trunc((A - 1) / K) : -1);
}

05 - GenomicRangeQuery.js

// https://app.codility.com/programmers/lessons/5-prefix_sums/genomic_range_query/

function solution(S, P, Q) {
	const TYPES_SORTED = ["A", "C", "G", "T"]; // types sorted by impact value asc, impact = index + 1
	const N = S.length;
	const M = P.length;

	const counter = {};
	TYPES_SORTED.forEach(val => counter[val] = 0);

	const prefixSums = new Array(N);
	const result = new Array(M);

	for (let i = 0; i < N; i++) { // O(N)
		counter[S[i]]++;
		prefixSums[i] = { ...counter};
	}

	for (let i = 0; i < M; i++) { // O(M)
		const fromIndex = P[i];
		const toIndex = Q[i];
		for (let typeIndex = 0; typeIndex < TYPES_SORTED.length; typeIndex++) {
			const type = TYPES_SORTED[typeIndex];
			const fromSum = (fromIndex > 0 ? prefixSums[fromIndex - 1][type] : 0);
			const toSum = prefixSums[toIndex][type];
			if (toSum - fromSum > 0) {
				result[i] = typeIndex + 1;
				break;
			}
		}
	}

	return result;
}

05 - MinAvgTwoSlice.js

// https://app.codility.com/programmers/lessons/5-prefix_sums/min_avg_two_slice/

function solution(A) {
	const N = A.length;
	let minAvg = 0;
	let minAvgIndex = 0;
	for (let i = 0; i + 1 < N; i++) {
		let avg = (A[i] + A[i + 1]) / 2;
		if (i + 2 < N) {
			avg = Math.min(avg, (avg * 2 + A[i+2]) / 3);
		}
		if (avg < minAvg || i === 0) {
			minAvg = avg;
			minAvgIndex = i;
		}
	}
	return minAvgIndex;
}

05 - PassingCars.js

// https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

function solution(A) {
	const MAX_RESULT = 1e9;
	let eastCount = 0;
	let result = 0;
	for (let val of A) {
		if (val === 0) {
			eastCount++;
		} else {
			result += eastCount;
			if (result > MAX_RESULT) {
				return -1;
			}
		}
	}
	return result;
}

06 - Distinct.js

// https://app.codility.com/programmers/lessons/6-sorting/distinct/

function solution(A) {
	const sortedA = A.slice().sort(); // O(N*log(N))
	let lastVal = 0;
	let result = 0;
	for (let val of sortedA) { // O(N)
		if (val !== lastVal || result === 0) {
			result++;
			lastVal = val;
		}
	}
	return result;
}

06 - MaxProductOfThree.js

// https://app.codility.com/programmers/lessons/6-sorting/max_product_of_three/

function solution(A) {
	const N = A.length;

	A.sort((a, b) => a - b);
	return Math.max(
		A[N - 3] * A[N - 2] * A[N - 1],
		A[0] * A[1] * A[N - 1]
	);
}

06 - NumberOfDiscIntersections.js

// https://app.codility.com/programmers/lessons/6-sorting/number_of_disc_intersections/

function solution(A) {
	const MAX_RESULT = 1e7;
	const points = [];

	A.forEach((radius, index) => points.push(
		{ point: index - radius, isStart: 1 },
		{ point: index + radius, isStart: 0 },
	));

	points.sort((a, b) => (a.point - b.point) || (a.isStart ? -1 : 1));

	let result = 0;
	let startedDiscs = 0;

	for (let point of points) {
		if (!point.isStart) {
			startedDiscs--;
			continue;
		}
		result += startedDiscs;
		startedDiscs++;
		if (result > MAX_RESULT) {
			return -1;
		}
	}

	return result;
}

06 - Triangle.js

// https://app.codility.com/programmers/lessons/6-sorting/triangle/

function solution(A) {
	const N = A.length;
	A.sort((a, b) => a - b);

	for (let i = 0; i + 2 < N; i++) {
		if (A[i] + A[i+1] > A[i+2]) {
			return 1;
		}
	}
	return 0;
}

07 - Brackets.js

// https://app.codility.com/programmers/lessons/7-stacks_and_queues/brackets/

function solution(S) {
	const CLOSING_BY_OPENING = {
		"{": "}",
		"[": "]",
		"(": ")",
	};

	const stack = [];
	for (let i = 0; i < S.length; i++) {
		const c = S[i];
		if (CLOSING_BY_OPENING.hasOwnProperty(c)) {
			stack.push(CLOSING_BY_OPENING[c]);
		} else if (stack.length === 0 || stack[stack.length - 1] !== c) {
			return 0;
		} else {
			stack.pop();
		}
	}
	return (stack.length === 0 ? 1 : 0);
}

07 - Fish.js

// https://app.codility.com/programmers/lessons/7-stacks_and_queues/fish/

function solution(A, B) {
	const N = A.length;
	const flowingDownSizes = [];
	let aliveUpCount = 0;

	for (let i = 0; i < N; i++) {
		const size = A[i];
		const dir = B[i];
		if (dir === 1) {
			flowingDownSizes.push(size);
			continue;
		}
		while (flowingDownSizes.length > 0 && flowingDownSizes[flowingDownSizes.length - 1] < size) {
			flowingDownSizes.pop();
		}
		if (flowingDownSizes.length === 0) {
			aliveUpCount++;
		}
	}
	return aliveUpCount + flowingDownSizes.length;
}

07 - Nesting.js

// https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

function solution(S) {
	let open = 0;
	for (let i = 0; i < S.length; i++) {
		const c = S[i];
		if (c === "(") {
			open++;
		} else if (open === 0) {
			return 0;
		} else {
			open--;
		}
	}
	return (open === 0 ? 1 : 0);
}

07 - StoneWall.js

// https://app.codility.com/programmers/lessons/7-stacks_and_queues/stone_wall/

function solution(H) {
	const stack = [];
	let result = 0;
	for (let i = 0; i < H.length; i++) {
		const h = H[i];
		while (stack.length && stack[stack.length - 1] > h) {
			stack.pop();
		}
		if (!stack.length || stack[stack.length - 1] < h) {
			stack.push(h);
			result++;
		}
	}
	return result;
}

08 - Dominator.js

// https://app.codility.com/programmers/lessons/8-leader/dominator/

function solution(A) {
	const N = A.length;
	let candidate = 0;
	let candidateCount = 0;

	for (let val of A) {
		if (candidateCount === 0 || candidate === val) {
			candidate = val;
			candidateCount++
		} else {
			candidateCount--;
		}
	}

	if (candidateCount === 0) {
		return -1;
	}

	candidateCount = 0;
	for (let i = 0; i < A.length; i++) {
		if (A[i] === candidate) {
			candidateCount++;
			if (candidateCount > N / 2) {
				return i;
			}
		}
	}

	return -1;
}

08 - EquiLeader.js

// https://app.codility.com/programmers/lessons/8-leader/equi_leader/

function solution(A) {
	const N = A.length;

	let leader = 0;
	let count = 0;
	let equiLeaders = 0;

	for (let val of A) {
		if (count === 0 || leader === val) {
			leader = val;
			count++;
		} else {
			count--;
		}
	}

	if (count === 0) {
		return 0;
	}

	count = 0;
	for (let i = 0; i < N; i++) {
		if (A[i] === leader) {
			count++;
		}
	}

	if (count <= N / 2) {
		return 0;
	}

	for (let i = 0, leftLeaders = 0; i < N; i++) {
		if (A[i] === leader) {
			leftLeaders++;
		}
		const leftItems = i + 1;
		const rightItems = N - leftItems;
		const rightLeaders = count - leftLeaders;

		if (leftLeaders > leftItems / 2 && rightLeaders > rightItems / 2) {
			equiLeaders++;
		}
	}

	return equiLeaders;
}