[Challenge] Flatten an Array ♭



Code Challenge #21: August 30, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reported to have been asked in interviews at Facebook and has also been asked right here at Codecademy!

Basic Difficulty

Write a function, flattenArray, that when given an 2D array, flattens it into a 1D array

  • Function Name: flattenArray
  • Input: a 2D array
  • Output: a 1D array
  • Example: flattenArray([1,2,3, [4,5], 6, [7,8], 9]) => [1,2,3,4,5,6,7,8,9]
  • Always remember to explain your code and the thought processes behind it!
  • You can think of a 2D array as a spreadsheet or a chessboard, whereas a 1D array is more like a list or one long chain of data.
  • What if your interviewer had follow-up questions or extensions to this challenge? Don’t anticipate what exactly those follow-ups or changes may be, but try to write your code so that it is easily read, easily maintained, and can be adapted to potential modifications in the interviewer’s questioning.
Find out more about basic challenges.

You can learn more about arrays with some JavaScript exercises here, here, and here.

Intermediate difficulty

Improve on the flattenArray function by writing flattenArrayN, a function that can flatten arrays that are nested n-levels deep, returning a flattened 1D array.

  • Function Name: flattenArrayN
  • Input: any array with n levels of depth, where n is an integer ≥1
  • Output: a 1D array
  • Example: flattenArrayN([1, 2, [3, [4, 5]], 6]) => [1, 2, 3, 4, 5, 6]
  • For our intermediate challenge, the array can have multiple types: {}, [], "", undefined, null, and integers (1,2,3,…) are all valid types inside the array.
  • You must explain your submission to be able to win!
Find out more about intermediate challenges.

Hard Difficulty

Write flattenArray and flattenArrayN as efficiently as possible.

  • Don’t forget to explain your submission just as you would do in a job interview setting!
Find out more about hard challenges and Big O

Reply to this thread with a link to your code on repl.it and paste your properly formatted code to participate! Don’t just submit your code, remember to explain your solution, too! If you want to be considered as the winner, your function must have the correct name and provide output in the format specified above, you also need to abide by our other simple rules.

As always solutions using imports to do all the heavy lifting such as itertools will not be considered for the winner.

When including your repl.it link, please just give us the link and not the code preview! Just put a space before your URL so that the preview box doesn’t show – too many preview boxes can make the thread hard to read.

The fine print:

Click the links to find out more about:


Here is my submission in Python 3,
for both the basic and intermediate challenges:

def flattenArray(my_nest):
    # my_nest is a list, possibly nested, to ONE level
    my_flat = [] # initially empty, result list
    for my_item in my_nest:
        if type(my_item) is list:
            # if we have a list, then extend the result
            # with the item, an assumed flat list
        else: # otherwise append to the result, one item
    return my_flat # now flattened list
def flattenArrayN(my_nest):
    # my_nest is a list, possibly nested, to ANY level
    my_flat = [] # initially empty, result list
    for my_item in my_nest:
        if type(my_item) is list:
            # if we have a list, then extend the result
            # with a recursively flattened list
        else: # otherwise append to the result, one item
    return my_flat # now flattened list

print(flattenArray([1,2,3, [4,5], 6, [7,8], 9]))

print(flattenArrayN([1, 2, [3, [4, 5]], 6]))

I use a Python list to hold an arbitrary array.

For flattenArray I assume, at most, one level of nesting.
I make use of the list function extend,
which adds the “contents” of a list to the end of another list.
Essentially, performing a single flattening, in the process.

For flattenArrayN I allow for any reasonable depth of nesting.
The code is very similar, except that a recursive call is necessary.

Here is the output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, 5, 6]

And here is the link:



Python 3.6 -

I have created this function to check if an object is array or not, which is used below

