Solution to Codility's MinAbsSum problem

codility-minabssum.ts

/**
 * This is a TypeScript solution to Codility's MinAbsSum problem.
 * Based on the official Python solution, but altered with my own logic:
 * https://codility.com/media/train/solution-min-abs-sum.pdf
 */

const reduceToAbsMax = (n: number, o: number): number =>
    Math.max(n, Math.abs(o));

const reduceToAbsSum = (n: number, o: number): number =>
    n + Math.abs(o);

function solution(A: number[]): number {
    if (A.length === 0) {
        return 0;
    }

    // O(N)
    const count: number[] = [];
    for (const a of A) {
        const absA: number = Math.abs(a);
        count[absA] = (count[absA] ?? 0) + 1;
    }

    // O(N)
    const max: number = A.reduce(reduceToAbsMax, 0);

    // O(N)
    const sum: number = A.reduce(reduceToAbsSum, 0);
    const halfSum: number = sum / 2;
    const halfSumCeil: number = Math.ceil(halfSum);
    const halfSums: Set<number> = new Set([
        halfSumCeil,
        Math.floor(halfSum),
    ]);

    // Dynamic programming 🤪
    const moves: number[] = [0];

    // O(Max): Move for each item in A.
    for (let move = 1; move <= max; move++) {
        // If we have no moves of this size, continue.
        if (typeof count[move] === 'undefined') {
            continue;
        }

        // O(Sum): Move from each previous space.
        for (let result = 0; result <= sum; result++) {
            // If we were already present on a space, reset moves.
            if (typeof moves[result] === 'number') {
                moves[result] = count[move];
                continue;
            }

            // If we can move to this space, set remaining moves.
            const previousMoves: number | undefined = moves[result - move];
            if (typeof previousMoves === 'undefined' || previousMoves === 0) {
                continue;
            }
            if (halfSums.has(result)) {
                return Math.ceil(halfSum % 1);
            }
            moves[result] = previousMoves - 1;
        }
    }

    // O(Sum)
    for (let i = halfSumCeil; i >= 0; i--) {
        if (typeof moves[i] !== 'number') {
            continue;
        }
        return sum - 2 * i;
    }

    return sum;
}