Last Updated: 13 Mar, 2021
Flatten 2D array
Easy
Asked in companies
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:
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
Approaches
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])’
- Run a loop where ‘j’ ranges from 0 to ‘sizeOf(ARR_2D[i]) - 1’. To traverse the ‘i-th’ row.
- 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’.
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’.
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’.
Similar problems