I had a recent interview question where given a 2d array in which each row is sorted. Implement an Iterator to iterate over the array and print the array in ascending order. Implement the iterator without using libraries. Example:

SortedIterator sc = new SortedIterator(new int[][]{{2, 5, 8, 10, 11},
{0,1,4,6},{17, 19}});

This should print out:

0
1
2
4
5
6
8
10
11
17
19

MY APPROACH: I used a dynamic list to add each element in the array and sort the list. Use an index everytime a next is called to get the element from the dynamic list. Also had a function call hasNext to return true or false if the index is greater or less than the dynamic list.

Source code below:

public class SortedIterator {
   private List<Integer> list;
   private index;
   public SortedIterator(int[][] array) {
     this.list = new ArrayList<>();
     this.index = 0;
     this.setUpArrayToList(array);
   }

   private void setUpArrayToList(int[][] array) {

         for(int i=0;array.length;i++) {
           for(int j=0;j<array[i].length;j++){
               list.add(array[i][j]);
            }
         }
       Collections.sort(list);
   }
   public int next() {
         int value = list.get(index);
         index++;
         return value;
    }
   public boolean hasNext() {
     return this.index < list.size();
   }
 }

TIME AND SPACE COMPLEXITY: The time complexity will be O(N*M) for inserting into the list and nlogn to sort the list. So the overall time complexity will be O(NM). Space Complexity will be O(N). Is there a better approach?