def isIterable(anyObject):             # O(1)
    if hasattr(anyObject, '__iter__'):     # Check if the object has __iter__ attribute to consider it an iterable
        if not len(anyObject):         # if the iterable is not blank i.e. length is greater than 0, return true
            return True
        elif len(anyObject) > 0:
            # if iterable is not checked infinite times like string, return True
            if not next(iter(anyObject)) == anyObject:
                return True
        return False

Basic Challenge :

def flattenArray(inputArray):      # O(N)
    flatList = []
    for item in inputArray:        # Loop over every element(array or not) in the array
        # If the element is nested array, join it with output flat array
        # else just add the element to the flat array
        flatList += item if type(item) is list else [item]
    return flatList

print(flattenArray([1,2,3, [4,5], 6, [7,8], 9]))
Output :
flattenArray([1,2,3, [4,5], 6, [7,8], 9]) => [1, 2, 3, 4, 5, 6, 7, 8, 9]

Intermediate Challenge :
I had few different ideas to solve this challenge.
This one is quite unique and it does the job but unfortunately I am unable to find its Big O notation, so who knows it may the fastest way to flatten an array.

def flattenArrayN(inputArray):
    # from string representation of list, remove all brackets which represent arrays to make the list one dimension
    arrayString = str(inputArray).replace('[', '').replace(']', '').replace('{', '').replace('}', '').replace('(', '').replace(')', '').replace(',', ' ').replace(':', ' ')
    # get list of all elements
    list_ = arrayString.split()
    flatList = []
    # Since all the elements are string, convert them back to their original data type
    for element in list_:
    return flatList

print(flattenArrayN([1, 2, [3, [4, 5]], 6]))

In this solution, every loop flattens nested list(two dimension list). The total number of loop depends on the maximum dimension.

def flattenArrayN(inputArray):     # O(N*d) where N is number of elements of array and d is the number of dimensions of the array
    flatList = inputArray
    arrayFlattended = False         # to keep check on progress
    while not arrayFlattended:      # loops over array d times
        arrayFlattended = True
        list_ = flatList            # iterate over previously flattened list
        flatList = []               # current list
        for element in list_:
            if isIterable(element):  # if the element is an array, append all elements with the current list
                for innerElement in element.items() if type(element) is dict else element:
                    # if the array is dictionary, append its key, value pair else append the elements of the array, which will be flattened in the next loop if they are also array
                    if arrayFlattended:       # If no nested array found yet, check if the current innerElement is an array of not
                        if isIterable(innerElement): # If the elements of nested list are also array run the loop again to flatten it
                            arrayFlattended = False
    return flatList
print(flattenArrayN([1, 2, [3, [4, 5]], 6]))

# Working -
# [1, 2, [3, [4, 5]], 6]
# [1, 2, 3, [4, 5], 6]
# [1, 2, 3, 4, 5, 6]

This solution uses recursion. Instead of flattening the whole list dimension by dimension, just flatten each nested list recursively.

def flattenArrayN(inputArray):       # O(N+s) i.e. O(N) where N is the total number of elements in the array and s is the sum of number of elements of nested arrays(sum of all k), here N >= s
    flatList = []
    for item in inputArray:          # Iterate over the input array, O(N)
        if isIterable(item):         # check if item is an array
            # Join nested array(recursively flattened) with outermost array
            flatList += flattenArrayN(item if type(item) is not dict else item.items())      # O(k), where k is number of elements in nested array

    return flatList

print(flattenArrayN([1, 2, [3, [4, 5]], 6]))

All the intermediate solutions have same output except first one as it does not change string elements

Output :
flattenArrayN([1, 2, [3, [4, 5]], 6]) => [1, 2, 3, 4, 5, 6]

Hard Challenge :
This is my hard entry to the challenge again using recursion in which every element is appended to a list(which is 1D) by recursively getting into every nested list at a time.

