Java- Flatten an array using recursion

Question

I have been practicing algorithms, and recursion is always my weak point. This problem asks to flatten a nested array into a single array. This would be simple if using a loop giving an O(n^3) [given an equally sized 3d array] solution.

However with recursion I have been struggling for a few hours. This is what I have, please note I have dabbled with my code trying out different solutions, this is just what I decided to leave it at to post up to you guys.

What I want are two things, is there anyway to fix my current code to get the correct output, and is there a simpler and less messy way to write this code using recursion, thanks!

Bonus Questions, if I did not know the dimensions of the nested array, how would I go about this problem then using recursion?

EDIT Ok so after some hard coding(which i do not want to do), I managed to get this to work. But the code is now hard coded and very messy, is there anyway to clean up the code or go about a simpler way to solve this using recursion?

EDIT2 I am attempting redo-ing this problem using helper method recursion. I'll see if I have better luck using this style

import java.io. * ;
    import java.util. * ;
    class Solution {
    // static int oneLen = 0;
    //static int twoLen = 0;
    //static int threeLen = 0;

    static int oneCnt = 0;
            static int twoCnt = 0;
            static int threeCnt = 0;
            static ArrayList < Integer > result = new ArrayList < Integer > ();
            public static ArrayList < Integer > flatten(int [][][] arr){

    if (oneCnt < arr[threeCnt][twoCnt].length && !(oneCnt == 2 && twoCnt == 2 && threeCnt == 2))
    {


    if (oneCnt == 0 && twoCnt == 0 && threeCnt == 0){
    result.add(arr[threeCnt][twoCnt][oneCnt]);
            oneCnt++;
            result.add(arr[threeCnt][twoCnt][oneCnt]);
            System.out.println("Line One");
            System.out.println("Count1:  " + oneCnt);
            System.out.println("Count2:  " + twoCnt);
            System.out.println("Count3:  " + threeCnt);
    }
    oneCnt++;
            if (oneCnt != 3){
    result.add(arr[threeCnt][twoCnt][oneCnt]); }






    System.out.println("Line One");
            System.out.println("Count1:  " + oneCnt);
            System.out.println("Count2:  " + twoCnt);
            System.out.println("Count3:  " + threeCnt);
            flatten(arr);
    }     else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt < arr[threeCnt].length - 1){


    //oneLen = 0;    
    oneCnt = 0;
            // twoLen++;


            twoCnt++;
            result.add(arr[threeCnt][twoCnt][oneCnt]);
            System.out.println("Line Two");
            System.out.println("Count:1  " + oneCnt);
            System.out.println("Count:2  " + twoCnt);
            System.out.println("Count:3  " + threeCnt);
            flatten(arr);
    }

    else if (oneCnt == arr[threeCnt][twoCnt].length && twoCnt == arr[threeCnt].length - 1 && threeCnt < arr.length - 1){

    oneCnt = 0;
     twoCnt = 0;
            threeCnt++;
            result.add(arr[threeCnt][twoCnt][oneCnt]);
            System.out.println("Line Three");
            System.out.println("Count:1  " + oneCnt);
            System.out.println("Count:2  " + twoCnt);
            System.out.println("Count:3  " + threeCnt);
            flatten(arr);
    }
    return result;
    }
    public static void main(String[] args) {
    int[][][] array =
    {  { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} },
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} },
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } };
            flatten(array);
            for (int i = 0; i < result.size(); i++){
    System.out.print(result.get(i) + ",");
    }
    }
    }

output: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,

Edit3 After using helper recursion I almost have the answer, but the last element wont add to the arraylist.

import java.io. * ;
    import java.util. * ;
    class Solution {



    static ArrayList < Integer > result = new ArrayList < Integer > ();
            public static void flatten(int [][][] arr){
    int oneLen = 0;
            int twoLen = 0;
            int threeLen = 0;
            flattenHelper(arr, oneLen, twoLen, threeLen);
    }

    public static void flattenHelper(int [][][] arr, int oneLen, int twoLen, int threeLen){

    if (oneLen < arr[threeLen][twoLen].length - 1){
    System.out.println("Line One");
            System.out.println("Count:1  " + oneLen);
            System.out.println("Count:2  " + twoLen);
            System.out.println("Count:3  " + threeLen);
            result.add(arr[threeLen][twoLen][oneLen]);
            flattenHelper(arr, oneLen + 1, twoLen, threeLen);
    }
    else if (twoLen < arr[threeLen].length - 1){
    System.out.println("Line Two");
            System.out.println("Count:1  " + oneLen);
            System.out.println("Count:2  " + twoLen);
            System.out.println("Count:3  " + threeLen);
            result.add(arr[threeLen][twoLen][oneLen]);
            flattenHelper(arr, oneLen = 0, twoLen + 1, threeLen);
    }     else if (threeLen < arr.length - 1){
    System.out.println("Line Two");
            System.out.println("Count:1  " + oneLen);
            System.out.println("Count:2  " + twoLen);
            System.out.println("Count:3  " + threeLen);
            result.add(arr[threeLen][twoLen][oneLen]);
            flattenHelper(arr, oneLen = 0, twoLen = 0, threeLen + 1);
    }

    }

    public static void main(String[] args) {
    int[][][] array =
    {  { {1, 2, 3}, { 4, 5, 6}, { 7, 8, 9} },
    { {10, 11, 12}, {13, 14, 15}, {16, 17, 18} },
    { {19, 20, 21}, {22, 23, 24}, {25, 26, 27} } };
            flatten(array);
            for (int i = 0; i < result.size(); i++){
    System.out.print(result.get(i) + ",");
    }
    }
    }

