Data Structures and Algorithms · Software Engineering

Coding: Flattening Nested Arrays

coding

Puzzle

Given an array of Integers that presents several levels of nesting, provide an algorithm to flatten the input array.

Input

A nested array of arrays.

Example. [[1,2,[3]],4]

Output

A flat array.

Example. [1,2,3,4]

 

Solution using Java as Programming Language

Gist with runnable code and tests.

public static Integer[] flattener(Object[] nested)
{
    List<Integer> flattened = flatten(nested);
    Integer[] canonical = new Integer[flattened.size()];

    return flattened.toArray(canonical);
}

 
public static List<Integer> flatten(Object[] nested)
{
    if(nested == null)
        throw new IllegalArgumentException("Nestings cannot be NULL");

    List<Integer> flattened = new LinkedList<>();
    for(int i = 0; i < nested.length; i++) {
        if(nested[i] instanceof Integer)
            flattened.add((Integer) nested[i]);
        else if(nested[i] instanceof Object[])
            flattened.addAll(flatten((Object[]) nested[i]));
        else
            throw new IllegalArgumentException("Only Integers and Nested Arrays are allowed");
    }

    return flattened;
}

Discussion

To get the job done, the solution adopts the recursion. Two cases are possible: looping through the array or any partial view of it, either an Integer can be found, or an Object; in the latter case, the recursion has to be nested. Naturally, the algorithm evolves from the first element of the original array up to the last one, no matter the level of nesting: nested arrays are flattened on the way on.

The output for any kind of nested array is a flat array, as demanded by the problem statement.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s