183

I have a Javascript array that I would like to split into two based on whether a function called on each element returns true or false. Essentially, this is an array.filter, but I'd like to also have on hand the elements that were filtered out.

Currently, my plan is to use array.forEach and call the predicate function on each element. Depending on whether this is true or false, I will push the current element onto one of the two new arrays. Is there a more elegant or otherwise better way to do this? An array.filter where the will push the element onto another array before it returns false, for instance?

3
  • If you can post some sample code, will help give you a better answer! Commented Jul 30, 2012 at 23:24
  • No matter what implementation you use Javascript will always have to: loop through items, run the function, push the item into an array. I don't think there is a way to make that more efficient.
    – TheZ
    Commented Jul 30, 2012 at 23:25
  • 7
    You can do whatever you want in the callback passed to .filter but such side effects are difficult to track and understand. Just iterate over the array and push to one array or an other. Commented Jul 30, 2012 at 23:28

16 Answers 16

129

With ES6 you can make use of the spread syntax with reduce:

function partition(array, isValid) {
  return array.reduce(([pass, fail], elem) => {
    return isValid(elem) ? [[...pass, elem], fail] : [pass, [...fail, elem]];
  }, [[], []]);
}

const [pass, fail] = partition(myArray, (e) => e > 5);

Or on a single line:

const [pass, fail] = a.reduce(([p, f], e) => (e > 5 ? [[...p, e], f] : [p, [...f, e]]), [[], []]);
5
  • 14
    For me, lodash partition or just forEach would be easier to understand, but even so, nice effort
    – Toni Leigh
    Commented Jul 23, 2018 at 12:56
  • 45
    This will create two new arrays for every element in the original. While one array will only have two elements, the other grows with the size of the array. This will thus be super slow and waste lots of memory. (You could do the same with a push and it would be more efficient.) Commented Aug 23, 2018 at 2:23
  • Thanks, saved my time!
    – 7urkm3n
    Commented Sep 19, 2019 at 22:32
  • This is really useful, braza. Note for others: there are some more readable versions below.
    – Raffi
    Commented Sep 11, 2020 at 13:11
  • 21
    This is an O(n^2) solution to an O(n) problem. Since the spread operator (or any other method that duplicates (part of) an array) will have to do work for each member of the array, and this solution applies such operations several times over for each element in the original array.
    – SFG
    Commented Jan 22, 2021 at 17:35
74

You can use lodash.partition

var users = [
  { 'user': 'barney',  'age': 36, 'active': false },
  { 'user': 'fred',    'age': 40, 'active': true },
  { 'user': 'pebbles', 'age': 1,  'active': false }
];

_.partition(users, function(o) { return o.active; });
// → objects for [['fred'], ['barney', 'pebbles']]

// The `_.matches` iteratee shorthand.
_.partition(users, { 'age': 1, 'active': false });
// → objects for [['pebbles'], ['barney', 'fred']]

// The `_.matchesProperty` iteratee shorthand.
_.partition(users, ['active', false]);
// → objects for [['barney', 'pebbles'], ['fred']]

// The `_.property` iteratee shorthand.
_.partition(users, 'active');
// → objects for [['fred'], ['barney', 'pebbles']]

or ramda.partition

R.partition(R.contains('s'), ['sss', 'ttt', 'foo', 'bars']);
// => [ [ 'sss', 'bars' ],  [ 'ttt', 'foo' ] ]

