How to improve time complexity of this snippet?

Question

I am trying to improve the time complexity and quality of the code snippet below. I am iterating through one array to check if the element this array exists in the object, should this be true it should return the name matching the element id in the object. how can I do this without having a nested loop? Can someone tell me what I can do to make this algo better, please?

Thank you all in advance.

let genres = [28, 12, 878];
data = {
  genres: [
    {
      id: 28,
      name: 'Action',
    },
    {
      id: 12,
      name: 'Adventure',
    },
    {
      id: 16,
      name: 'Animation',
    },
    {
      id: 35,
      name: 'Comedy',
    },
    {
      id: 80,
      name: 'Crime',
    },
    {
      id: 99,
      name: 'Documentary',
    },
    {
      id: 18,
      name: 'Drama',
    },
    {
      id: 10751,
      name: 'Family',
    },
    {
      id: 14,
      name: 'Fantasy',
    },
    {
      id: 36,
      name: 'History',
    },
    {
      id: 27,
      name: 'Horror',
    },
    {
      id: 10402,
      name: 'Music',
    },
    {
      id: 9648,
      name: 'Mystery',
    },
    {
      id: 10749,
      name: 'Romance',
    },
    {
      id: 878,
      name: 'Science Fiction',
    },
    {
      id: 10770,
      name: 'TV Movie',
    },
    {
      id: 53,
      name: 'Thriller',
    },
    {
      id: 10752,
      name: 'War',
    },
    {
      id: 37,
      name: 'Western',
    },
  ],
};

const getGenreName = () => {
  let result = [];
  for (let genre of data.genres) {
    //console.log("genre", genre.name)
    for (let id of genres) {
      //console.log('id',genres[i])
      if (id === genre.id) result.push(genre.name);
    }
  }
  console.log(result);
};

getGenreName();

Hi @derpirscher, thanks for helping, id of genres refers to genres [ 28,12,878] — Leo
– Leo, Commented Jan 30, 2022 at 8:14

derpirscher · Accepted Answer · 2022-01-30 08:49:50Z

3

You can use reduce and includes as others have already shown. This will make the code a bit cleaner, but not change the overall runtime complexity. To improve runtime complexity you may need to use a different data structure.

For instance instead of

let genres = [1,2,3,4];

as a simple array, you could use a Set, which has a better lookup performance.

let genres = new Set([1,2,3,4]);

Then you can use this as follows

let result = data.genres
 .filter(g => genres.has(g.id))
 .map(g => g.name);

and won't need any explict for loops

edited Jan 30, 2022 at 8:49

answered Jan 30, 2022 at 8:25

derpirscher

17.7k3 gold badges25 silver badges54 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jonas Høgh · Accepted Answer · 2022-01-30 08:14:51Z

2

The simplest improvement would probably be converting genres to a Set https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set and use the has method to check if each id in the data is a member of the set of chosen genres.

You can also convert the data to a map with the ids as the keys in order to look up by id quickly instead of looping, but that is only faster if the data is reused many times.

answered Jan 30, 2022 at 8:14

Jonas Høgh

10.9k1 gold badge29 silver badges49 bronze badges

Comments

Rida F'kih · Accepted Answer · 2022-01-30 08:30:33Z

2

JavaScript #reduce in the example outlined below would have O(n) time complexity. This only loops through the array once. We could use filter, and map but it would result in us having to loop through the array twice.

const getGenreName = () => {
    const genreSet = new Set(genres);
    return data.genres.reduce((accumulator, { id, name }) => {
        if (genreSet.has(id)) accumulator.push(name);
        return accumulator;
    }, []);
};

console.log(getGenreName()); // [ 'Action', 'Adventure', 'Science Fiction' ]

We are initializing the reducer to start with the array [], or an empty array, and then checking to see if the genre property of the object is included in the genres array, if it isn't, return the accumulator, if it is, append it to the end of the accumulator and return it.

edited Jan 30, 2022 at 8:30

answered Jan 30, 2022 at 8:15

Rida F'kih

2561 silver badge7 bronze badges

5 Comments

derpirscher Over a year ago

Eventhough you are hiding the loops behind reduce and includes your snippet has exact the sampe runtime complexity as OPs code. Because internally reduce has also to itererate all elements of data.genres and genres.includes traverses the elements of genres in each iteration

Jonas Høgh Over a year ago

