CODEWITHSUNDEEP
javascriptdata-structuresecmascript-6
Carolyn Cordeiro
Carolyn Cordeiro

Reputation: 1915

Longest Increasing Subsequence Problem with Javascript

I generated this code for Longest Increasing Subsequence:

var lengthOfLIS = function(nums) {
  if (nums.length === 0) return 0;
  let result = 1;
  const LISEndAt = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    LISEndAt[i] = Math.max(1,
      ...LISEndAt.slice(0, i).map((item, j) => {
        return nums[i] > nums[j] ? item + 1 : 0
      }));

    result = Math.max(LISEndAt[i], result);
  }
  
  return result;
}

let nums = [7,7,7,7,7,7,7];

console.log(lengthOfLIS(nums));

Can some one help me to understand this line:

LISEndAt[i] = Math.max(1,...LISEndAt.slice(0, i).map((item, j)

What is significance of three dots and as we know map generates key value pairs, what is map doing along with slice?

Upvotes: 0

Views: 1786

Answers (1)

D M
D M

Reputation: 7179

Clarification

Before I can explain what the line you're asking about does, there are a few things to clear up.

...

... is the spread syntax which expands the given iterable (array indices, object key-value pairs, etc). Here's an example where an existing array is used to create a new array with more elements:

const first = [1, 2, 3];
const second = [...first, 4, 5, 6];
console.log(second);
/* returns [1, 2, 3, 4, 5, 6] */

In your example, it is being used to provide multiple parameters to the Math.max() function. Here's an example of that:

const candidates = [1, 5, 6, 2, 4];
const largest = Math.max(...candidates);
console.log(largest);
/* returns 6 */

Array#map

Array#map doesn't create key/value pairs. Instead, it creates a new array by performing an action on each element in the original array. Here's an example where a new array is created by doubling each item in the original array:

const original = [1, 2, 3];
const doubled = original.map(i => i * 2);
console.log(doubled);
/* returns [2, 4, 6] */

You can also access the index of each item in the original array:

const alphabet = ['A', 'B', 'C'];
const positions = alphabet.map((letter, index) => index);
console.log(positions);
/* returns [0, 1, 2] */

Array#slice

Array#slice creates a new array that is a subset of the original array from the provided starting index until (but not including) the provided end index. Here's an example where a new array is created from the first three items of an existing array:

const superset = [1, 2, 3, 4, 5, 6];
const subset = superset.slice(0, 3);
console.log(subset);
/* returns [1, 2, 3] */

Your question

With all that in mind, let's take a look at the loop containing your line:

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
const LISEndAt = new Array(nums.length).fill(1);
/* [1, 1, 1, 1, 1, 1, 1, 1] */

for (let i = 1; i < nums.length; i++) {
    LISEndAt[i] = Math.max(1,
        ...LISEndAt.slice(0, i).map((item, j) => {
            return nums[i] > nums[j] ? item + 1 : 0;
        }));
}

LISEndAt is being updated with each iteration of your for-loop. Each time, the next index is calculated as:

  • The max of 1 and any element in:
  • The subset of LISEndAt from 0 to the current iteration of the for-loop as modified by:
  • Some comparison in map which returns either:
  • The item at the current index being modified plus one or:
  • Zero.

If we add some logging to your loop, you can see this happen in sequence:

const nums = [10, 9, 2, 5, 3, 7, 101, 18];
const LISEndAt = new Array(nums.length).fill(1);
console.log(`original: ${JSON.stringify(LISEndAt)}`);

for (let i = 1; i < nums.length; i++) {
  const subset = LISEndAt.slice(0, i);
  console.log(`sliced: [${subset.join(', ')}]`);
  const someArray = subset.map((item, j) => {
    console.log(`comparing ${nums[i]} > ${nums[j]} ? ${item + 1} : 0`);
    return nums[i] > nums[j] ? item + 1 : 0;
  });
  console.log(`taking max of 1, ${JSON.stringify(...someArray)}`);
  LISEndAt[i] = Math.max(1, ...someArray);
  console.log(`iteration ${i}: ${JSON.stringify(LISEndAt)}`);
}

Upvotes: 1

Related Questions