I have two array of objects (users and deposits).
const users = [
{
_id: 1,
username: 'tajmirul',
email: 'tajmirul@gmail.com',
},
{
_id: 2,
username: 'tajmirul2',
email: 'tajmirul2@gmail.com',
},
];
const deposits = [
{
_id: 1,
userId: 1,
amount: 250,
},
{
_id: 2,
userId: 1,
amount: 500,
},
];
I want to calculate total deposit for each user and update the users array. like this
// modified users array will look like this
[
{
_id: 1,
username: 'tajmirul'
deposit: 750,
},
{
_id: 2,
username: 'tajmirul2'
deposit: 0,
}
]
I tried this
users.forEach((user, index) => {
deposits.forEach(deposit => {
if (user._id === deposit.userId) {
if (users[index].deposit) {
users[index].deposit += deposit.amount;
} else {
users[index].deposit = deposit.amount;
}
}
});
});
In this case, the time complexity is O(m * n). Is there any way to reduce the time complexity?
You can create a hash map and index deposits by user Ids.
This gives you O(m)
Size of Users = n, Size of Deposits = m
After that, you can iterate over users and that would be O(n)
In the end, the time complexity will be O(MAX(m,n))
const users = [
{
_id: 1,
username: 'tajmirul',
email: 'tajmirul@gmail.com',
},
{
_id: 2,
username: 'tajmirul2',
email: 'tajmirul2@gmail.com',
},
];
const deposits = [
{
_id: 1,
userId: 1,
amount: 250,
},
{
_id: 2,
userId: 1,
amount: 500,
},
];
const depositsMap = new Map();
for (const deposit of deposits) { // O(m)
if (depositsMap.has(deposit.userId)) {
const prevDeposit = depositsMap.get(deposit.userId);
depositsMap.set(deposit.userId, prevDeposit + deposit.amount);
} else {
depositsMap.set(deposit.userId, deposit.amount ?? 0);
}
}
const aggregatedUsers = users.map(user => { // O(n)
return {
_id: user._id,
username: user.username,
deposit: depositsMap.get(user._id) ?? 0,
};
});
console.log(aggregatedUsers);You might first reduce the deposits to {userId:total} which is say O(n),
then update the users which is O(m):
const users = [
{
_id: 1,
username: 'tajmirul',
email: 'tajmirul@gmail.com',
},
{
_id: 2,
username: 'tajmirul2',
email: 'tajmirul2@gmail.com',
},
];
const deposits = [
{
_id: 1,
userId: 1,
amount: 250,
},
{
_id: 2,
userId: 1,
amount: 500,
},
];
const userDeposits = deposits.reduce((a, {userId, amount}) => (a[userId] = (a[userId] || 0) + amount, a), {}) // O(n)
users.forEach(u => u.amount = userDeposits[u._id] || 0) // O(m)
console.log(users).as-console-wrapper {
top: 0;
max-height: none !important;
}const usersWithAmount = users.map((user) => {
const { _id } = user;
const depositsFiltered = deposits.filter(({ userId }) => userId === _id);
if (depositsFiltered.length > 0) {
return {
...user,
deposit:
(user?.deposit ?? 0) +
depositsFiltered.reduce((acc, { amount }) => (acc + amount), 0),
};
}
return { ...user, amount: 0 };
});