Issue with ArrayList array generation

Question

You are given an array A of N integers. Return a 2D array consisting of all the subarrays of the array.

I had tried to get subarrays in temp as per loop and add that subarray directly to ans(2d arraylist)

public ArrayList<ArrayList<Integer>> solve(ArrayList<Integer> A) {
    int n=A.size();
    ArrayList<ArrayList<Integer>> ans= new ArrayList<>();
    for(int i=0;i<n;i++)
    {
        ArrayList<Integer> temp=new ArrayList<>();
        for(int j=i;j<n;j++)
        {
            temp.add(A.get(j));                           
            ans.add(temp);                       
        }
    }
    return ans;
}

Input: [1,2,3,4,5]

Output: [1 2 3 4 5 ] [1 2 3 4 5 ] [1 2 3 4 5 ] [1 2 3 4 5 ] [1 2 3 4 5 ] [2 3 4 5 ] [2 3 4 5 ] [2 3 4 5 ] [2 3 4 5 ] [3 4 5 ] [3 4 5 ] [3 4 5 ] [4 5 ] [4 5 ] [5 ]

Expected output: [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[2],[2,3],[2,3,4],[2,3,4,5],[3],[3,4],[3,4,5],[4],[4,5],[5]]

Answer 1

The issue is that you're adding the same ArrayList object (temp) multiple times to ans. In Java, the ArrayList object is mutable. So, when you modify temp, all the references to it in ans get updated as well.

To fix, create a new list from temp before adding it to ans, e.g., use new ArrayList<>(temp):

import java.util.ArrayList;
import java.util.Arrays;

class Main {
  public static void main(String[] args) {
    ArrayList<Integer> input = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    System.out.println(solve(input));
  }

  public static ArrayList<ArrayList<Integer>> solve(ArrayList<Integer> A) {
    int n = A.size();
    ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      ArrayList<Integer> temp = new ArrayList<>();
      for (int j = i; j < n; j++) {
        temp.add(A.get(j));
        ans.add(new ArrayList<>(temp));
      }
    }
    return ans;
  }
}

Output:

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2], [2, 3], [2, 3, 4], [2, 3, 4, 5], [3], [3, 4], [3, 4, 5], [4], [4, 5], [5]]

Answer 2

Utilize the List#subList method, and remove the need for temp.

List<List<Integer>> solve(List<Integer> A) {
    List<List<Integer>> list = new ArrayList<>();
    for (int i = 0, j, n = A.size(); i < n; i++)
        for (j = i + 1; j <= n; j++)
            list.add(new ArrayList<>(A.subList(i, j)));
    return list;
}

Output

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[2]
[2, 3]
[2, 3, 4]
[2, 3, 4, 5]
[3]
[3, 4]
[3, 4, 5]
[4]
[4, 5]
[5]