TypeScript function to compare two arrays while ignoring case and whitespace

Question

I'm just looking for general guidance on this short TypeScript function I implemented. Are there any glaring violations? Are there better practices for accomplishing this?

Should I be using map/reduce/filter, or is this simple approach just fine here? I'm not sure about efficiency here because we basically just need to examine every item from each list. I don't think there is a shortcut way to make this faster, but that's why I'm asking. For what it's worth, we're only talking about examining a couple hundred items.

The function takes two lists. If the source list contains items that the other list does not, we need to return those items. When comparing the lists, we need to remove leading and trailing whitespace, and we need to ignore case sensitivity. However, the returned values need to be in their original casing.

/**
 * Returns a list of items missing from a source list. The items are compared while ignoring case and
 * ignoring leading and trailing whitespace. The values returned maintain their original casing though.
 * @param sourceList - The master list used for comparison.
 * @param otherList  - The list to be compared to the source list.
 * @returns The items in the source list that are missing from the other list.
 */
    export function getMissingItemsIgnoreCase(
      sourceList: string[],
      otherList: string[],
    ): string[] {
      const otherListLowerCaseAndTrimmed: string[] = otherList.map((x) =>
        x.toLowerCase().trim(),
      );
    
      // The key is the lower-case and trimmed provider name. The value is the same, but with original casing.
      // We'll return the value so we preserve the casing.
      const missingMap = new Map<string, string>();
    
      for (const sourceItem of sourceList) {
        const sourceItemLowerCaseAndTrimmed = sourceItem.toLowerCase().trim();
        if (!otherListLowerCaseAndTrimmed.includes(sourceItemLowerCaseAndTrimmed)) {
          missingMap.set(sourceItemLowerCaseAndTrimmed, sourceItem.trim());
        }
      }
    
      return Array.from(missingMap.values());
    }

Answer 1

One glaring issue is using of .includes() for every element. AFAIK, .includes() just does linear search item by item -- it's a hidden loop. And then there is your const (const sourceItem of sourceList), an explicit loop. These loops are nested, and which means the time required to run your function is proportional to <number of items in 1st array> * <number of items in 2nd array>. To me it seems like O(n^2), which is slow for big numbers and/or additional levels of nesting -- imagine somebody uses your function in a tight loop on a big dataset. (Disclaimer: I'm not a guru on big O notation, so, I might be wrong re particulars, but I believe the main idea is still correct.)

What can be done? Instead of this:

const otherListLowerCaseAndTrimmed: string[] = otherList.map((x) =>
  x.toLowerCase().trim(),
);
// ...
if (!otherListLowerCaseAndTrimmed.includes(sourceItemLowerCaseAndTrimmed)) {
  // ...
}

Do this (note new Set() and .has()):

const otherListLowerCaseAndTrimmed = new Set(
  otherList.map((x) =>
    x.toLowerCase().trim(),
  )
);
// ...
if (!otherListLowerCaseAndTrimmed.has(sourceItemLowerCaseAndTrimmed)) {
  // ...
}

I believe this change makes it O(n) instead of O(n^2), i.e. required time grows in a linear fashion instead of quadratic.

Your original implementation seems to be fine, and with smallish datasets you won't encounter problems. If you're sure that's the most plausible scenario, then it's actually fine to leave it like that. But it's a good habit to avoid O(n^2) if possible, because in a fairly complex application these things stack, and can suddenly bite you when total amount of data you're working with hits certain limits.

There is another thing which is less impactful but still could be useful: instead of building a map of results, you could make a generator and output values one by one, as they are ready, which somewhat lowers memory requirements, but also substantially changes function signature and the way client code consumes is. So, I'd recommend investigating this only if you know memory usage could be an issue (probably not for browser code, probably yes for server-side with lots of concurrent requests).

And one more thing which could make your function less specific. Consider this:

export function getMissingItems(
  sourceList: string[],
  otherList: string[],
  transform: (value: string) => string = s => s.toLowerCase().trim()
): string[] {
  const otherListTransformed = new Set(otherList.map(x => transform(x)));

  const missingMap = new Map<string, string>();

  for (const sourceItem of sourceList) {
    const sourceItemTransformed = transform(sourceItem);
    if (!otherListTransformed.has(sourceItemTransformed)) {
      missingMap.set(sourceItemTransformed, sourceItem);
    }
  }

  return Array.from(missingMap.values());
}

With this code your function could handle any kind of transformation, but defaults to your original behavior (minus transformation of the resulting strings, but please bear with me).

This approach could be generalized to this:

export const lowercase = (items: string[]): string[] => items.map(x => x.toLowerCase());
export const trim = (items: string[]): string[] => items.map(x => x.trim());
export const getMissingItems = (
  sourceList: string[],
  otherList: string[],
  transformation: (x: string) => string = x => x,
): string[] => {
  const otherItems = new Set(otherList.map(x => transformation(x)));
  return sourceList.filter(x => otherItems.has(transformation(x)));
};

And with this little "library" of pretty generic functions your original code can be expressed like this:

export function getMissingItemsIgnoreCase(
  sourceList: string[],
  otherList: string[],
): string[] {
  return getMissingItems(
    trim(sourceList),
    trim(otherList),
    x => x.toLowerCase()
  );
}

Please be careful, here starts the domain of functional programming, composition, and many other interesting things which might drastically change your approach to solving problems. Jokes aside, that's where people usually start to over-optimize, over-abstract, over-generalize, and many other "over-" things that hurt productivity.