The challenge then is that memory consumption needs to be less than N + M + N*M where N and M represent the number of elements in the respective lists.

That's N + M + N * M of what? Since you aren't writing it as a big-O notation (in which case, it's fairly trivial, as any naive implementation doesn't need more memory than O(N*M), and cannot use less as that's the size of the output list), you should mention the units you mean. Considering that N + M is the size of the input, and N * M the size of the output, it means that if the unit is "values", there isn't room for a single iterator.