R.partition(R.contains('s'), { a: 'sss', b: 'ttt', foo: 'bars' });
// => [ { a: 'sss', foo: 'bars' }, { b: 'ttt' }  ]
2
  • 1
    Any info on the big o analysis for `lodash.partition? Is it O(n) or O(n^2)?
    – Ricardo
    Commented Apr 29, 2022 at 0:09
  • 1
    Man, lodash never ceases to delight. Thanks for sharing this! I didn't know I had it right in the lib this whole time, and kept trying to (poorly) reinvent the wheel. Commented Jul 26, 2022 at 16:24
48

I came up with this little guy. It uses for each and all that like you described, but it looks clean and succinct in my opinion.

//Partition function
function partition(array, filter) {
  let pass = [], fail = [];
  array.forEach((e, idx, arr) => (filter(e, idx, arr) ? pass : fail).push(e));
  return [pass, fail];
}

//Run it with some dummy data and filter
const [lessThan5, greaterThanEqual5] = partition([0,1,4,3,5,7,9,2,4,6,8,9,0,1,2,4,6], e => e < 5);

//Output
console.log(lessThan5);
console.log(greaterThanEqual5);

3
  • 7
    This solution is far better than some of the ones with more upvotes, IMHO. Easy to read, makes a single pass through the array, and doesn't allocation and re-allocate the partition result arrays. I also like that it exposes all three common filter values to the filter function (value, index, and the whole array). This will make this function much more reusable. Commented Dec 23, 2019 at 20:11
  • 1
    I also like this one very much for its simplicity and elegance. Having said that, I found it to be significantly slower than a simple for loop as in an old answer by @qwertymk. E.g. for an array containing 100,000 elements it was twice as slow on my system.
    – tromgy
    Commented Jan 30, 2020 at 5:09
  • Any .push() is a potential reallocation though, isn't it?
    – Aviad P.
    Commented Aug 2, 2022 at 8:13
31

You can use reduce for it:

function partition(array, callback){
  return array.reduce(function(result, element, i) {
    callback(element, i, array) 
      ? result[0].push(element) 
      : result[1].push(element);
    
        return result;
      }, [[],[]]
    );
 };

Or if using Typescript:

const partition = <T,>(
  array: T[],
  callback: (element: T, index: number, array: T[]) => boolean
) => {
  return array.reduce(function(result, element, i) {
    callback(element, i, array)
      ? result[0].push(element) 
      : result[1].push(element);

    return result;
  }, [[],[]]);
};

Example:

const groceries = [
  { type: "apple" },
  { type: "pear" },
  { type: "banana" }
]

const [apples, others] = partition(
  groceries, 
  (item) => item.type === "apple",
);

// => apples: [{ type: "apple" }]
// => others: [{ type: "pear" }, { type: "banana" }] 

Using ES6 syntax you also can do that using recursion (updated to avoid creating new arrays on every iteration):

function partition([current, ...tail], f, left = [], right = []) {
    if(current === undefined) {
        return [left, right];
    }
    if(f(current)) {
        left.push(current);
        return partition(tail, f, left, right);
    }
    right.push(current);
    return partition(tail, f, left, right);
}
4
  • 5
    IMHO, the first solution (push) is better performance as array size grows. Commented Nov 3, 2019 at 19:26
  • @ToolmakerSteve could you elaborate more why? I also read comment on top answer but still confused why
    – buncis
    Commented Apr 21, 2020 at 20:25
  • 4
    @buncis. The first approach examines each element one time, simply pushing that element to the appropriate array. The second approach constructs [...left, current] or [...right, current] - for each element. I don't know the exact internals, but I'm sure that construction is more expensive than simply pushing an element on to an array. Also, as a general rule, recursion is more expensive than iterating, because it involves creating a "stack frame" each time. Commented Apr 22, 2020 at 19:39
  • 1
    @buncis not only does it have to construct an array for each element in the source array (constructing things in JS is highly optimized, that's not the worst) it also copies the source array each time it's doing that. Which is an O(n) operation (amount of work is proportional to the array size). It's repeating this for each member in the source array, making the total amount of work squared to the number of elements in the array. Which is obviously not very good if the work could be done in a number of operations that grows proportional to the number of elements.
    – SFG
    Commented Jan 22, 2021 at 17:55
16

In filter function you can push your false items into another variable outside function:

var bad = [], good = [1,2,3,4,5];
good = good.filter(function (value) { if (value === false) { bad.push(value) } else { return true});

Of course value === false need to be real comparasion ;)

But it do almost that same operation like forEach. I think you should use forEach for better code readability.

3
  • 2
    Agreed with above poster...putting this kind of logic in a filter function feels a bit bloated and hard to manage. Commented Apr 3, 2018 at 1:15
  • I think filter makes sense, you want to remove them from the original array so it it a filter
    – Mojimi
    Commented Dec 13, 2018 at 11:26
  • Looks readable, performant, and simple to me. Just use this and be a dragon. 🐲 Commented Oct 20, 2022 at 20:51
15

This sounds very similar to Ruby's Enumerable#partition method.

If the function can't have side-effects (i.e., it can't alter the original array), then there's no more efficient way to partition the array than iterating over each element and pushing the element to one of your two arrays.

That being said, it's arguably more "elegant" to create a method on Array to perform this function. In this example, the filter function is executed in the context of the original array (i.e., this will be the original array), and it receives the element and the index of the element as arguments (similar to jQuery's each method):

Array.prototype.partition = function (f){
  var matched = [],
      unmatched = [],
      i = 0,
      j = this.length;

  for (; i < j; i++){
    (f.call(this, this[i], i) ? matched : unmatched).push(this[i]);
  }

  return [matched, unmatched];
};

console.log([1, 2, 3, 4, 5].partition(function (n, i){
  return n % 2 == 0;
}));

//=> [ [ 2, 4 ], [ 1, 3, 5 ] ]
1
  • 22
    For the modern reader, PLEASE do not add methods to global standard library objects. It's dangerous, and likely to be overwritten, leading to mysterious and broken behavior. A plain old function, properly scoped, is far safer, and calling myFunc(array) is no less "elegant" than array.myFunc().
    – Emmett R.
    Commented Jul 26, 2018 at 15:35
12

A lot of answers here use Array.prototype.reduce to build a mutable accumulator, and rightfully point out that for large arrays, this is more efficient than, say, using a spread operator to copy a new array each iteration. The downside is that it's not as pretty as a "pure" expression using the short lambda syntax.

But a way around that is to use the comma operator. In C-like languages, comma is an operator that always returns the right hand operand. You can use this to create an expression that calls a void function and returns a value.

function partition(array, predicate) {
    return array.reduce((acc, item) => predicate(item)
        ? (acc[0].push(item), acc)
        : (acc[1].push(item), acc), [[], []]);
}

If you take advantage of the fact that a boolean expression implicitly casts to a number as 0 and 1, and you can make it even more concise, although I don't think it's as readable:

function partition(array, predicate) {
    return array.reduce((acc, item) => (acc[+!predicate(item)].push(item), acc), [[], []]);
}

Usage:

const [trues, falses] = partition(['aardvark', 'cat', 'apple'], i => i.startsWith('a'));
console.log(trues); // ['aardvark', 'apple']
console.log(falses); // ['cat']
10

What about this?

[1,4,3,5,3,2].reduce( (s, x) => { s[ x > 3 ].push(x); return s;} , {true: [], false:[]} )

Probably this is more efficient than the spread operator

Or a bit shorter, but uglier

[1,4,3,5,3,2].reduce( (s, x) => s[ x > 3 ].push(x)?s:s , {true: [], false:[]} )

1
  • 1
    Really nice and concise answer. Just want to add that if you want to rename the output you can do something like this: let { true: hello, false: world } = [1,4,3,5,3,2].reduce( (s, x) => s[ x > 3 ].push(x)?s:s , {true: [], false:[]} )
    – 8bithero
    Commented Jun 5, 2021 at 20:25
6

Try this:

function filter(a, fun) {
    var ret = { good: [], bad: [] };
    for (var i = 0; i < a.length; i++)
        if (fun(a[i])
            ret.good.push(a[i]);
        else
            ret.bad.push(a[i]);
    return ret;
}

DEMO

1
  • Pointing out that the filter function of arrays isn't actually supported in all browsers (I'M LOOKING AT YOU OLDER IEs)
    – TheZ
    Commented Jul 30, 2012 at 23:27
6

Easy to read one.

const partition = (arr, condition) => {
    const trues = arr.filter(el => condition(el));
    const falses = arr.filter(el => !condition(el));
    return [trues, falses];
};

// sample usage
const nums = [1,2,3,4,5,6,7]
const [evens, odds] = partition(nums, (el) => el%2 == 0)
2
  • 11
    The downside is you make 2 loops instead only one
    – Laurent
    Commented May 20, 2019 at 15:49
  • upvote for readability, for small array this one is cleary more future proof Commented Aug 25, 2020 at 7:44
6

It can be done using Object.groupBy. Imagine if I want to separate an array by whether its elements are larger than 2.

const array = [1, 2, 3, 4, 5];
const { true: large, false: small } = Object.groupBy(array, e => e > 2);

console.log({ large, small });

Be aware of its coverage. By March 2024, the overall coverage of this built-in function is below 90% and is not advised to use it on production environments.

5

I ended up doing this because it's easy to understand:

const partition = (array, isValid) => {
  const pass = []
  const fail = []
  array.forEach(element => {
    if (isValid(element)) {
      pass.push(element)
    } else {
      fail.push(element)
    }
  })
  return [pass, fail]
}

// usage
const [pass, fail] = partition([1, 2, 3, 4, 5], (element) => element > 3)

And the same method including types for typescript:

const partition = <T>(array: T[], isValid: (element: T) => boolean): [T[], T[]] => {
  const pass: T[] = []
  const fail: T[] = []
  array.forEach(element => {
    if (isValid(element)) {
      pass.push(element)
    } else {
      fail.push(element)
    }
  })
  return [pass, fail]
}

// usage
const [pass, fail] = partition([1, 2, 3, 4, 5], (element: number) => element > 3)
0
2

ONE-LINER Partition

const partitionBy = (arr, predicate) =>
    arr.reduce((acc, item) => (acc[+!predicate(item)].push(item), acc), [[], []]);

DEMO

// to make it consistent to filter pass index and array as arguments
const partitionBy = (arr, predicate) =>
    arr.reduce(
        (acc, item, index, array) => (
            acc[+!predicate(item, index, array)].push(item), acc
        ),
        [[], []]
    );

console.log(partitionBy([1, 2, 3, 4, 5], x => x % 2 === 0));
console.log(partitionBy([..."ABCD"], (x, i) => i % 2 === 0));

For Typescript (v4.5)

const partitionBy = <T>(
  arr: T[],
  predicate: (v: T, i: number, ar: T[]) => boolean
) =>
  arr.reduce(
    (acc, item, index, array) => {
      acc[+!predicate(item, index, array)].push(item);
      return acc;
    },
    [[], []] as [T[], T[]]
  );
1

Lodash partition alternative, same as the first solution of @Yaremenko Andrii but shorter syntax

function partition(arr, callback) {
  return arr.reduce(
    (acc, val, i, arr) => {
      acc[callback(val, i, arr) ? 0 : 1].push(val)
      return acc
    },
    [[], []]
  )
}
1

Most of the answers here are simply variations of Array.reduce, which is a correct way to accomplish this. I wrote a small library that abstracts all this away with a simple API for partitioning arrays in JavaScript. Additionally it has the ability to spawn a web worker (or web thread in Node) to make reducing arrays to partitions async.

const someArray = [1, ... , 100]

console.log('--- start ---');

const reduced = someArray.reduce((reducer, i) => {
      // Different variations of fancy code can go here that all do the same thing
      if (i < 33) reducer[0].push(i)
      else if (i => i > 32 && i < 66) reducer[1].push(i)
      else if (i => i > 67) reducer[2].push(i)
      return reducer
    }, [[], [], []])

console.log('array.reduce done processing');
console.log('--- UI element loaded ---');

'--- start ---'
'array.reduce done processing'
'--- UI element loaded ---'

Here is how you would accomplish the same thing with the library but async

const someArray = [1, ... , 100]

console.log('--- start ---');

partition()
    .async()
    .add(i => i < 33)
    .add(i => i > 32 && i < 66)
    .add(i => i > 67)
    .split(someArray)
    .then(result => {
      console.log('Partitions done processing');
    });

console.log('--- UI element loaded ---');

'--- start ---'
'--- UI element loaded ---'
'Partitions done processing'

The output of both would be three array paritions.

[
  [1, ..., 32],
  [33, ..., 65],
  [66, ..., 100]
]
-1

I know there are multiple solutions already but I took the liberty of putting together the best bits of the answers above and used extension methods on Typescript. Copy and paste and it just works:

declare global {

  interface Array<T> {
    partition(this: T[], predicate: (e: T) => boolean): T[][];
  }

}

if(!Array.prototype.partition){

  Array.prototype.partition = function<T>(this: T[], predicate: (e: T) => boolean): T[][] {

    return this.reduce<T[][]>(([pass, fail], elem) => {
      (predicate(elem) ? pass : fail).push(elem);
      return [pass, fail];
    }, [[], []]);

  }
}

Usage:


const numbers = [1, 2, 3, 4, 5, 6];
const [even, odd] = numbers.partition(n => n % 2 === 0);

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.