def flattenArrayN(inputArray, flatList=0):   # O(N+d), i.e. O(N) where n is number of elements in input array(including only 2D arrays and not arrays nested in 2D arrays) and d is the dimension of innermost array
    if flatList == 0:      # if no argument is given initialize the array
        flatList = []
    for item in inputArray:          # Iterate over the input array, O(N)
        # Append elements of nested arrays recursively
        if isIterable(item):        # If the object is iterable, it is considered array and flattened
            if type(item) is dict:        # Different way to flatten dictionary than other arrays
                for pair in item.items():       # item.items() return an array of tuples containing key,value pair which is again recursively flattened
                    flattenArrayN(pair, flatList)
                flattenArrayN(item, flatList)
    return flatList

print(flattenArrayN([1, 2, [3, [4, 5]], 6]))
print(flattenArrayN([1, 2, [3, [4, [5, [6, [7, [8]]]]]], 9, [10, 11, [12, 13, [14, 15, [16, [17, [18, [19, [20]]]]]]]]]))
print(flattenArrayN([(1, 2, [3, {4, 5}], {6: 'seven'}), 8, 9, {10: 11}, [[{12}]]]))

The only significant difference between the two solution using recursion is that intermediate solution joins recursively flattened lists with final 1D list whereas hard solution appends elements from each nested list to final 1D list.

Output :
flattenArrayN([1, 2, [3, [4, 5]], 6]) => [1, 2, 3, 4, 5, 6]
flattenArrayN([1, 2, [3, [4, [5, [6, [7, [8]]]]]], 9, [10, 11, [12, 13, [14, 15, [16, [17, [18, [19, [20]]]]]]]]]) => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
flattenArrayN([(1, 2, [3, {4, 5}], {6: 'seven'}), 8, 9, {10: 11}, [[{12}]]]) => [1, 2, 3, 4, 5, 6, 's', 'e', 'v', 'e', 'n', 8, 9, 10, 11, 12]


EDIT ==> I have adjusted my solutions to flatten arrays of different types.


Easy, Intermediate, and (possibly) hard explained below:

