6
\$\begingroup\$

I am certain there is a better way to flatten the array with an optimized approach for the solution.

Example:

[[1,2,24],[12,1241,122],[3,2],[7]] => 1 12 3 7 2 1241 2 24 122


public class flattenArray {

public static void main(String args[]) {

    int inputLists[][] = {{1,2,24},{12,1241,122},{3,2},{7}};

    flattenList(inputLists);

}

public static void flattenList(int input[][]){
    List result = new ArrayList();
    Map<Integer, List<Integer>> elements = new HashMap<Integer,List<Integer>>();
    for(int i=0;i<input.length;i++){
        for(int j=0;j<input[i].length;j++){

            List<Integer> temp = new ArrayList<Integer>();


            if(elements.get(j)!=null) {
                temp=elements.get(j);
                temp.add(input[i][j]);
                elements.put(j, temp);
            }

            else {
                temp.add(input[i][j]);
                elements.put(j,temp);
            }
        }
    }

    for(int i=0;i<input.length;i++){
        if(elements.get(i)!=null)
        result.addAll(elements.get(i));
    }

    for(int i=0;i<result.size();i++){
        System.out.println(result.get(i)+" ");
    }
}
}
\$\endgroup\$
0

4 Answers 4

5
\$\begingroup\$

Don't use raw types:

List result = new ArrayList();

Should be:

List<Integer> result = new ArrayList<>();

If you are using Java8, you could simplify the code of the map creation using the function computeIfAbsent:

for (int i = 0; i < input.length; i++){
    for (int j = 0; j < input[i].length; j++){
        elements.computeIfAbsent(j, k -> new ArrayList<>()).add(input[i][j]);
    }
}

In the next loop, you are using the break condition incorrectly.

for(int i=0;i<input.length;i++){ // input.length is not what you need 
    if(elements.get(i)!=null)
        result.addAll(elements.get(i));
}

input.length is the number of arrays in your 2d array. If the length of any array is greater than the number of arrays, the code is skipping values.

This is a failed test:

Input: {{1,2,24},{12,1241,122}} 
Output: 1 12 2 1241
Expected: 1 12 2 1241 24 122

You don't need to use input in the loop, you have a map with all the elements for each index, so you can make the conversion using only the map:

