Flatten 2D array

Easy
0/40
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in companies
MeeshoDunzoApple

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
    Detailed explanation ( Input/output format, Notes, Images )
    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

    Sample input 1:

    2
3
3 1 2 3
1 -5
0
2
2 5 6
3 1 3 2

    Sample output 1:

    1 2 3 -5
5 6 1 3 2

    Explanation of sample input 1:

    Test Case 1:
Input: arr2d = [ 
                  [1, 2, 3],
                  [-5],
                  [] 
                ]
The computed ‘arr1d’ should be as follows:
arr1d = [1, 2, 3, -5]
So, the printed output will be: 1 2 3 -5 

Test Case 2:
Input: arr2d = [ 
                  [5, 6],
                  [1, 3, 2]
                ]
The computed ‘arr1d’ should be as follows:
arr1d = [5, 6, 1, 3, 2]
So, the printed output will be: 5 6 1 3 2

    Sample input 2:

    2
4
0
3 1 2 2
1 5
2 6 7
2
3 1 2 3
3 3 2 1

    Sample output 2:

    1 2 2 5 6 7
1 2 3 3 2 1
    Hint

    Convert ‘arr2d’ into a 1-D array beforehand.

    Approaches (3)
    Convert to a 1-D array

    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’.
    Time Complexity

    O(N), where ‘N’ is the number of elements in ‘ARR_2D’.

     

    We traverse both ‘ARR_2D’ and ‘ARR’ once, each having ‘N’ elements.

    Space Complexity

    O(N), where ‘N’ is the number of elements in ‘ARR_2D’.

     

    We convert ‘ARR_2D’ and store it in ‘ARR’ of size ‘N’.

    Video Solution
    Unlock at level 3
    (75% EXP penalty)
    Code Solution
    (100% EXP penalty)
    Flatten 2D array
    Full screen
    Console