Question 167595 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – How to iterate over 2 large array of objects in typescript efficiently

I have 2 sample arrays as below

var marks=[{"id":1,"marks":null,"grade":"A"},{"id":1,"marks":90,"grade":null},{"id":1,"marks":90,"grade":"A"},{"id": 2, "marks": 65, "grade":"B"}]
var student=[{"id":1,"name":"john"},{"id": 2, "name": "anna"}]

in real-time the length of student array is close to 1000 and length of marks array is close to 10000. I have to iterate through them and check if id is same and then add first non-null marks and grade field in the student array . We cannot group on the id and merge the 2 arrays as we need to eliminate null values.
I have took the standard approach of using loops but the complexity is order of n*m. How to optimize it?
The result be as follows

var student=[{"id":1,"name":"john","marks":90,"grade":"A"},{"id": 2, "name": "anna", "marks": 65, "grade":"B"}]
Tags:

2

Answers


  1. 0

    To find matches between the marks and student arrays, you can use a nested loop to compare the id property of each object in both arrays. However, to optimize the loop for efficiency, you can use a hash table to store the id property of each student object as the key, and the index of the object in the student array as the value. Then, you can loop through the marks array, and for each object, check if there is a corresponding student object using the hash table. This will reduce the time complexity from O(n^2) to O(n).

    var marks=[{"id":1,"marks":null,"grade":"A"},{"id":1,"marks":90,"grade":null},{"id":1,"marks":90,"grade":"A"},{"id": 2, "marks": 65, "grade":"B"}]
var students=[{"id":1,"name":"john"},{"id": 2, "name": "anna"}]

// Create a map of student IDs
const studentMap = new Map(students.map((student) => [student.id, student]));

// Loop through marks and find matching students
marks.filter(mark => mark.marks && mark.grade)
     .map(mark => {
       const student = studentMap.get(mark.id);
       if (student) {
         // Execute your code here
         console.log(`${student.name} scored ${mark.marks} and got a grade of ${mark.grade}`);
     }
});
    Login or Signup to reply.
  2. 0

    Convert students into a Map (O(n)), and use it as the accumulator for the reduce:

    new Map(student.map(o => [o.id, { ...o }]))

    Then reduce the marks (O(m)). Get the student from the accumulator (m), and if grade or marks are not not null assign them to the student using Nullish coalescing assignment (??=) to avoid updating an existing property:

    if(grade !== null) student.grade ??= grade;
if(marks !== null) student.marks ??= marks;

    The complexity is O(n) + O(m) => O(n + m).

    Example (TS playground):

    const marks=[{"id":1,"marks":null,"grade":"A"},{"id":1,"marks":90,"grade":null},{"id":1,"marks":90,"grade":"A"},{"id": 2, "marks": 65, "grade":"B"}]
const students =[{"id":1,"name":"john"},{"id": 2, "name": "anna"}]

const result = Array.from(marks.reduce((m, { id, marks, grade }) => {
    const student = m.get(id)

    if(!student) return m

    if(grade !== null) student.grade ??= grade;
    if(marks !== null) student.marks ??= marks;

    return m
  }, new Map(students.map(o => [o.id, { ...o }])))
  .values()
)

console.log(result)
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search