Iterating over solutions

TL;DR: I’m no perfectionist. Once I’m done with a problem, I tend to move to solve the next one. However, sometimes it’s worth taking a second glance and improving a solution. Here is a problem I worked on recently and what the solutions to the problem were.

Recently I had a relatively simple problem to solve at work. There was a form that had a select with nested optgroups in it, where the group name was a type of food (fruit, vegetable, etc.) and the group was various products belonging to that group (apples, cucumbers, juice, etc.). You can find all working examples on CodeSandbox.

The data structure we got from the backend looked something like this:

const categories = [
  { name: 'Fruit' },
  { name: 'Vegetable' },
  { name: 'Beverage' },
]

const subCategories = [
  { name: 'Apple', category: 'Fruit' },
  { name: 'Pear', category: 'Fruit' },
  { name: 'Pineapple', category: 'Fruit' },
  { name: 'Cucumber', category: 'Vegetable' },
  { name: 'Bell pepper', category: 'Vegetable' },
  { name: 'Avocado', category: 'Vegetable' },
  { name: 'Tomato', category: 'Vegetable' },
  { name: 'Apple juice', category: 'Beverage' },
  { name: 'Water', category: 'Beverage' },
  { name: 'Club mate', category: 'Beverage' },
]

The way I prefer to go about solving problems like this is to have a working solution first before making any optimizations. For example, the first iteration of the solution looked like this:

// A brute force first iteration that works
// iterations: 3 (outer .map) * 10 (inner .map)
<select id='select'>
  {categories.map(category => (
    <optgroup key={category.name} label={category.name}>
      {subCategories.map(
        subcategory =>
          subcategory.category === category.name && (
            <option key={subcategory.name}>{subcategory.name}</option>
          )
      )}
    </optgroup>
  ))}
</select>

In this solution, we iterate 3 times over 10 subcategories. So, all in all, we do 30 iterations.

So the next step is to ask ourselves: what can be improved? We could, for example, filter the subcategories by the categories before the rendering. The second version therefore might look like something like this:

// Make an array of categories and add the subcategories as children
// The result will look like this:
// [{ name: 'fruits', children: ['apple', 'pear']}]
// iterations: 3 (.reduce) * 10 (.filter) + 10 (.map in render)
const items = categories.reduce(
  (acc, { name }) => [
    ...acc,
    {
      name,
      children: subCategories.filter(({ category }) => name === category),
    },
  ],
  []
)

// In the render:
return (
  <select id='select'>
    {items.map(({ name, children }) => (
      <optgroup key={name} label={name}>
        {children.map(subcategory => (
          <option key={subcategory.name}>{subcategory.name}</option>
        ))}
      </optgroup>
    ))}
  </select>
)

While we improved the iteration count in the render to 10, we have to add the number of iterations when we do the initial filtering. So, in the end, we actually increased our iteration count to 40. 🙀

By looking at the data structure, we can identify that we don’t need to iterate over the categories.

// Make an object with the categories as the key and the subcategory list as
// the value. The result will look like this:
// { fruits: ['apple', 'pear', 'pineapple'] }
// iterations: 10 (.reduce) + 10 (.map in render)
const categories = subCategories.reduce((acc, { name, category }) => {
  if (acc[category]) acc[category].push({ name })
  else acc[category] = [{ name }]

  return acc
}, {})

<select id='select'>
  {Object.keys(categories).map(category => (
    <optgroup key={category} label={category}>
      {categories[category].map(({name}) => <option key={name}>{name}</option>)}
    </optgroup>
  ))}
</select>

All in all, we reduced the count of iterations from 30 to 40 to 20. Not too bad.