Flatten 2D array

PROBLEM STATEMENT

You have to implement an iterator for ‘FLATTEN_2D’ to flatten a two-dimensional array ‘ARR_2D’ into a one-dimensional array ‘ARR_1D’. The iterator should support the following two operations:
‘NEXT’: The first call to ‘NEXT’ should return the first element of ‘ARR_2D’. Each subsequent call should return the next element in the row-wise traversal of ‘ARR_2D’.
‘HAS_NEXT’: It should return ‘true’ if the iteration has more elements to traverse; otherwise, if ‘NEXT’ has traversed the entire ‘ARR_2D’, return ‘false’.

Try to code this using only iterators in C++ or iterators in Java.

The ‘FLATTEN_2D’ object will be instantiated and called as follow:
FLATTEN_2D it = new FLATTEN_2D(ARR_2d);
while (it.hasNext()) {
arr1d.append(it.next());
}

Example:

ARR_2D = [ 
          [0, 1],
          [2, 3, 4],
          [],
          [5] 
        ]
The computed ‘ARR_1D’ should be as follows:
ARR_1D = [0, 1, 2, 3, 4, 5]
So, the printed output will be: 0 1 2 3 4 5

Input format:

The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains an integer ‘N’ denoting the number of rows in ‘ARR_2D’. Then, ‘N’ lines follow.

Each line contains an integer ‘M’ denoting the number of columns in that row and ‘M’ space-separated integers denoting the row values.

For more clarity, please refer to the sample inputs.

Output format:

For every test case, the values in ‘ARR_1D’ will be printed in a separate line.

Note:

1. You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 100
0 <= M <= 100
-10^6 <= Value in each element of ‘ARR_2D’ <= 10^6

Time limit: 1 sec

Approach 1

A simple and less efficient approach will be to convert the given ‘ARR_2D’ into a 1-D array during initialization. We need to store a single pointer that initially points to the start of the 1-D array. Each call of ‘NEXT’ will increment this pointer, and ‘HAS_NEXT’ will return false when the pointer points outside the array.

The ‘FLATTEN_2D’ class stores two variables:

1-D array: 'ARR"
Integer: 'POS'

The constructor ‘FLATTEN_2D(ARR_2D)’ is as follows:

Run a loop where ‘i’ ranges from 0 to ‘sizeOf(ARR_2D) - 1’. To traverse ‘ARR_2D’ row-wise.
- Run a loop where ‘j’ ranges from 0 to ‘sizeOf(ARR_2D[i]) - 1’. To traverse the ‘i-th’ row.
  - ‘arr.append(ARR_2D[i][j])’
Initialize 'POS' to 0.

The ‘NEXT’ function:

Initialize integer 'RES' to ‘arr[pos]’.
‘POS = POS + 1’. To point 'POS' to the NEXT element in 'ARR".
Return 'RES'.

The ‘HAS_NEXT’ function:

If 'POS' is less than ‘sizeOf(ARR)’. The iteration still has some element left to traverse.
- Return ‘true’.
Else, return ‘false’.

Try Problem

Approach 2

Instead of using extra space to store a 1-D array, we can use two variables to point to a position in ‘ARR_2D’. Variable 'ROW' will point to the row, and 'COL' will point to the column in that row. Initialize 'ROW' and 'COL' to point to the first element in ‘ARR_2D’. After each ‘NEXT’ and ‘HAS_NEXT’ call, we update the pointer values. In ‘NEXT’, move to the NEXT column in the current row, and if all columns are traversed, then move to the first column of the NEXT row. In ‘HAS_NEXT’, check for empty rows and move to the NEXT non-empty row.

The 'FLATTEN_2D' class stores three variables:

Reference to a 2-D array: ‘ARR_2D’
Integer: 'ROW'
Integer: 'COL'

The constructor ‘FLATTEN_2D(ARR_2D)’ is as follows:

Store the reference of ‘ARR_2D’ in ‘this.ARR_2D’.
Initialize 'ROW' to 0 and 'COL' to 0.

The ‘NEXT’ function:

Initialize integer 'RES' to ‘ARR_2D[ROW][COL]’.
‘COL = COL + 1’
If 'COL' is equal to ‘sizeOf(ARR_2D[ROW])’,i.e., all the elements of 'ROW' are traversed.
- ‘ROW = ROW + 1’
- ‘COL = 0’. Now, 'COL' points to the first element of the new 'ROW'.
Return 'RES'.

The ‘HAS_NEXT’ function:

Run a loop until ('ROW' is less than ‘sizeOf(ARR_2D)’) and (‘sizeOf(ARR_2D[ROW])’ is equal to 0). Keep moving to the NEXT row until we find a non-empty row.
- ‘ROW = ROW + 1’
If 'ROW' is greater than equal to ‘sizeOf(ARR_2D)’. We have traversed all rows in ‘ARR_2D’.
- Return ‘false’.
Else, return ‘true’.

Try Problem

Approach 3

Use an inbuilt iterator 'IT' of type 1-D array’. Initialize 'IT' to point to the first row in ‘ARR_2D’. After each 'NEXT' and ‘HAS_NEXT’ call, we update this iterator. In 'NEXT', we increment 'IT' to point to the current row’s next element. If a row is traversed or is empty, then 'IT' points to ‘end()’ (in C++) or ‘it.HAS_NEXT()’ returns false (in Java). In ‘HAS_NEXT’, check if the current row is traversed or is empty and point 'IT' to the next non-empty row.

The ‘Flatten2D’ class stores three variables:

Reference to a 2-D array: ‘ARR_2D’
Iterator of type 1-D array: 'IT'
Integer: 'ROW'

The constructor ‘Flatten2D(ARR_2D)’ is as follows:

Store the reference of ‘ARR_2D’ in ‘this.ARR_2D’.
Initialize iterator 'IT' to ‘this.ARR_2D[ROW]’ and integer 'ROW' to 0.

The 'NEXT' function:

Initialize integer 'RES' to value pointed by 'IT'.
Increment 'IT' to point to the next element.
Return 'RES'.

The ‘HAS_NEXT’ function:

Run a loop until ('IT' is equal to ‘ARR_2D[row].end()’) and ('ROW' is less than ‘sizeOf(ARR_2D)). Keep moving to the next row until we find a valid row.
- ‘ROW = ROW + 1’
- Point 'IT' to ‘ARR_2D[row]’
If 'ROW' is greater than equal to ‘sizeOf(ARR_2D)’. We have traversed all rows in ‘ARR_2D’.
- Return ‘false’.
Else, return ‘true’.

Try Problem