Flatten 2D array

Posted: 13 Mar, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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