ES6 in action (or using ES6 to ease problem solving)

Hello!

In this article, I'll cover some features introduced in ECMAScript 2015 (ES6) (A bit late I know! 😅) with the help of a practice problem.

Problem Statement

MaxCounters - Codility

Calculate the values of counters after applying all alternating operations: increase counter by 1; set value of all counters to current maximum.

Not interested in the problem? Skip to the explanation of ES6 features.

SPOILER ALERT!

Below is a solution to the above problem. I highly encourage you to solve the problem yourself before reading more.

Solution

/**
 * @param {number} N Number of counters
 * @param {number[]} A Operations to be performed on the counters
 * @returns {number[]} Counters after operations
 */
function solution(N, A) {
    // Generators
    const arrSplits = (function* () {
        // Map
        let split = new Map();
        // for...of
        for (const x of A) {
            if (x === N + 1) {
                yield split;
                split = new Map();
            } else {
                split.set(x, (split.get(x) || 0) + 1);
            }
        }
        return split;
    })();

    let max = 0;
    // Object destructuring assignment
    let { value: split, done } = arrSplits.next();
    while (!done) {
        // Spread operator
        max += split.size ? Math.max(...split.values()) : 0;
        ({ value: split, done } = arrSplits.next());
    }

    // Array.from
    const counters = Array.from({ length: N }, () => max);
    // Array destructuring assignment
    for (const [x, c] of split) {
        counters[x - 1] += c;
    }
    return counters;
}

Explanation of solution

Time Complexity: O(N + M)

Space Complexity: O(N + K); K = No. of distinct elements in A

Algorithm

1. Define a generator that splits the input array of operations A into sub-arrays delimited by the N + 1 element.
   
   In other words, this generator function will yield a Map containing occurrences of the all the elements in that sub-array, whenever it encounters the N + 1 element.

2. Declare two variables – max, to store the running maximum, and split, to store the current sub-array.

3. Iterate over the generated sub-arrays and compute the max as the maximum of the occurrences in the sub-array (split).
   
   Note that we iterate over the operation array only till the last maxCounter operation.

4. Construct the counters array with all values initialized to the computed max.

5. The remaining operations in A are stored in the last sub-array (split).
   
   Perform these operations as we would have done if we were to solve this problem naively.

Example

Let's take the sample test case as an example.

solution(5, [3, 4, 4, 6, 1, 4, 4]) // => [3, 2, 2, 4, 2]

The first Map yielded is Map { 3 => 1, 4 => 2 }

At this point, max === 2.

There is only one N + 1 element at index 3 which means that the generator is exhausted.

At this point, max === 2 and split is Map { 1 => 1, 4 => 2 }.

Logic

Well, that was the how. Let's talk about the why.

The first thing you might notice after reading the problem statement is that the performing the maxCounter operation essentially resets the counters with the only difference being the counters' value.

At the start, the counters are [0, 0, 0, 0, 0].

After the maxCounter operation at index 3, the counters become [2, 2, 2, 2, 2].

As mentioned earlier, we exploit this behavior by keeping track of only the running maximum value (max) and the counters in the sub-array that is being iterated (split).

Then, it's only a matter of handling edge cases and voila! We have solved the problem!

ES6 Features

Below is a summary of the ES6 features that are used in the above solution.

Generators

Generators are objects that are returned by generator functions (defined using the function* syntax). These objects are special in that they are an iterable as well as an iterator.

From the MDN page on iteration protocols,

The iterable protocol allows JavaScript objects to define or customize their iteration behavior.

The iterator protocol defines a standard way to produce a sequence of values (either finite or infinite), and potentially a return value when all values have been generated.

What this means is that a generator, because it is an iterable, can be passed to any APIs, functions or syntaxes that can accept or expect iterables. These include but aren't limited to Set([iterable]), Array.from(), and for...of loops.

Also, because it is also an iterator. It can be used to generate finite or infinite sequences. This is especially useful for streaming algorithms that operate over one element or a chunk of elements of a sequence at a time.

Reference: function* - JavaScript | MDN

Map

Maps are the JS version of hash tables/maps. Before Maps, Objects were used to serve the same purpose.

MDN has an excellent comparison between Objects and Maps.

The key difference that make Maps preferable to Objects are the ability to iterate effortlessly.

With Objects, you have to explicitly obtain the keys of an Object and which will include any custom properties in the prototype chain.

With Maps, it's just a matter of iterating it directly as it conforms to the above mentioned iterable protocol.

There are also WeakMaps which can be used to save memory if retaining the keys that are not referenced anymore elsewhere (AKA garbage collected) is not necessary.

Sets and WeakSets are the other sibling objects that are implemented using hash tables.

Reference: Map - JavaScript | MDN

for...of

The for...of statement creates a loop iterating over iterable objects

There is also the for...in statement which has acts a bit differently.

The for...in statement iterates over the enumerable properties of an object, in an arbitrary order.

What this means is that if you use for (const x in iterable), you will end up iterating over the iterable's properties as well as any custom properties defined on its prototype chain.

The for...of statement iterates over values that the iterable object defines to be iterated over.

Simple enough. If you use for (const x of iterable), you will only iterate over those values that the iterable's iterator allows you to iterate.

Reference: for...of - JavaScript | MDN

Destructuring assignment

Destructuring assignment allows you to unpack values from inside objects into distinct variables.

This is an idea that, I think, comes from constraint-based programming and from pattern matching syntaxes in functional programming languages like Haskell.

The MDN page on this (linked below), provides extensive and well-written examples. My favorite use case is the one where you can use it to emulate GraphQL-like selectivity to only get the information from an object that you want.

const user = {
    givenName: 'Siddhesh',
    familyName: 'Mhadnak',
    age: '22',
    subscriptions: [{
        name: 'netflix',
        paid: true
    }]
};

const {
    givenName: firstName, // rename
    age, // implicit
    subscriptions: [{
        name: subscriptionName, // rename
    }]
} = user;

console.info(firstName); // => "Siddhesh"
console.info(age) // => 22
console.info(subscriptionName); // => "netflix"

Reference: Destructuring assignment - JavaScript | MDN

Spread syntax

Spread and its sibling, rest syntax, can be used to expand and condense an iterable respectively.

It is useful when we have an iterable and we want to pass it to a function that only accepts distinct parameters such as Math.max, Math.min, etc.

The idiomatic way to do this before spread syntax was to use f.apply(null, args). But, with spread syntax, it is as simple as f(...args).

An important thing to note, when using spread syntax to copy a deep object, is that spread only goes one level deep.

const c = { a: { b: 1 } };
const d = { ...c };
d.a.b = 2;
console.info(c.a.b); // => 2

Reference: Spread syntax - JavaScript | MDN

Array.from

The Array.from() method creates a new, shallow-copied Array instance from an array-like or iterable object.

As you'd expect from a named constructor, it essentially constructs an Array from the passed iterable.

But, what do you mean by array-like? An array-like object means an object that has a length property.

const arr = Array.from({ 0: "Hello", 1: "World", length: 2 });
console.info(arr.join(", ")); // => "Hello, World"

This can be useful when we want to construct an Array of known length and want to pre-fill it with values using some logic.

Array.from({ length: 5 }, (v, i) => i + 1); // => [1, 2, 3, 4, 5]

Reference: Array.from() - JavaScript | MDN

Thanks for reading 😊!