# Flatten 2D Vector Problem in Java

The Flatten 2D Vector Problem is a complex computer science puzzle involving manipulating two-dimensional data structures for efficient traversal and retrieval. It requires innovative approaches to reconcile the irregular inner arrays of the matrix-like data structure and balances space and time complexity. The problem is applied in image processing, computer graphics, natural language processing, and computational biology.

Example 1:

Input: [[1,2], [3], [4,5,6]]

Output: 1 2 3 4 5 6

Explanation: The iterator moves from the first row to the next, printing elements in sequential order and then prints elements in the second row, printing them sequentially, resulting in a single-line output.

## Using Iterator Approach

Algorithm

Step 1: Initializes 2D vector and indices 'row' and 'col' for current position tracking.

Step 2: Constructor accepts the input 2D vector and initializes vector and indices.

Step 3: The HasNext() method increments the row index and resets the column index to 0 if the current row index is less than the total number of rows.

Step 4: The Next() method checks if there are more elements, throws an exception if not, retrieves the current element from the 2D vector, increments the column index, and returns the current element.

Step 5: Provides a clean, straightforward way to access elements sequentially.

Here is an implementation of a problem to flatten a 2D Vector using an iterator approach :

Filename: IteratorApproach.java

`import java.util.Iterator;public class IteratorApproach {    public static void main(String[] args) {        int[][] input = {{1, 2}, {}, {3}, {4, 5, 6}};        Vector2D vector2D = new Vector2D(input);        while (vector2D.hasNext()) {            System.out.print(vector2D.next() + " ");        }    }    // Inner class representing the iterator for the 2D vector    static class Vector2D implements Iterator<Integer> {        private int[][] vector;         private int row, col;          // Constructor initializes the iterator with the 2D vector        public Vector2D(int[][] vec) {            this.vector = vec;            row = 0;              col = 0;         }        // Checks if there are more elements to iterate over in the 2D vector        @Override        public boolean hasNext() {            // Move to a valid position if necessary            while (row < vector.length && col == vector[row].length) {                // Skip empty rows                row++;                col = 0;            }            // Determine if there are more elements based on the current position            return row < vector.length;        }        // Returns the next element in the 2D vector and moves the pointer        @Override        public Integer next() {            // Check if there are more elements to iterate over            if (!hasNext()) throw new IllegalStateException("No more elements");            // Get the current element and move the column index forward            int result = vector[row][col++];            return result;        }    }}`

Output:

`1 2 3 4 5 6`

Complexity analysis: The time complexity of the above approach is O(n), as iterating over each element of the input 2D vector once without revisiting any. The space complexity is O(1), as the iterator implementation uses constant extra space for indices 'row' and 'col'.

## Using a Naive Flattening Approach

Algorithm

Step 1: Initialize an empty list to store the flattened elements.

Step 2: Iterate over each row in the 2D vector.

Step 3: For each row, iterate over each element.

Step 4: Add each element to the list.

Step 5: After iterating through all elements, print each element from the list separated by a space.

Here is an implementation of a problem to flatten a 2D Vector using a naive flattening approach :

FileName: NaiveFlattening.java

`import java.util.ArrayList;import java.util.List;public class NaiveFlattening {    public static void main(String[] args) {        int[][] input = {{1, 2}, {}, {3}, {4, 5, 6}};        // Initialize an ArrayList to store flattened elements        List<Integer> flattenedList = new ArrayList<>();        // Iterate over each row in the 2D vector        for (int[] row : input) {            // Iterate over each element in the current row            for (int num : row) {                // Add the current element to the flattened list                flattenedList.add(num);            }        }        for (int num : flattenedList) {            System.out.print(num + " ");        }    }}`

Output:

`1 2 3 4 5 6`

Complexity analysis: The above approach has a time complexity of O(n) due to iterating over each element of the input 2D vector using nested loops and a space complexity of O(n) due to the additional space needed to store flattened elements in an ArrayList (`flattenedList`), which grows linearly with the number of elements in the input 2D vector.