// Use a TreeMap instead of a HashMap to have the elements ordered by index
Map<Integer, List<Integer>> elements = new TreeMap<Integer,List<Integer>>();
...
for (List<Integer> e : elements.values()) {
    result.addAll(e);
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks David. That is a good catch. for(int i=0;i<input.length;i++){ // input.length is not what you need if(elements.get(i)!=null) result.addAll(elements.get(i)); } would it be best to hold the max key in the HashMap and run up to that value and spit out the values in the next list \$\endgroup\$ Aug 24, 2016 at 15:35
5
\$\begingroup\$

Separate concerns

You shouldn't output in the same method that generates the results.

    for(int i=0;i<result.size();i++){
        System.out.println(result.get(i)+" ");
    }

You don't need to use an index variable here.

    for (int element : flattenArrays(inputArrays)) {
        System.out.println(element);
    }

I also removed the + " ", as it doesn't really do anything if you print a new line each time.

I moved this into main and changed flattenArrays to return a List. I changed flattenLists to flattenArrays as being more descriptive. And changed inputLists to inputArrays to match.

Now you can choose to display the results. Or you can manipulate them further. It's your choice. Before you would have had to rewrite the method in order to do something other than display or even just to make a display change. Now you can leave the method untouched and choose how and what to display in the caller.

Don't waste objects

            List<Integer> temp = new ArrayList<Integer>();


            if(elements.get(j)!=null) {
                temp=elements.get(j);
                temp.add(input[i][j]);
                elements.put(j, temp);
            }

            else {
                temp.add(input[i][j]);
                elements.put(j,temp);
            }

You create a new ArrayList on every iteration, but you only use it occasionally. Why not simplify things?

            List<Integer> temp = elements.get(j);
            if (temp == null) {
                temp = new ArrayList<>();
                elements.put(j, temp);
            }

            temp.add(input[i][j]);

You don't have to put into the Map things on which you previously did a get. They're already in the Map. This is because you have a reference to that List. So you are modifying the List already in the Map.

So instead of having two paths, we have one path. We just need to ensure that there is already a List in the Map for j. If not, then we need to create one and put it in the Map. Again, we can do this before we modify the List, as we still have the reference to it after we put it in the Map.

We only call get once this way, regardless of path.

But why use a Map or other intermediate data structure at all?

Don't overcomplicate things

    public static List<Integer> flattenArrays(int input[][]) {
        List<Integer> results = new ArrayList<>();

        int previousSize;
        int column = 0;
        do {
            previousSize = results.size();

            for (int[] row : input) {
                if (row.length > column) {
                    results.add(row[column]);
                }
            }

            column++;
        } while (previousSize != results.size());

        return results;
    }

This copies the data directly, without any intermediate variables. It does so at the cost of checking each array for as many elements as the longest array has.

I changed result to results, as it is a List and can have multiple values (or none).

It would be possible to use Arrays.asList(input) with the iterator remove method to pop out the finished arrays.

    public static List<Integer> flattenArrays(int input[][]) {
        List<Integer> results = new ArrayList<>();
        List<int[]> data = new ArrayList<>(Arrays.asList(input));

        for (int column = 0; !data.isEmpty(); column++) {
            Iterator<int[]> it = data.iterator();
            while (it.hasNext()) {
                int[] row = it.next();
                if (row.length > column) {
                    results.add(row[column]);
                } else {
                    it.remove();
                }
            }
        }

        return results;
    }

I'll leave it up to you if the savings in comparisons is worth the increased overhead of the extra data structure.

I would find either of these easier to follow than the Map method.

\$\endgroup\$
4
\$\begingroup\$

You can transpose the array and then flat it. This approach to me seems more intuitive than putting elements on a map.

However transpose needs to be implemented with the particularity to support jagged arrays. In order to make an implementation you might need to make some assumptions.

I made an assumption that row(i).length >= row(j).length, where i < j

public static int[][] transpose(int[][] values){
    int[][] transposed = new int[values[0].length][];

    int minLastLenIdx = values.length - 1;
    for (int i = 0; i < values[0].length; ++i)
    {
        while(values[minLastLenIdx].length < i + 1){
            minLastLenIdx--;
        }

        transposed[i] = new int[minLastLenIdx + 1];
    }

    for (int i = 0; i < values.length; i++)
    {
        for (int j = 0; j < values[i].length; j++)
        {
            transposed[j][i] = values[i][j];
        }
    }
    return transposed;
}

public static int[] flattenList(int input[][]){
    return Arrays.stream(transpose(input))
                 .flatMapToInt(Arrays::stream)
                 .toArray();
}
\$\endgroup\$
4
\$\begingroup\$

You can simplify your flattening algorithm when you determine the maximum length of the sub arrays with a helper function first:

public static int maxLength(int array[][]) {
    int maxLength = 0;

    for (int i = 0; i < array.length; i++) {
        maxLength = array[i].length > maxLength ? array[i].length : maxLength;
    }

    return maxLength;
}

Now you can iterate over the jagged array maxLength times and by checking if the current iteration index exceeds the current sub array length you know whether you can safely read a value from a sub array or not:

public static void flattenList(int input[][]) {
    int maxLength = maxLength(input);
    List<Integer> result = new ArrayList<>();

    for (int i = 0; i < maxLength; i++) {
        for (int j = 0; j < input.length; j++) {
            if (i < input[j].length) {
                result.add(input[j][i]);
            }
        }
    }

    for(int i=0;i<result.size();i++){
        System.out.print(result.get(i)+" ");
    }
}

See this working example: https://ideone.com/EV8Wjg

...or this one: http://www.browxy.com/SubmittedCode/568038

(Boy, it's hard to find a decent online compiler for Java.)

\$\endgroup\$
1
  • \$\begingroup\$ tutorialspoint works really good. That approach is also a good one. \$\endgroup\$ Aug 25, 2016 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.