CODEWITHSUNDEEP
javascriptarraysobjectbig-o
Sobolishche
Sobolishche

Reputation: 13

Time complexity of iterating through array and object

I have a small application where I have an array of objects. Each object is a student and each student object has an array of tags that looks like this:

const students = 
  [ { name: "John",   tags: [ 'tag1', 'tag2' ] } 
  , { name: "Leslie", tags: [ 'tag1' ]         } 
  , { name: "Mark",   tags: [ 'tag', 'tag2' ]  }
  ]

Right now to search for students with the same tags I iterate through the array of objects and array of tags for each student which is O(n) squared.

const filterByTag = (filter) => {
  let result = [];
  initialStudents.map((student) => {
    student.tags.map((tag) => {
      if (tag.includes(filter)) {
        result.push(student);
      }
    });
  });
  return result;
};

How can I reduce time complexity? I was thinking of creating an object with name->tags and then go through it, but it seems to be the same O(n) squared.

Upvotes: 0

Views: 951

Answers (1)

CertainPerformance
CertainPerformance

Reputation: 371168

I don't think there are any significant gains to be made here, from a complexity standpoint. There's no way around iterating over

  • each student
  • each tag inside each student
  • each character inside each tag string (abstracted behind the .includes)

That requires a significant amount of computational complexity, which you're implementing pretty reasonably already.

But you can make the code a bit better and reduce a bit of unnecessary overhead. Don't use .map for side-effects - for side-effects, use forEach or for..of. But a better approach here would be to use .filter to construct a new array of student objects depending on which pass the test - since you probably only want to push a single student when it matches, rather than that student for every matching tag.

const filterByTag = (filter) => {
    return initialStudents.filter(student => 
        student.tags.some(
            tag => tag.includes(filter)
        )
    );
};

(Only use .map when you're using the result of the call as a new array - eg const mappedArray = originalArray.map(...)

Upvotes: 1

Related Questions