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
Define a generator that splits the input array of operations
A
into sub-arrays delimited by theN + 1
element.
In other words, this generator function willyield
aMap
containing occurrences of the all the elements in that sub-array, whenever it encounters theN + 1
element.Declare two variables β
max
, to store the running maximum, andsplit
, to store the current sub-array.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 lastmaxCounter
operation.Construct the
counters
array with all values initialized to the computedmax
.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,
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
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.
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 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 and WeakSet
s 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 π!
Top comments (0)