output: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,

score 7 · Accepted Answer · edited May 23 '17 at 10:27

It's recursive, you don't need to change the input structure and it doesn't need to know the dimension of your array. You can go crazy and mix Arrays, Lists and other objects, it will return an ArrayList :

package stackOverflow;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.List;

public class Solution
{
    public static void main(String[] args) {
        int[][][] int3dArray = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } },
                { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } },
                { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 }, { 29, 30 } } };
        String[][] string2dArray = { { "He, llo" }, { "Wo", "rld" } };
        String[] stringArray = { "Hello", "World" };
        Object[] objectArray = { "Hell", 0, "W", 0, "rld" };

        List<Object> mixList = new ArrayList<Object>();
        mixList.add("String");
        mixList.add(3);
        mixList.add(string2dArray);

        System.out.println(flatten(int3dArray));
        System.out.println(flatten(flatten(int3dArray)));
        System.out.println(flatten(3));
        System.out.println(flatten(stringArray));
        System.out.println(flatten(string2dArray));
        System.out.println(flatten(objectArray));
        System.out.println(flatten(mixList));
    }

    private static List<Object> flatten(Object object) {
        List<Object> l = new ArrayList<Object>();
        if (object.getClass().isArray()) {
            for (int i = 0; i < Array.getLength(object); i++) {
                l.addAll(flatten(Array.get(object, i)));
            }
        } else if (object instanceof List) {
            for (Object element : (List<?>) object) {
                l.addAll(flatten(element));
            }
        } else {
            l.add(object);
        }
        return l;
    }
}

It outputs :

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
[3]
[Hello, World]
[He, llo, Wo, rld]
[Hell, 0, W, 0, rld]
[String, 3, He, llo, Wo, rld]

Here's a modified version, which also flatten Maps to a collection of values. It can output either a Set or a List.

Here is my original solution, which only displayed the results, but returned void :

package stackOverflow;

import java.lang.reflect.Array;


public class Solution
{
    public static void main(String[] args) {
        int[][][] array = { { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } },
                { { 10, 11, 12 }, { 13, 14, 15 }, { 16, 17, 18 } },
                { { 19, 20, 21 }, { 22, 23, 24 }, { 25, 26, 27 }, { 28 } } };
        flatten(array);
    }

    private static void flatten(Object object) {
        if (object.getClass().isArray()) {
            for (int i = 0; i < Array.getLength(object); i++) {
                flatten(Array.get(object, i));
            }
        } else {
            System.out.print(object + ",");
        }
    }
}

It returns : 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,

Thank you! This is exactly what I was looking for in terms of also answering the bonus questions I had. — user3051442, Oct 22 '16 at 00:14
Can I ask what the reflect library does and how it correlates to this solutions? Trying to find some documentation on it, thank you. — user3051442, Oct 22 '16 at 00:15
Here is a good start : https://docs.oracle.com/javase/tutorial/reflect/ It basically makes Java a little bit less "rigid", and brings some methods that are more commonly found in languages like Python and Ruby. Sometimes, you cannot know everything at compile time, and need to wait for runtime. Like : I know this object will look like an Array, it might be int[][] or it might be ArrayList, I just want to iterate over all the elements. — Eric Duminil, Oct 22 '16 at 00:41

score 1 · Answer 2 · answered Oct 21 '16 at 23:48

If you can change the data to be arrays of Integer instead of int, you can inspect the elements of the array passed and recurse for elements that are arrays or just add them directly to the result if not.

public static ArrayList<Integer> flatten(Object [] arr) {
    ArrayList<Integer> result = new ArrayList<>();

    for (int i = 0; i < arr.length; i++) {
        if (arr[i].getClass().isArray()){
            result.addAll(flatten((Object[])arr[i]));
        } else {
            result.add((int)arr[i]);
        }
    }

    return result;
}

Java- Flatten an array using recursion

2 Answers2

Linked