This will still be O(m * n) where m is the size of genres, as includes will iterate over that array internally

Rida F'kih Over a year ago

@derpirscher Good point, thank you for outlining. In order to get around includes iteration, I've gone ahead and switched the answer to use Set, since has uses O(1) rather than the includes which has O(n).

Leo Over a year ago

thank you all for your contributions. I don't understand the accumulator I will search about this so i can understand it better @RidaF'kih

Rida F'kih Over a year ago

@JonasHøgh Thank you both for the fantastic point, I've made a couple improvements. Feel free to review. I've switched the answer to use Array push, as spread operator has time complexity of O(n), versus push having O(1), and switched to casting the array to a Set, then using has in order to check for presence, reducing from O(n) of includes to the O(1)` of `has.

swamp · Accepted Answer · 2022-01-30 08:16:21Z

1

You wanted this in one loop, so here it is:

let result = [];
data.genres.forEach(function (e) {
  if (genres.includes(e.id)) result.push(e.name);
});
console.log(result);

In case you were wondering about forEach, here's a very good reference: https://www.w3schools.com/jsref/jsref_foreach.asp

answered Jan 30, 2022 at 8:16

swamp

4061 gold badge3 silver badges9 bronze badges

1 Comment

Rida F'kih Over a year ago

With this solution, forEach has time complexity of O(n), and so does Array includes, which also has time complexity of O(n), so this solutions overall time complexity, similarly to my previous solution prior to my edits, is O(m * n).

6e23 · Accepted Answer · 2022-01-30 09:02:39Z

0

The current time complexity is O(MN) where M is the length of data.genres and N is the length of genres. Time complexity in JavaScript depends on which engine you use, but in most cases you can use a Map to reduce this time complexity to O(max{N,M}):

const getGenreName = () => {
  const dataGenresMap = new Map( // O(M)
    data.genres.map(({id,...params}) => [id,params]) // O(M)
  )
  let result = []
  for (let id of genres) { // O(N)
    if (dataGenresMap.has(id)) result.push(dataGenresMap.get(id).name) // O(1)
  }
  console.log(result)
}

answered Jan 30, 2022 at 9:02

6e23

214 bronze badges

Comments

JSmart523 · Accepted Answer · 2022-01-30 09:40:43Z

If you might be doing this more than once then I'd recommend using a Map. By creating a hash map, retrieving genre names per id is much more performant.

  let genres = [28, 12, 878];
  data = {
    genres: [
      {
        id: 28,
        name: 'Action',
      },
      {
        id: 12,
        name: 'Adventure',
      },
      {
        id: 16,
        name: 'Animation',
      },
      {
        id: 35,
        name: 'Comedy',
      },
      {
        id: 80,
        name: 'Crime',
      },
      {
        id: 99,
        name: 'Documentary',
      },
      {
        id: 18,
        name: 'Drama',
      },
      {
        id: 10751,
        name: 'Family',
      },
      {
        id: 14,
        name: 'Fantasy',
      },
      {
        id: 36,
        name: 'History',
      },
      {
        id: 27,
        name: 'Horror',
      },
      {
        id: 10402,
        name: 'Music',
      },
      {
        id: 9648,
        name: 'Mystery',
      },
      {
        id: 10749,
        name: 'Romance',
      },
      {
        id: 878,
        name: 'Science Fiction',
      },
      {
        id: 10770,
        name: 'TV Movie',
      },
      {
        id: 53,
        name: 'Thriller',
      },
      {
        id: 10752,
        name: 'War',
      },
      {
        id: 37,
        name: 'Western',
      },
    ],
  };
  
  const genreById = new Map ();
  data.genres.forEach(({id, name}) => genreById.set(id, name));
  
  const pushMapValueIfTruthy = map => array => key => {
    const val = map.get(key);
    if (val) {
      array.push(val);
    }
  };
  
  /** function that takes an array, then id, and pushes corresponding name (if exists) into the array. */
  const pushGenreNaneIfExists = pushMapValueIfTruthy(genreById);
  
  const getGenreNames = (ids) => {
    result = [];
    ids.forEach(pushGenreNaneIfExists(result));
    return result;
  };
  
  console.log(getGenreNames(genres));

Collectives™ on Stack Overflow

How to improve time complexity of this snippet?

6 Answers 6

Comments

Comments

5 Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

5 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related