Split array to minimum subarray containing unique object combinations

Question

I am working on a project in which the client sends us an array having some objects, there can be duplicate objects in the request as well. We determine the duplicate object based on the key called code. Here's an example:

[ {code: 10}, {code: 10}, {code: 10}, {code: 20}, {code:30} ]

In the example array above, we have 3 duplicate objects i.e., {code: 10}

We need to send this request to a third-party API, which accepts an array as well. The problem is that, in a single request to this API, we can't send duplicate objects. So we need to break this array provided by the client to a subarray, and then send each array to the API. If we break the sample provided above, we can get

[ [ {code: 10}, {code:20}, code:30} ], [ {code:10} ], [ {code:10} ] ]

So, in each of the subarray, we have unique objects (not duplicated) Also, we have a condition that the very first subarray, should contain all of the unique objects provided in the request by the client.

So, if we have a request from the client something like

[ {code: 10}, {code: 10}, {code: 10}, {code:20}, {code:20}, {code:30} ]

then the minimum subarray should be

[ [ {code: 10}, {code: 20}, {code:30} ], [ {code: 10}, {code:20} ], [ {code: 10} ] ]

can anyone help me here how can I break the array-like this? thank you

I would loop through all the objects and check if it is present in the first minimal array. If not, put it in the first minimal array. If it does exist, check the next. And so on. — Douwe de Haan
– Douwe de Haan, Commented Aug 21, 2020 at 10:35

Luke Storry · Accepted Answer · 2020-08-21 10:41:23Z

3

You can use a reducer to start with [[]] and then attempt to add each item to successive subarrays depending on whether it can find an i with the same code as the item, and then if it can't place it in any subarray, append a new subarray.

const input = [ {code: 10}, {code: 10}, {code: 10}, {code: 20}, {code:30} ]

const output = input.reduce((accumulator, item) => {
  let foundSpace = false;

  accumulator.forEach(subArray => {
    if (!foundSpace && !subArray.find(i => i.code == item.code)) {
      subArray.push(item);
      foundSpace = true;
    }
  })
  if (!foundSpace) {
    accumulator.push([item])
  }
  return accumulator;
}, [[]]);

console.log(output)

answered Aug 21, 2020 at 10:41

Luke Storry

6,7821 gold badge11 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tejashwi Kalp Taru · Accepted Answer · 2021-04-02 10:00:22Z

2

This is simple, I found the answer after some fiddling around. We can find the subarray in basically 3 steps

Find all the unique objects, and push them to an array, name unique
Find the difference from the original array
repeat, until there is a difference left

const data = [ {code: 10}, {code: 10}, {code: 10}, {code:20}, {code:20}, {code:30} ];

let temp = data;
const subarray = [];
while (temp.length) {
  // find unique
  let unique = [];
  temp.map(x => unique.filter(a => a.code === x.code).length > 0 ? null : unique.push(x));

  // find difference
  const diff = temp.filter(x => !unique.includes(x));

  // store
  subarray.push(unique);
  temp = diff;
}
console.log(subarray);

edited Apr 2, 2021 at 10:00

answered Aug 21, 2020 at 10:58

Tejashwi Kalp Taru

3,1192 gold badges22 silver badges38 bronze badges

Comments

Rahul Bhobe · Accepted Answer · 2020-08-21 10:49:03Z

2

Here is a solution in O(n log n) time complexity. First sort the input array. Then iterate over the array to create output. If the current is same as previous, add it to the next sub array.

let input = [ {code: 10}, {code: 10}, {code: 10}, {code: 20}, {code:30} ];

input.sort((a, b) => a.code - b.code);

let arr  = [[]];
let idx  = 0;
let prev = -Infinity;

input.forEach(a => {
    if (a.code !== prev) {
         idx = 0;
    } else {
         idx++;
    }
    arr[idx] = arr[idx] || [];
    arr[idx].push(a);
    prev = a.code;
});

console.log(arr);

answered Aug 21, 2020 at 10:49

Rahul Bhobe

4,4714 gold badges19 silver badges35 bronze badges

Comments

Szaman · Accepted Answer · 2020-08-21 11:16:47Z

Here's an efficient solution which only parses the original array once. We're going to keep track of the codes we've already encountered in the helper indices array. This way we can instantly look up where to put an element.

This way we can simply reduce an array using an accumulator result, which will contain all our subarrays.

const arr = [ {code: 10}, {code: 10}, {code: 10}, {code: 20}, {code:30} ];

// helper array to keep track of where to put elements with given code
let indices = [];

// we're going to accumulate our subarrays into the result array
const result = arr.reduce((result, el) => {
  // on first encounter, put in subarray with index 0
  let index = indices[el.code] ?? 0;
  
  // initialise the subarray if not present, and push
  const subArray = result[index] ?? [];
  subArray.push(el);
  
  // put the subarray into the result array
  result[index] = subArray;
  
  // increment the index so next item with this code will go to the next subarray
  indices[el.code] = ++index;
  
  return result;
}, []);

console.log(result);

Collectives™ on Stack Overflow

Split array to minimum subarray containing unique object combinations

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related