ES6 in action (or using ES6 to ease problem solving)
Tags: javascript
Published: 2019-09-05 17:35:21

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](https://app.codility.com/programmers/lessons/4-counting_elements/max_counters)  
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](#es6-features) 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
```js
/**
 * @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 &ndash; `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` `yield`ed 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/function*)

## Map
`Map`s are the JS version of hash tables/maps. Before `Map`s, `Object`s were used to serve the same purpose.

MDN has an excellent [comparison between `Object`s and `Map`s](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map#Objects_and_maps_compared).  
The key difference that make `Map`s preferable to `Object`s are the ability to iterate effortlessly.

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

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

There are also [`WeakMap`s](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakMap) which can be used to save memory if retaining the keys that are not referenced anymore elsewhere (AKA garbage collected) is not necessary.

[`Set`s](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set) and [`WeakSet`s](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/WeakSet) are the other sibling objects that are implemented using hash tables.

Reference: [Map - JavaScript | MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map)

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

There is also the [for...in statement](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...in) 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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...of)

## 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.

```js
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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment)

## 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.

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

Reference: [Spread syntax - JavaScript | MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Spread_syntax)

## 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.

```js
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.

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

Reference: [Array.from() - JavaScript | MDN](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from)

Thanks for reading 😊!