1

I am aware of the recursive way to flatten a nested array. There are several solutions on stackoverflow (both in java and javascript - some using built in libraries).

But the time complexity of these solutions is O(n^2)! I was wondering if there is an algorithm which could do better.

Thanks in advance for your help!

Community
  • 1
  • 1
Karthik Vasishta Ramesh
  • 109
  • 2
  • 15
  • 6
    They look like O(n) where n is the number of elements. I don't see how you will get better than that. – Peter Lawrey Feb 11 '17 at 17:17
  • Is n dimension of array you are referring to?, but If n is number of elements its considered O(n) – mc20 Feb 11 '17 at 17:18
  • The answer from "Adam" in that JavaScript question you linked is linear, not quadratic. @VinceEmigh it's not reasonable when it's trivial to do it in linear time :) – Pointy Feb 11 '17 at 17:19
  • @PeterLawrey well the versions that use some sort of array concatenation functions are not really linear, but doing it by building a single accumulator array is linear if you ignore the cost of a dynamically-sized array. – Pointy Feb 11 '17 at 17:21

1 Answers1

4

You are either mistaken or you define your n as the root square of number of elements to process.

All the sane solutions of the array flattening problem are O(n), where n depends on the total number of elements (because, essentially, you need to scan them all, each of them only once). Flattening an array is not an algorithmic problem, it's just the question of getting it in an "elegant" snippet.

fdreger
  • 12,264
  • 1
  • 36
  • 42
  • I see. Please correct me if I am wrong, but is it safe to say that it is pseudo-polynomial then? – Karthik Vasishta Ramesh Feb 11 '17 at 17:24
  • 1
    @KarthikVasishta big-O is always the highest order of the polynomial. – Peter Lawrey Feb 11 '17 at 17:26
  • Thanks @PeterLawrey – Karthik Vasishta Ramesh Feb 11 '17 at 17:30
  • 1
    *"you need to scan them all, each of them **only once**"*. That's not true for Java. Since Java arrays are fixed-size, you have to pre-scan the arrays to find the total number of elements for the result, before you can start building it. Still *O(n)* though. – Andreas Feb 11 '17 at 17:36
  • @Andreas: I appreciate your nit-pick :-) But if we interpret things at this level, the question is not really valid - there is no "array" in Javascript (unless you count the Typed Arrays API, which is not part of ECMA) - so the cost of just adding N elements to a javascript "array" probably gets us around NlogN (to pay for growing the array). In my reply I assumed that the equivalent of Javascript "array" is Java's LinkedList :-) – fdreger Feb 12 '17 at 23:15