In JavaScript, from two array of objects I need to filter out objects based on a filter condition, in a new array in complexity less than O(n^2)

user_10352684 0
Viewed 72

Explanation of the problem statement : I have two arrays A and B :

A = [
     {
         "isAvailable" : true,
         "productCode" : "12103977",
         "size" : "UK/IND-3",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103977"
      },

      {
         "isAvailable" : true,
         "productCode" : "12103978",
         "size" : "UK/IND-4",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103978"
      },

      {
         "isAvailable" : true,
         "productCode" : "12103979",
         "size" : "UK/IND-8",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103979"
      },

]


B = [
       {
         "dimensionSize" : "3",
         "euroSize" : "36",
         "usSize" : "4"
      },

      {
         "dimensionSize" : "4",
         "euroSize" : "36",
         "usSize" : "4"
      },

      {
         "dimensionSize" : "10",
         "euroSize" : "36",
         "usSize" : "4"
      },
]

I need to create a new array C basis the below condition :

Condition : "If the value contained in "size" key of any object in array A includes the value contained in key "dimensionSize" of any object in array B then add the corresponding matching object from array B to array C".

So array C will look like this after the above condition is met -

C = [
      {
         "dimensionSize" : "3", 
         "euroSize" : "36",
         "usSize" : "4"
      },

      {
         "dimensionSize" : "4", 
         "euroSize" : "36",
         "usSize" : "4"
      },
]

Explanation of how array C is obtained : In array A there is one object that has key "size" with value "UK-IND-3" that contains the value "3" from the key "dimensionSize" in one of the object from array B.Same goes for object with key "size" value "UK-IND-4"

My motive to find the solution to this problem : I have huge length arrays and I need to run condition similar to above to filter out some data in a new array. I have seen other solutions in stack-overflow and I have derived a solution using array methods like filter, includes, some, map etc but I need an efficient solution that is efficient with real time data, like arrays with huge length.

Any help in sharing an efficient algorithm or a path-forward is highly appreciated. Thank you in advance!

Edit : Existing solution that I have which runs in O(n^2). Assume A and B as arrays from my problem statement. matchArray is the resultant array.

let matchArray;
        matchArray = B.filter(objB => {
            let match = false;
            A.forEach(objA => {
                if (objA.size.includes(objB.dimensionSize) {
                    match = true;
                }
            });
            return match;
        });

Edit 2 : Structure of array B and array C were not correct. I have corrected it now.

time-complexity arrays javascript
3 Answers

Solution with O(n) complexity

const solution = (A, B) => {
  const allowedSizes = new Set()
  
  A.forEach(({ size }) => {
    const [ s ] = size.match(/\d+$/g)
    
    allowedSizes.add(s)
  })
  
  return B.filter(({ dimensionSize }) => {
    return allowedSizes.has(dimensionSize)
  })
}

const A = [
      {
         "isAvailable" : true,
         "productCode" : "12103977",
         "size" : "UK/IND-3",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103977"
      },

      {
         "isAvailable" : true,
         "productCode" : "12103978",
         "size" : "UK/IND-4",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103978"
      },

      {
         "isAvailable" : true,
         "productCode" : "12103979",
         "size" : "UK/IND-8",
         "url" : "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103979"
      },

]


const B = [
      {
         "dimensionSize" : "3",
         "euroSize" : "36",
         "usSize" : "4"
      },

      {
         "dimensionSize" : "4",
         "euroSize" : "36",
         "usSize" : "4"
      },

      {
         "dimensionSize" : "10",
         "euroSize" : "36",
         "usSize" : "4"
      },
]

console.log(solution(A, B))

user_124103460

All credits go to @kerm's answer, here is the adaptation to your updates with explanation:

  1. Create a Set of A[i].size values - Set contains every value only once, in your example, the filterSet will contain (3,4,8) - this is done in O(n)
let filterSet = new Set();
A.forEach(i => filterSet.add(i.size.match(/\d+$/)[0]));
  1. Set has a has() method which returns in O(1), which can be used in the B.filter method with O(n) complexity:
let result = B.filter(i => filterSet.has(i.dimensionSize))
user_3437210

Here is a working example, first it creates an object with all available sizes in A, then filters B to keep only the ones that dimensionSize exist as key in listedSizes

console.clear();
(()=>{

    let A = [{
        "isAvailable": true,
        "productCode": "12103977",
        "size": "UK/IND-3",
        "url": "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103977"
    }, {
        "isAvailable": true,
        "productCode": "12103978",
        "size": "UK/IND-4",
        "url": "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103978"
    }, {
        "isAvailable": true,
        "productCode": "12103979",
        "size": "UK/IND-8",
        "url": "/asics-mens-gel-kayano-28-harmony-blue-running-shoes/12103979"
    }, ]

    let B = [{
        "dimensionList": [{
            "dimensionSize": "3",
            "euroSize": "36",
            "usSize": "4"
        }]
    }, {
        "dimensionList": [{
            "dimensionSize": "4",
            "euroSize": "36",
            "usSize": "4"
        }]
    }, {
        "dimensionList": [{
            "dimensionSize": "10",
            "euroSize": "36",
            "usSize": "4"
        }]
    }];
    let listedSizes = Object.fromEntries(A.map(e=>[(e.size.match(/UK\/IND-(\d)+/) || [0, 0])[1],0]));
    let filteredB = B.filter(e=>listedSizes.hasOwnProperty(e.dimensionList[0].dimensionSize));

    console.log(listedSizes, filteredB);
}
)();

user_14561510
Related