Flatten 2D Vector

LeetCode 251: Flatten 2D Vector Solution & Explanation

Problem Overview

TL;DR: The optimal solution maintains two pointers (row and column indices) to navigate the 2D structure virtually, advancing past empty rows on-the-fly without copying data.

The Flatten 2D Vector problem asks us to design an iterator class that traverses a 2D list (a list of lists) as if it were a 1D list. We must implement next() to return the next integer in row-major order and hasNext() to determine if any integers remain. The key challenge in LeetCode 251 is handling jagged arrays where rows may be empty or of varying lengths efficiently.

Brute Force Approach for Flatten 2D Vector

The most straightforward approach is to flatten the entire 2D data structure into a single 1D list during initialization.

1. Initialization: Iterate through every row and every column of the input 2D vector.
2. Storage: Copy every integer into a new list (e.g., std::vector or ArrayList).
3. Iteration: Maintain a simple integer index pointing to the current position in the flattened list. next() returns the element at the index and increments it; hasNext() checks if the index is within bounds.

Pseudo-code:

Class Vector2D:
    list flattened_data
    int index

    Constructor(vec):
        for row in vec:
            for val in row:
                flattened_data.add(val)
        index = 0

    next():
        return flattened_data[index++]

    hasNext():
        return index < flattened_data.size()

Complexity Analysis:

• Time Complexity: $O(N)$ for the constructor, where $N$ is the total number of elements. next() and hasNext() are $O(1)$.
• Space Complexity: $O(N)$ to store the flattened copy.

Why it fails: While this solution passes correctness tests, it fails the design principles of an iterator. Iterators are expected to be lightweight and lazy. If the input vector contains millions of elements but the user only calls next() once, the brute force approach wastes significant time and memory preprocessing data that is never used. Furthermore, duplicating the entire dataset is memory inefficient ($O(N)$ extra space).

Algorithm Strategy: Design Patterns

We implement the Vector2D class by maintaining references to the input data and two integer indices (row, col).

1. State Management: Store the input 2D vector (or a reference to it) and initialize row = 0, col = 0.
2. Smart hasNext(): This method is the engine of the class. It is responsible for ensuring the pointers point to a valid element.
   • While the row index is valid but the col index matches the size of the current row (meaning we finished this row or it was empty), increment row and reset col to 0.
   • If row is within bounds after this check, we have a valid element. Return true.
   • Otherwise, we have exhausted the structure. Return false.
3. Simplified next():
   • Call hasNext() first. This ensures pointers are valid and skips any preceding empty rows.
   • Retrieve the value at vector[row][col].
   • Increment col.
   • Return the value.

By delegating the "skipping" logic entirely to hasNext(), we simplify next() and ensure that multiple calls to hasNext() are idempotent (they don't change the state effectively, just validate it).

Execution Flow

Consider the input vec = [[1, 2], [3], []].

1. Initialization:

   • row = 0, col = 0.
   • Data: [[1, 2], [3], []].

2. Call next() (1st time):

   • Calls hasNext().
   • row (0) < vec.length (3). col (0) < vec[0].length (2). Valid. Returns true.
   • Return vec[0][0] which is 1.
   • Increment col to 1. State: row=0, col=1.

3. Call next() (2nd time):

   • Calls hasNext().
   • row (0) < 3. col (1) < vec[0].length (2). Valid. Returns true.
   • Return vec[0][1] which is 2.
   • Increment col to 2. State: row=0, col=2.

4. Call next() (3rd time):

   • Calls hasNext().
   • Current row vec[0] has length 2. col is 2. col == length, so we must advance.
   • Increment row to 1, reset col to 0.
   • Check vec[1]. Length is 1. col (0) < 1. Valid. Returns true.
   • Return vec[1][0] which is 3.
   • Increment col to 1. State: row=1, col=1.

5. Call hasNext():

   • Current row vec[1] has length 1. col is 1. Advance row.
   • Increment row to 2, reset col to 0.
   • Check vec[2] (which is []). Length is 0. col (0) is not less than 0. Advance row.
   • Increment row to 3, reset col to 0.
   • row (3) is not < vec.length (3).
   • Return false.

Proof of Correctness

The algorithm correctness relies on the invariant enforced by hasNext().

• Invariant: Upon returning true, hasNext() guarantees that vec[row][col] exists and is a valid integer.
• Termination: The row index strictly increases when a row is exhausted. Since the number of rows is finite, the loop inside hasNext() must terminate either by finding a valid element or reaching the end of the input.
• Order: The algorithm iterates col until the end of a row, then increments row and resets col. This strictly follows row-major order (left-to-right, top-to-bottom).

Pattern Reuse Notes

The Design pattern and the specific technique of maintaining internal pointers/state are applicable to several other popular interview questions:

• LeetCode 146: LRU Cache - Requires maintaining state (ordering of usage) combined with a Hash Map for fast access.
• LeetCode 155: Min Stack - Requires designing a class that maintains auxiliary state (minimums) alongside standard data.
• LeetCode 225: Implement Stack using Queues - Adapts one data structure's interface to behave like another.
• LeetCode 232: Implement Queue using Stacks - Similar to the above, dealing with state inversion.

Understanding how to encapsulate state and logic behind a standard interface is key to solving these problems efficiently.

Reference Implementation

C++ Solution for LeetCode 251

1class Vector2D {
2private:
3    vector<vector<int>> vec;
4    int row;
5    int col;
6
7    // Helper to advance to the next valid element
8    void advanceToNext() {
9        // While we are within rows, and the current row is exhausted
10        while (row < vec.size() && col == vec[row].size()) {
11            row++;
12            col = 0;
13        }
14    }
15
16public:
17    Vector2D(vector<vector<int>>& v) {
18        vec = v;
19        row = 0;
20        col = 0;
21    }
22    
23    int next() {
24        // Ensure we are pointing to a valid element
25        advanceToNext();
26        // Return current element and move pointer
27        return vec[row][col++];
28    }
29    
30    bool hasNext() {
31        advanceToNext();
32        return row < vec.size();
33    }
34};

Java Solution for LeetCode 251

1class Vector2D {
2    private int[][] vector;
3    private int row;
4    private int col;
5
6    public Vector2D(int[][] v) {
7        this.vector = v;
8        this.row = 0;
9        this.col = 0;
10    }
11    
12    public int next() {
13        // Ensure we are at a valid position before retrieving
14        if (hasNext()) {
15            return vector[row][col++];
16        }
17        throw new java.util.NoSuchElementException();
18    }
19    
20    public boolean hasNext() {
21        // While current row is valid but col is at the end of the row
22        while (row < vector.length && col == vector[row].length) {
23            row++;
24            col = 0;
25        }
26        // If row is still within bounds, we have a valid element
27        return row < vector.length;
28    }
29}

Python Solution for LeetCode 251

1class Vector2D:
2
3    def __init__(self, vec: List[List[int]]):
4        self.vec = vec
5        self.row = 0
6        self.col = 0
7
8    def next(self) -> int:
9        # hasNext() handles the logic of skipping empty rows
10        self.hasNext()
11        val = self.vec[self.row][self.col]
12        self.col += 1
13        return val
14
15    def hasNext(self) -> bool:
16        # While we are within the outer list bounds
17        while self.row < len(self.vec):
18            # If current col is within current inner list bounds, we found a valid element
19            if self.col < len(self.vec[self.row]):
20                return True
21            # Otherwise, move to the next row and reset col
22            self.row += 1
23            self.col = 0
24        
25        return False