How to bring the json structure to linear time complexity?

Eugen Sunic 0
Viewed 59

Input json:

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}

desired output

{
  "38931": {
    "13424": {
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample"
      }
    },
    "19999": {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample"
      }
    }
  },
  "77777": {
    "55555": {
      "userT": "z",
      "personId": 55555,
      "user": {
        "id": 77777,
        "email": "sample"
      }
    }
  }
}

This is what I tried to bring it to O(n), but still the destructuring in the reducer will give me O(n2) which is in the last .reducer func with callback accObject.

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}


const accList = (acc, id) => {
  acc.push(i[id]);
  return acc;
}
const accObject = (acc, [key, val]) => {
  const {
    user: {
      id
    }
  } = val;
  acc[id] = {
    ...acc[id],
    [key]: val
  };
  return acc;
}

// concat arrays of main object (i) 2D array, transform to 1D array, 
// transform to hashMap with key personId,
// transform to array for iterable (Object.entries) and create the object result.

const personas = Object.keys(i)
  .reduce(accList, [])
  .flat()
  .reduce((acc, obj) => {
    acc[obj.personId] = obj;
    return acc;
  }, {});

const result =
  Object
  .entries(personas)
  .reduce(accObject, {});

console.log('result', result);

It does give me the correct result, but am wondering if there is a bette approach to have

T = O(n)

time-complexity reduce json algorithm javascript
1 Answers

I think you can do this with a single iteration over the entries in the top-level object, converting the array of objects under each key into an object using Object.fromEntries:

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}

const result = Object.fromEntries(Object.entries(i)
  .map(([k, v]) => [k,
    Object.fromEntries(v.map(o => [o.personId, o]))
  ])
)

console.log(result)
.as-console-wrapper { max-height: 100% !important; top 0; }

If you don't mind modifying the object in place, you can use a simple forEach:

const i = {
  "38931": [{
      "userT": "z",
      "personId": 13424,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    },
    {
      "userType": "z",
      "personId": 19999,
      "user": {
        "id": 38931,
        "email": "sample",
      },
    }
  ],
  "77777": [{
    "userT": "z",
    "personId": 55555,
    "user": {
      "id": 77777,
      "email": "sample",
    },
  }]
}

Object.keys(i).forEach(k => i[k] = Object.fromEntries(i[k].map(o => [o.personId, o])))

console.log(i)
.as-console-wrapper { max-height: 100% !important; top 0; }

usergAKD0
Related