LeetCode 30 Days of JavaScript¶
Introduction¶
Check the full source code, including unit tests in the Gitlab repository for this project.
Performance¶
In general, using some new ECMAScript features will result in less performant results (both in terms of execution time and memory footprint).
For example, using …spread is orders of magnitude more computationally costly than good old Array.prototype.push() to add elements to, or copying an array.
Similarly, recursion, call stack and the like are more costly (in JavaScript) than some good old for loop approaches.
Using helper functions, immutable data structures and the best coding practices regarding readability and elegance don’t always result in the most performant code.
That is why some of the problems are implemented in a few different ways. Some approach to make it more performant, and some other approaches to use a more functional programming style, immutable data structures, or some other thing we might find fun and/or useful to explore.
Closures¶
Hello¶
/**
* @returns {Function}
*/
function createHelloWorld() {
return function hello() {
return "Hello World";
};
}
Counter¶
/**
* @param {number} n
* @returns {() => number}
*/
function createCounter(n) {
var x = n;
return function counter() {
return x++;
};
}
To Be Or Not To Be (Expect)¶
/**
* @param {unknown} actual
* @returns {{
* toBe: (expected: unknown) => true | never;
* notToBe: (expected: unknown) => true | never;
* }}
*/
function expect(actual) {
return {
/**
* Checks whether `actual === expected`.
*
* @param {unknown} expected
* @throws {Error}
* @returns {true}
*/
toBe: function toBe(expected) {
if (expected !== actual)
throw Error("Not Equal");
return true;
},
/**
* Checks whether `actual !== expected`.
*
* @param {unknown} expected
* @throws {Error}
* @returns {true}
*/
notToBe: function notToBe(expected) {
if (expected === actual)
throw Error("Equal");
return true;
},
};
}
Counter II¶
/**
* Returns an object with with a few counter-related methods.
*
* - T.C: O(1).
* - S.C: O(1).
*
* @param {number} init The initial integer value for the counter.
* @returns {{
* increment: () => number;
* decrement: () => number;
* reset: () => number;
* }}
*/
function createCounter(init) {
var count = init;
return {
/**
* - T.C: O(1).
* - S.C: O(1).
*
* @returns {number}
*/
increment: function increment() {
return ++count;
},
/**
* - T.C: O(1).
* - S.C: O(1).
*
* @returns {number}
*/
decrement: function decrement() {
return --count;
},
/**
* - T.C: O(1).
* - S.C: O(1).
*
* @returns {number}
*/
reset: function reset() {
return count = init;
},
};
}
In reset(), we are doing return count = init.
We could add parenthesis around the assignment, like (count = init), but the assignment has higher precedence anyway and will happen before the value is returned.
Basic Array Transformations¶
Apply Transform Over Each Element in Array (map())¶
/**
* Applies a function to each element of the input array and returns
* a new array with the result.
*
* - T.C: O(n). Applies fn once per each element. The final time
* complexity will depend on the time complexity of the callback.
* - S.C: Same notes as for T.C.
*
* @param {unknown[]} xs
* @param {(val: number, idx: number) => unknown} fn The index of
* the current element is passed to the callback, but it is up
* to the callback to decide if it wants to use it or not.
* @returns {unknown[]}
*/
function map(xs, fn) {
var mapped = [],
x,
i;
for (i = 0; x = xs[i], i < xs.length; ++i)
mapped.push(fn(x, i));
return mapped;
}
Using …spread syntax is way costly and slower than good old Array.prototype.push().
Also, this implementation does not mutate the input array and therefore using push() is not really bad at all in this case.
Only the new array which is returned is mutated while it is being constructed, but from the client code point of view, this map() implementation is pure.
Filter Elements from Array (filter())¶
/**
* Returns a new array containing only elements from the original
* array that satisfy the predicate.
*
* - T.C: O(n). Applies `predicate` once per each element. The final
* time complexity will depend on the time complexity of the
* predicate.
* - S.C: Same notes as for T.C.
*
* @param {unknown[]} xs
* @param {(val: number, idx: number) => unknown[]} fn The index of
* the current element is passed to the predicate, but it is up
* to the predicate to decide if it wants to use it or not.
* @returns {unknown[]}
*/
function filter(xs, predicate) {
var filtered = [],
x,
i;
for (i = 0; x = xs[i], i < xs.length; ++i)
if (predicate(x, i))
filtered.push(x);
return filtered;
}
Same notes for map() apply here regarding the use of push() and a simple loop.
Array Reduce Transformation (reduce())¶
Using Good Old for Loop¶
/**
* Applies a reducing function to `xs` and returns the result.
* Returns `init` if `xs` is empty.
*
* - T.C: O(n), but final T.C will depend on T.C of reducing fn.
* - S.C: Same notes as T.C.
*
* @param {unknown[]} xs
* @param {(acc: unknown, x: unknown) => unknown} fn
* @param {unknown} init
* @returns {unknown}
*/
function reduce(xs, fn, init) {
var { length: len } = xs,
acc = init,
x,
i;
for (i = 0; x = xs[i], i < len; ++i)
acc = fn(acc, x);
return acc;
}
Using Recursion¶
const head = xs => xs[0];
const tail = xs => xs.slice(1);
const isEmpty = xs => xs.length === 0;
/**
* Applies a reducing function to `xs` and returns the result.
* Returns `init` if `xs` is empty.
*
* - T.C: O(n), but final T.C will depend on T.C of reducing fn.
* - S.C: Same notes as T.C.
*
* @param {unknown[]} xs
* @param {(acc: unknown, x: unknown) => unknown} fn
* @param {unknown} init
* @returns {unknown}
*/
function reduce(xs, fn, init) {
return (function go(acc, elems) {
return isEmpty(elems)
? acc
: go(fn(acc, head(elems)), tail(elems));
}(init, xs));
}
export { reduce };
Function Composition (compose())¶
for loop¶
/**
* Applies all functions from left to right. Works as the identity
* function if `fns` is empty.
*
* - T.C: Depends on T.C of input `fns` and `val`.
* - S.C: Same notes as T.C apply.
*
* @param {Array<Function>} fns
* @returns {(val: unknown) => unknown}
*/
function compose(fns) {
/**
* @param {unknown} val
* @returns {unknown}
*/
return function composed(val) {
var lastFnIdx = fns.length - 1,
result = val,
i;
for (i = lastFnIdx; i >= 0; --i)
result = fns[i](result);
return result;
};
}
reduceRight()¶
Solution using Array.prototype.reduceRight().
/**
* Applies all functions from left to right. Works as the identity
* function if `fns` is empty.
*
* - T.C: Depends on T.C of input `fns` and `val`.
* - S.C: Same notes as T.C apply.
*
* @param {Array<Function>} fns
* @returns {(val: unknown) => unknown}
*/
function compose(fns) {
/**
* @param {unknown} val
* @returns {unknown}
*/
return function composed(val) {
return fns.reduceRight(function reducer(acc, fn) {
return fn(acc, val);
}, val);
};
}
Return Length of Arguments Passed¶
/**
* Returns the number of arguments passed.
*
* - T.C: O(1).
* - S.C: O(1).
*
* @param {...unknown} args
* @returns {number}
*/
function argsLen(...args) {
return args.length;
}
Or, just to show it is even possible to destructure length from args:
/**
* Returns the number of arguments passed.
*
* - T.C: O(1).
* - S.C: O(1).
*
* @param {...unknown} args
* @returns {number}
*/
function argsLen(...{ length }) {
return length;
}