const flattenArray = (arr) => {
	let flatArr = [];
	for (var i = 0; i < arr.length; i++){
		if (Array.isArray(arr[i])){
			for (var x = 0; x < arr[i].length; x++){
		} else {
	return flatArr; 

console.log(flattenArray([1,2,3, [4,5], 6, [7,8], 9]))
//returns [1,2,3,4,5,6,7,8,9]

Pretty straightforward- the function loops through an array. It determines if item i is itself an array. If so, it runs an inner loop and pushes the sub-item x into a new array. Otherwise, item i is pushed into the array. (Note, I explain below why I used a second array instead of modifying the existing array in-place)

The intermediate function basically does the same thing, but takes it a step further using recursion:

const flattenArrayN = (arr)=> {
	let flatArray = [];
	let loopAgain = false;
	for (var i = 0; i < arr.length; i++){
		if (!Array.isArray(arr[i])){
		} else {
			for (var x = 0; x < arr[i].length; x++){
			loopAgain = true;
	if (loopAgain) {
		return flattenArrayN(flatArray);
	} else {
		return flatArray;

console.log(flattenArrayN([1, 2, [3, [4, 5]], 6])); 
//returns [1,2,3,4,5,6]

In this function, the “easy” loop process from above runs, but this time adds a loopAgain variable that sets to true if the loop runs into an array item i. So, just like before, the loop iterates over array item i. If i is not an array, i gets pushed into a new array flatArray. Otherwise, an inner loop runs and pushes sub-item x into flatArray, and loopAgain is set to true. Once out of the outer loop, if loopAgain is true, the function calls itself recursively on flatArray and runs the same test, until all items checked are not arrays, and loopAgain is false.

Edited to add: here’s an attempt at optimizing the Easy challenge, also added to the repl.it link:

const altFlattenArray = (arr) => {
	let flatArray = [];
	flatArray = arr.toString().split(',');
	//now every item is a string, so convert numbers back to Number
		flatArray[index]=isNaN(Number.parseInt(item))? item: Number.parseInt(item);
	return flatArray;

This time, the array is only iterated once (after being split and then joined again, removing the single-nested arrays), instead of multiple passes like in the above easy function. I added the check to see if parseInt() returns NaN in case the original item in the array was already a string before .toString() was called. If so, just return the original string, otherwise convert the number string back to a number.

And another way to accomplish the easy challenge:

const flat2DHard = (arr)=> {
	let flat2D = [1, 2, [3, 4, 5], 6].reduce(function(acc,cv){
		return acc.concat(cv);
	return flat2D;

Here, as above, the function only makes one full pass through the array to flatten it, instead of multiple loops. However, the above function allows for any data type in the 2D array, since all it does is .concat() the individual items.

Link to repl.it showing matching output: https://repl.it/K9R9/0


Your function runs in time complexity of O(n*d) where n is the number of elements in the outermost list and d is the maximum number of dimension i.e. number of nested arrays inside outermost array which means it loops over outer most array for d times and everytime a nested array is flattened, no. of elements is outermost array increases. Your solution using recursion is a good one but can’t say its very efficient :slightly_smiling_face:


My first time participatin in a challenge here. My submission is in Ruby an for the Basic and Intermediate levels.

def flatten_array_n(array)
  target = [] # Create an array to store the extracted values.
  array.each do |v| # Iterate through the array
    if v.is_a?(Array) # If the value is an array flatten it recursively (to account for deeper levels)
      target.concat(flatten_array_n(v)) # Then append each value to the target array
    else # If it's anything other than an array, append it to the target array
  target # Return

puts flatten_array_n([1, 2, [3, [4, 5]], 6]).to_s

It’s type agnostic and can deal with any number of nested levels.


Here is my entry for the Basic Challenge in Python 2.7… https://repl.it/K7tW/2

test = [1, 2, 3, [4, 5], 6, [7, 8], 9, "10", {"eleven": 11, "twelve": 12}, 13, ["14", "15"]] # Creates a test array

def flattenArray(lst):
    results = [] # Creates an empty array called results.
    for each in lst: # Loops through the original (unflattened) array
        if type(each) is list or type(each) is tuple: # Checks if the item is either an array or a tuple. 
            for n in each: # Loops through the item. This is because arrays and tuples can be iterated through in the same way.
                results.append(n) # Appends the item to results
        elif type(each) is dict: # Checks if the item is a dictionary type. 
            for n in each.items(): # Loops through the dictionary and converts each key/value pair into a tuple.
                for i in n: # Loops through the tuple.
                    results.append(i) # Appends the item to results.
            results.append(each) # Appends all items that are not within a dictionary, a tuple, or an array to results.
    return results # Returns results, which is now a flat array.

print "Before:", test # Prints the original (unflattened) array.
print "After:", flattenArray(test) # Prints the flattened array.


Cool, thanks! Still getting my head around complexity theory, and based on your reply, I definitely see how my solution can get pretty expensive pretty quickly.


This is my submission in Javascript.
It calls the function recursively in order to flatten any nested n-levels deep arrays.
This is the code:

function flattenArrayN(arr, newArr) {
  //Loop through the array
  for(let i = 0; i < arr.length; i++) {
    //If the element is an object, recursively call the function
    //to flatten the arrays that are nested n-levels deep
    if(typeof(arr[i]) === 'object' && arr[i] !== null) {
      flattenArrayN(arr[i], newArr);
    } else { //Otherwise, add the element to a new flattened array
  return newArr; //return the flattened array

//Output: [1, 2, 3, 4, 5, 6, "", undefined, null, 7]
console.log(flattenArrayN([1, 2, [3, [4, 5]], 6, '', undefined, null, {}, [], 7], []));

//Output: [1, 2, 3, 4, 5, 6]
console.log(flattenArrayN([1, 2, [3, [4, 5]], 6], []));

 //Output: [1, 2, 3]
console.log(flattenArrayN([[[[[1, 2]]]], 3], []));

//Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(flattenArrayN([1, 2, 3, [4, 5], 6, [7, 8], 9], []));

//Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
console.log(flattenArrayN([1, 2, 3, [4, 5], 6, [7, 8, 9], 10, [11, 12, [13, 14, 15]]], []));


This is my first time participating in a challenge! My submission is in Python3 and is for the intermediate (and possibly hard) challenge:

from copy import copy

def flattenArrayN(list_in): #list_in is the list we wish to flatten
    list_out = copy(list_in) #adjust this until we get desired result
    j = 0 #iterates through integer labels of list_out
    while j < len(list_out):
        if isinstance(list_out[j], list) == True: #checks if a given element of list_out is a list
            temp_list = list_out[j] #result[j] is a list, make a copy of that list
            for s in temp_list[::-1]: #goes through elements of temp_list from right to left
                list_out.insert(j+1,s) #adds s directly after list at element j
            del list_out[j] #after removing elements of list in list_out at j, remove the list
            j += 1 #if list_out[j] is not a list, move on to the next element
    return list_out
#test run:    
k = [1, 2, [3, [4, 5]], 6]

Here’s how it works. We first make a copy of the input list and call it list_out. We go through each element of list_out and check if that element is itself a list. If it is not a list, we move on to the next element. If the element is a list, we replace that list with its contents and repeat the process starting from the first new element. The way we replace that list is to go through its elements starting from the right, and insert them ahead of the list. Once we go through that whole list, we delete it. After going through all of list_out, we return it. Here’s an example to illustrate the process:
-> [1,2,[3,4,[5]], 3,4,[5],6]
-> [1,2,3,4,[5],6]

Here is a link to the code: https://repl.it/KbV3/3

I think a neat modification of the code would be to allow the user to only partially flatten an array. For example, if the input array is 5 dimensional, the user could decide if the output array is 4, 3, 2, or 1 dimensional.


Given N dimentional array - A.
Elements of A can be:

  1. items to be flattern - L
  2. N-1 (or less) dimentional arrays - N

Consider A as a tree, where root of that three is the pointer to A.
Then L - are leafes, and N- are nodes of our tree.

To flattern A we should traverse tree in deep and collect all leafes. Recursion and Stack are most simple ways to traverse a tree. I have choose Stack as more ‘controllable’ method, and because in Python we have a great tool for saving traversing context in stack - iterators.

All uncertainties isolated in subroutine inside function. Modifications can be done to add or skip , () elements, to deal with string like objects, etc.

Python3: https://repl.it/Kc1E/15

def flattenArrayN(ArrayN):
    def lookDeeper(el):
        Test given element is Node or Leaf
        Return None for Leaf, iterator for Node
            itr = iter(el)
        except TypeError:
            itr = None
            # Check for infinite loop
            check_itr = iter(el)
            if (len(el) > 0):
                check_el = next(check_itr)
                if (check_el is el):
                    # Stop infinite loop for string like objects
                    itr = None
                # Element contains nothing - Leaf
                itr = None
        return itr
    # Start from Root        
    itr = lookDeeper(ArrayN);
    # Prepare traverse stack
    itr_stack = []
    # Result list
    flat = []
    while (itr != None):
        # Get element from sequnce
            el = next(itr)
        except StopIteration:
            # End of current level sequence
            # Check stack for untraversed branches
            if len(itr_stack) > 0:
                itr = itr_stack.pop()
                itr = None
            # Test element for Leaf/Node
            deeper_itr = lookDeeper(el)
            if (deeper_itr == None):
                # Leaf - get it
                # Push current level traverse context
                # Go deeper
                itr = deeper_itr
    return flat

test = [1, 2, [3, [4, 5]], 6]
print('test: ', test)
print('flat: ', flattenArrayN(test))

test = [([],), [(None, {None}), 1, 2, 3], {4, 5}, [6, 7, (8,{9})], 'END', ""]
print('test: ', test)
print('flat: ', flattenArrayN(test))


Python 3.6 Hard

class FlattenArray:
    This class assumes that the values in the input array(list) is either of 
    type int or list. As we run through the vales, ints are appended and 
    lists are extended.

    def __init__(self, nested_array):
        self.__flat_array__ = list()

    def __repr__(self):
        return str(self.flat_array)

    def __flatten__(self, nested_array):

        for element in nested_array:

            if isinstance(element, int):


    def flat_array(self):
        return self.__flat_array__
from collections import deque

class FlattenArrayN:
    This class uses the __flatten__ method recursively. Each element 
    is type checked. If it is of one of the atomic types (int, string, None),
    it is appended to the __flat_array__ list. 
    If the element is of type list, the __flatten__ method is called again 
    with the list object as input. 
    If the element is of type dict, we loop through each of the key, value
    pairs and hand them to the __flatten__  method as small lists [key, value]
    When the recursion is complete, the flattening is also complete.

    def __init__(self, nested_array):
        self.__flat_array__ = list()

    def __repr__(self):
        return str(self.flat_array)

    def __flatten__(self, nested_array):

        for element in nested_array:

            if isinstance(element, int):

            elif isinstance(element, str):
                if element.isdigit():

            elif element is None:

            elif isinstance(element, list):
            elif isinstance(element, tuple):

            elif isinstance(element, set):

            elif isinstance(element, deque):

            elif isinstance(element, dict):

                for item in element.items():

            # takes care of OrderedDict, Counter and defaultDict
            # from the collections module
            elif issubclass(element, dict):

                for item in element.items():

    def flat_array(self):
        return self.__flat_array__

Running the code

if __name__ == '__main__':
    flatten_array = FlattenArray([1, 2, 3, [4, 5], 6, [7, 8], 9])

    flatten_array_n = FlattenArrayN(
        [1, (2, 3), [4, {None: ["crazy_time", "Duffman!"]}, 5], 
        6, {"7": {8: None}, "nine":  10}, deque(["10a", "10b"]),
        11, None, [[[[[[[[set([12])]]]]]]]]]



[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 2, 3, 4, None, 'crazy_time', 'Duffman!', 5, 6, '7', 8, None, 'nine', 10, 11, None, 12]


#Typo: double closing parentheses 6])) with a single opening


@danieloduffy: Took care of it for you.

@designslayer50856: Thanks for pointing that out, Daniel.


Another typo @danieloduffy or @mtf


Do we also need to unpack immutable types such as tuple and string to get 1D array in addition to mutable types such as list, set, dictionary ?


Intermediate Challenge in Python

def flattenArrayN(ar,al=[]):
    if isinstance(ar,list) or isinstance(ar,tuple) or isinstance(ar,set):
        for l in ar:
    elif isinstance(ar,dict):
        for x in ar.iteritems():
    return al

inp = [1,2,[3,[4,5]],6]
inp2 = [1,2,3,[4,5],6,[7,8],9]
inp3 = ['ada',{1:2,23:54}, (3,4),[('lol',34,''),67,[5,78]], (['c','d','e'])]
print flattenArrayN(inp3)


['ada', 1, 2, 23, 54, 3, 4, 'lol', 34, '', 67, 5, 78, 'c', 'd', 'e']

This recursive function creates a new array, flattens nested lists, tuples, sets and dictionaries, and simply adds all other type elements into the new, flat array. Simple, but probably not very efficient. The structure of dictionary is being completely flattened, but keys and respective values are placed next to each other in the resulting list.

[Edited to handle dicts and sets]



Nice and compact, but ya forgot to handle the dict :slight_smile:


You forgot to handle the set :slightly_smiling_face:


That’d be outside of the scope of the prompt, but if you wanted to go above and beyond, don’t let us stop you!