Efficiently tagging first and last of each object matching condition

Question

How can I make the code more readable and more efficient? (provided code is O(n²) time, but intuition says it can be pre-processed and done in O(n) time)

Description

• it tags the first and last of each object matching a condition, and removes all objects without tags
  • the input order must be preserved
  • the first match may also be the last match (see "Bobby" example)
• it must use at most ES6 functions

Input

[
    { name: "John Smith", value: 5 },
    { name: "Jane Doe", value: 3 },
    { name: "John Smith", value: 1 },
    { name: "John Smith", value: 3 },
    { name: "Jane Doe", value: 5 },
    { name: "Bobby", value: 2 },
]

Output

[
    { name: "John Smith", value: 5, tags: ["first"] },
    { name: "Jane Doe", value: 3, tags: ["first"] },
    // removed since it is not the first nor last of "John Smith": { name: "John Smith", value: 1, tags: [] },
    { name: "John Smith", value: 3, tags: ["last"] },
    { name: "Jane Doe", value: 5, tags: ["last"] },
    { name: "Bobby", value: 2, tags: ["first", "last"] },
]

Code

Only "PROCESSING" needs to be reviewed.

/* SETUP */
const arrays = [{
    name: "John Smith",
    value: 5
  },
  {
    name: "Jane Doe",
    value: 3
  },
  {
    name: "John Smith",
    value: 1
  },
  {
    name: "John Smith",
    value: 3
  },
  {
    name: "Jane Doe",
    value: 5
  },
  {
    name: "Bobby",
    value: 2
  },
]

const expectedTaggedArrays = [{
    name: "John Smith",
    value: 5,
    tags: ["first"]
  },
  {
    name: "Jane Doe",
    value: 3,
    tags: ["first"]
  },
  {
    name: "John Smith",
    value: 3,
    tags: ["last"]
  },
  {
    name: "Jane Doe",
    value: 5,
    tags: ["last"]
  },
  {
    name: "Bobby",
    value: 2,
    tags: ["first", "last"]
  },
]

/* PROCESSING */
// set all elements to have empty list of tags
let taggedArrays = arrays.map((x) => ({ ...x,
  tags: []
}))

for (let i = 0; i < taggedArrays.length; i++) {
  // function to compare for "equality"
  const hasSameName = (x) => x.name === taggedArrays[i].name

  // tag if first time name seen
  const firstMatchingIndex = taggedArrays.findIndex(hasSameName)
  if (firstMatchingIndex === i) {
    taggedArrays[firstMatchingIndex].tags.push("first")
  }

  // tag if last time name seen
  const lastMatchingIndex = taggedArrays.findLastIndex(hasSameName)
  if (lastMatchingIndex === i) {
    taggedArrays[lastMatchingIndex].tags.push("last")
  }
}

// remove all elements that have not been tagged
taggedArrays = taggedArrays.filter((x) => x.tags.length)

/* TEST */
const isCorrect =
  JSON.stringify(taggedArrays) == JSON.stringify(expectedTaggedArrays)
isCorrect ? console.info("correct") : console.error("incorrect")

Answer 1

sorting

How can I make the code ... more efficient? provided code is O(n^2)

Use a stable sort on the name field, with \$O(n \log n)\$ time complexity. Now, with \$O(1)\$ constant memory complexity, scan through the name entries, maintaining prev and count state variables to detect "first" and "last" transitions. This has the advantage of letting you stream output values, once you've incurred the cost of the sort.

hashing

Make a first pass over the data to build up a name hash map ("object"), storing the first and last record index seen for a given name. These are all \$O(1)\$ constant time operations.

Then make another pass over the data to produce output records. Memory cost is proportional to number of distinct names, and time cost is \$O(n)\$ linear.

Initialize first and last objects, then iterate index i over the input records:

• if rec.name not in first, then store first[rec.name] = i
• unconditionally store last[rec.name] = i

Again iterate i over the input records:

• assign empty output record
• if first[rec.name] == i, then we'll produce a "first" output
• if last[rec.name] == i, then we'll produce a "last" output
• if non-empty output record, then emit it

Let \$d\$ be number of distinct names, and \$n\$ be number of input records. If \$d \ll n\$ then memory complexity is \$O(d)\$, otherwise it is \$O(n)\$. In any event the time complexity shall be \$O(n)\$ linear in the size of the input.

Answer 2

How can I make the code ... more efficient? provided code is O(n^2)

time complexity

This is \$O(n)\$ time complexity, following inspiration from @J_H's solution.

counting

In one pass, count the number of elements for each name:

{
    "John Smith": 3,
    "Jane Doe": 2,
    "Bobby": 1,
}

producing output

In one pass, go through each element and count as you go along. If it is the first occurence, add to the output array. If it is the last occurence, add to the output array.

code

/* SETUP */
const arrays = [{
    name: "John Smith",
    value: 5
  },
  {
    name: "Jane Doe",
    value: 3
  },
  {
    name: "John Smith",
    value: 1
  },
  {
    name: "John Smith",
    value: 3
  },
  {
    name: "Jane Doe",
    value: 5
  },
  {
    name: "Bobby",
    value: 2
  },
]

const expectedTaggedArrays = [{
    name: "John Smith",
    value: 5,
    tags: ["first"]
  },
  {
    name: "Jane Doe",
    value: 3,
    tags: ["first"]
  },
  {
    name: "John Smith",
    value: 3,
    tags: ["last"]
  },
  {
    name: "Jane Doe",
    value: 5,
    tags: ["last"]
  },
  {
    name: "Bobby",
    value: 2,
    tags: ["first", "last"]
  },
]

/* PROCESSING */
const counts = arrays.reduce((accumulator, currentValue) => {
  const key = currentValue.name
  accumulator[key] = (accumulator[key] || 0) + 1

  return accumulator
}, {})

const seen = {}
const taggedArrays = []
arrays.forEach(currentValue => {
  const key = currentValue.name
  seen[key] = (seen[key] || 0) + 1

  const taggedObject = currentValue
  taggedObject.tags = []

  if (seen[key] === 1) {
    taggedObject.tags.push("first")
  }

  if (seen[key] === counts[key]) {
    taggedObject.tags.push("last")
  }

  if (taggedObject.tags.length) {
    taggedArrays.push(currentValue)
  }
})

/* TEST */
const isCorrect =
  JSON.stringify(taggedArrays) == JSON.stringify(expectedTaggedArrays)
isCorrect ? console.info("correct") : console.error("incorrect")

Answer 3

Here is my solution. Note: I am not sure if it helps with the time complexity, but it makes the code readable.

const arrays = [
  { name: 'John Smith', value: 5 },
  { name: 'Jane Doe', value: 3 },
  { name: 'John Smith', value: 1 },
  { name: 'John Smith', value: 3 },
  { name: 'Jane Doe', value: 5 },
  { name: 'Bobby', value: 2 },
];

const groupedByName = arrays.reduce((acc, item, mainIdx) => {
  (acc[item.name] ??= []).push({ ...item, mainIdx });
  return acc;
}, {});

const finalArray = Object.values(groupedByName)
  .reduce((acc, nameArray) => {
    if (nameArray.length === 1) {
      const firstLast = { ...nameArray.at(0), tags: ['first', 'last'] };
      return [...acc, firstLast];
    }

    const first = { ...nameArray.at(0), tags: ['first'] };
    const last = { ...nameArray.at(-1), tags: ['last'] };

    return [...acc, first, last];
  }, [])
  .sort((a, b) => a.mainIdx - b.mainIdx);

console.log(finalArray);