Can I flatten an array without making a new list/array?

Question

Let's say I have arr = [[1], [0, 0], [2], [3], [0, 0], [4]]

Could I flatten this into [1, 0, 0, 2, 3, 0, 0, 4] without having to use itertools, map/reduce, or a list comp? I am struggling to figure out a way to do this. Thanks.

This is what I have tried so far, it is a leetcode question: https://leetcode.com/problems/duplicate-zeros/

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        
        """
        for ix in range(len(arr) - 2):
            if arr[ix] == 0:
                arr[ix] = [0, 0]
                del arr[-1]
            else:
                l = []
                l.append(arr[ix])
                arr[ix] = l

# Output when you return arr is [[1],[0, 0],[2],[3],[0, 0],[4]]

Why don't you want to use a list comprehension ? It seems to be the best solution to flatten a list. — LCMa, Nov 12 '20 at 13:50
"without having to use itertools, map/reduce, or a list comp" - that seems really arbitrary. Why rule out those tools? If you knew of something else that could flatten nested lists, would you have ruled that out too? — user2357112, Nov 12 '20 at 13:50
Could you point out why you don't want to use list comprehensions, itertools, etc.? Comprehensions allow quite simple and Pythonic solutions: `[x for items in arr for x in items]` — Frank, Nov 12 '20 at 13:50
Arbitrary ruling out things to use [check] - No code yet [check] - Homework? — Patrick Artner, Nov 12 '20 at 13:53
One way can be: `list(list(zip(*arr))[0])` it's really bad answer ... someone can answer it well — Shashank, Nov 12 '20 at 13:53
It's a leetcode question. I've edited my my question to show what I've tried so far. — User_13, Nov 12 '20 at 14:04
That leetcode problem has nothing to do with what you're asking for. Flattening nested lists isn't involved at all. — user2357112, Nov 12 '20 at 14:21
right, but that's the approach i took towards tackling the problem. Sure its messy but I am kinda disappointed with the reaction to my question. Dunno why it warrants these downvotes (my fault for not be specific enough pre-edit I guess) — User_13, Nov 12 '20 at 14:46

score 3 · Answer 1 · answered Nov 12 '20 at 13:55

3

You can simply do:

arr = sum(arr, [])

What you are doing here is adding the iterable elements of arr taking an empty array [] as initial value.

answered Nov 12 '20 at 13:55

lorenzozane

1,214
1
5
15

1

This is extremely inefficient - it's quadratic time. – user2357112 Nov 12 '20 at 14:20
@user2357112supportsMonica I agree, I do not argue about this. Mine is just another possible solution that when I posted was in accordance with the question requirements (do not use list comprehension, map, reduce, do not create a new list). As you can see the question requirements are quite restrictive, and I'm noticing that they are also changing, it has already been edited several times. Maybe it is not the best solution, it is a possible solution. If there are better ones I will be happy to learn something too – lorenzozane Nov 12 '20 at 14:31

score 1 · Answer 2 · answered Nov 12 '20 at 13:54

Try some recursion:

def flatten(lst):
    ans = []
    for el in lst:
        if type(el) == list:
             for e in flatten(el):
                 ans.append(e)
        else:
            ans.append(el)
    return ans

It will flatten any-dimensionanal lists.

Emma · Accepted Answer · 2020-11-12T14:49:04.010

We can also use the list copy ([:]) here, for solving the problem:

class Solution:
    def duplicateZeros(self, A):
        """
        Do not return anything, modify arr in-place instead.
        """
        A[:] = [x for num in A for x in ([num] if num else [0, 0])][:len(A)]

Additionally, the optimal solution would be an order of N runtime with constant memory. That's already been addressed by LeetCode here:

class Solution:
    def duplicateZeros(self, arr: List[int]) -> None:
        """
        Do not return anything, modify arr in-place instead.
        """

        possible_dups = 0
        length_ = len(arr) - 1

        # Find the number of zeros to be duplicated
        for left in range(length_ + 1):

            # Stop when left points beyond the last element in the original list
            # which would be part of the modified list
            if left > length_ - possible_dups:
                break

            # Count the zeros
            if arr[left] == 0:
                # Edge case: This zero can't be duplicated. We have no more space,
                # as left is pointing to the last element which could be included  
                if left == length_ - possible_dups:
                    arr[length_] = 0 # For this zero we just copy it without duplication.
                    length_ -= 1
                    break
                possible_dups += 1

        # Start backwards from the last element which would be part of new list.
        last = length_ - possible_dups

        # Copy zero twice, and non zero once.
        for i in range(last, -1, -1):
            if arr[i] == 0:
                arr[i + possible_dups] = 0
                possible_dups -= 1
                arr[i + possible_dups] = 0
            else:
                arr[i + possible_dups] = arr[i]

Can I flatten an array without making a new list/array?

3 Answers3