 # 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.

### 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.

### 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!

### 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!

#### `Reply` to this thread with a link to your code on repl.itand 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:

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
my_flat.extend(my_item)
else: # otherwise append to the result, one item
my_flat.append(my_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
my_flat.extend(flattenArrayN(my_item))
else: # otherwise append to the result, one item
my_flat.append(my_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]
``````

https://repl.it/K8op/10

4 Likes

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
else:
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_:
try:
flatList.append(eval(element))
except:
flatList.append(element)
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
flatList.append(innerElement)
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
else:
flatList.append(element)
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
else:
flatList.append(item)

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)
else:
flattenArrayN(item, flatList)
else:
flatList.append(item)

return flatList

print(flattenArrayN([1, 2, [3, [4, 5]], 6]))
print(flattenArrayN([1, 2, [3, [4, [5, [6, [7, ]]]]], 9, [10, 11, [12, 13, [14, 15, [16, [17, [18, [19, ]]]]]]]]))
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, ]]]]], 9, [10, 11, [12, 13, [14, 15, [16, [17, [18, [19, ]]]]]]]]) => [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]
``````

https://repl.it/KfPl

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

2 Likes

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

``````//Easy:
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++){
flatArr.push(arr[i][x]);
};
} else {
flatArr.push(arr[i]);
}
};
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])){
flatArray.push(arr[i]);
} else {
for (var x = 0; x < arr[i].length; x++){
flatArray.push(arr[i][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.forEach(function(item,index){
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

2 Likes

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 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.push(v)
end
end
target # Return
end

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.
https://repl.it/K95u/3

2 Likes

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.
else:
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.
``````
1 Like

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
newArr.push(arr[i]);
}
}
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]]], []));
``````
2 Likes

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
else:
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]
print(flattenArrayN(k))
print(k)
``````

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,],6]
-> [1,2,[3,4,], 3,4,,6]
-> [1,2,3,4,,6]
->[1,2,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.

3 Likes

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
"""
try:
itr = iter(el)
except TypeError:
itr = None
else:
# 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
else:
# 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
try:
el = next(itr)
except StopIteration:
# End of current level sequence
# Check stack for untraversed branches
if len(itr_stack) > 0:
itr = itr_stack.pop()
else:
itr = None
else:
# Test element for Leaf/Node
deeper_itr = lookDeeper(el)
if (deeper_itr == None):
# Leaf - get it
flat.append(el)
else:
# Push current level traverse context
itr_stack.append(itr)
# 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))
``````
3 Likes

Python 3.6 Hard
https://repl.it/KcvO/1

``````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()
self.__flatten__(nested_array)

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

def __flatten__(self, nested_array):

for element in nested_array:

if isinstance(element, int):
self.flat_array.append(element)

else:
self.flat_array.extend(element)

@property
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()
self.__flatten__(nested_array)

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

def __flatten__(self, nested_array):

for element in nested_array:

if isinstance(element, int):
self.flat_array.append(element)

elif isinstance(element, str):
if element.isdigit():
self.flat_array.append(int(element))
else:
self.flat_array.append(element)

elif element is None:
self.flat_array.append(element)

elif isinstance(element, list):
self.__flatten__(element)

elif isinstance(element, tuple):
self.__flatten__(element)

elif isinstance(element, set):
self.__flatten__(element)

elif isinstance(element, deque):
self.__flatten__(element)

elif isinstance(element, dict):

for item in element.items():
self.__flatten__(item)

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

for item in element.items():
self.__flatten__(item)

@property
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()]]]]]]]]]
)

print(flatten_array)
print(flatten_array_n)
``````

Output

``````[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]
``````
2 Likes

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

@danieloduffy: Took care of it for you.

@designslayer50856: Thanks for pointing that out, Daniel.

3 Likes

Another typo @danieloduffy or @mtf

2 Likes

@danieloduffy
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 ?

1 Like

Intermediate Challenge in Python

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

inp = [1,2,[3,[4,5]],6]
inp2 = [1,2,3,[4,5],6,[7,8],9]
print flattenArrayN(inp3)
``````

Output:

``````['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]

https://repl.it/KhgH/4

2 Likes

Nice and compact, but ya forgot to handle the dict You forgot to handle the set 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!

2 Likes