'flatten array of arrays (in a specific way) in O(n) time or better

if we have a nested array of objects, type of

{ 
  [a: string]: string, 
  [b: string]: {[foo: string]: number}[]
}[]

or, as an example,

[
  {
    'a': 'group1', 
    'b': [{'group1_elem1': 1}, {'group1_elem2': 3}]
  }, 
  {
    'a': 'group2', 
    'b': [{'group2_elem1': 2}, {'group2_elem2': 4}]
  },
  ...,
  {
    'a': 'groupN', 
    'b': [{'groupN_elem1': x}, {'groupN_elem2': y}, ... {'groupN_elemN': z}]
  },
]

is there a way to restructure that array to be

[
  {
    'a': 'group1', 
    'elem1_1': 1
  },
  {
    'a': 'group1',
    'elem1_2': 3
  }
  ...,
  {
    'a': 'groupN',
    'elemN_1': x
  },
  ...,
  {
    'a': 'groupN',
    'elemN_N': z
  }
]

in O(n) time or better?

it seems like you have to iterate through every 'a' group (O(n)) and each of its elements (O(n)), in order to (tl;dr) make an array consisting of each 'b' array element matched with its parent 'a' group name, but maybe there is some magic, in the world, of which i am not aware.



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source