user3051442 user3051442 - 1 month ago 13
Java Question

Java- Flatten an array using recursion

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,

Answer

It's recursive, you don't need to change the input structure and it doesn't need to know the dimension of your array :

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,

With some tweaks, it could return an ArrayList or a String without trailing ",".