Complexities: Filtering out nested array inside an array

Question

I am doing some iteration over an array which have another set of array (the nested array). I need to .map() the outer array in such a way that it should filter out the nested array based on some criteria.

Following is the example:
JSON

[{
  "id": "CAM000001",
  "type": 128,
  "name": "abc",
  "fieldSets":
  [
    {
      "fields":
      [
        {
          "entity_name": "abc_id",
          "type": "String",
          "value": ""
        },
        {
          "entity_name": "abc_name",
          "type": "String",
          "value": "XYZ Inc."
        },
        {
          "entity_name": "created_on",
          "type": "Date",
          "value": "09/20/2016"
        }
      ]
    }
  ]
}]  

Code

datas = datas.map(data => {
  data.fieldSets[0].fields = data.fieldSets[0].fields.filter(field => {
    return field.entity_name === 'abc_name';
  });
  return data;
});  

I searched a bit, and it seems like above code has time complexity of \$\mathcal{O}(n^2)\$ (I am still learning about time and space complexity, please correct my understanding if it's wrong).

So, considering the large datasets, if fields (nested array) and datas (parent array) is growing in size, it would cost much. So can you please help me to understand what could be the best possible solution to avoid worst time complexities? Is whatever I am doing here correct?

Answer 1

If you are specifically trying to filter on entity_name, then it would appear that you will need to reconsider your initial data structure if you want to be able to get to a better level of performance for this specific operation.

A format like this would reduce this filtering operation to \$\mathcal{O}(n)\$:

[{
    "id": "CAM000001",
    "type": 128,
    "name": "abc",
    "fields": {
        "abc_id": {
            "value": "",
            "type": "String"
        },
        "abc_name": {
            "value": "XYZ Inc.",
            "type": "String"
        },
        "created_on": {
           "value": "09/20/2016",
           "type": "Date"
        }
    }
}]

Note: I removed the fieldSets concept altogether as it did not seem like it was adding any value. In fact, your example explicitly only expects a single set of fields since you are hardcoding fieldSets[0] into the logic.

This might even remove your need for "filtering" altogether as you would now have a direct way to access whatever field you were looking for.

I, in fact, don't really understand your current filtering logic, as it would only seem to potentially filter out fields from the nested array, but not perform any filtering on the outer array. If this is the desired behavior, then I do believe this would eliminate need for filtering, as you could now just access the fields directly. With this proposed data structure, if you wanted to iterate the array and do something based on the presence of the field you are trying to filter on, that might look like this:

// let's get all values for abc_name in an array
var searchField = 'abc_name';
var searchFieldValues = [];
// O(n) iteration over array
datas.forEach( data => {
    // O(1) field lookup
    if(searchField in data.fields) {
        // this field is present
        searchFieldValues.push(data.fields[searchField].value);
    }
});

If you truly are trying to filter the array based on the presence of the field on the objects in the array, then that may look like:

var searchField = 'abc_name';
// O(n) iteration with O(1) field lookup in filter callback
var filteredData = datas.filter( data => searchField in data.fields );

In either case, you now have \$\mathcal{O}(n)\$ operation. You also have a slightly smaller data structure, which may or may not be meaningful to you depending on how the data set grows.