Flatten 2D Vector

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Reported atAirbnb

Flatten 2D Vector is a medium design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (row and column pointers), runs in O(1) amortized per call time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy into a flat list) up.

Problem

Build an iterator class Vector2D over a two-dimensional array of integers. Vector2D(int[][] vec) receives the data; the rows may have different lengths, and some rows may be empty.

next() returns the next integer in row-major order (all of row 0 from left to right, then row 1, and so on) and moves past it. hasNext() returns true if at least one integer has not been returned yet, and false otherwise. Calling hasNext() never consumes a value.

Examples

Example 1

Input
Vector2D([[7, 8], [], [9]]), next(), hasNext(), next(), next(), hasNext()
Output
7, true, 8, 9, false
Why
The empty middle row is skipped; after 9 every value has been handed out.

Example 2

Input
Vector2D([[], [4], [], [], [5, 6]]), hasNext(), next(), next(), hasNext(), next(), hasNext()
Output
true, 4, 5, true, 6, false
Why
Leading and repeated empty rows contribute nothing, so the values come out as 4, 5, 6.

Constraints

  • 0 <= vec.length <= 200
  • 0 <= vec[i].length <= 500
  • -500 <= vec[i][j] <= 500
  • At most 10^5 calls to next and hasNext in total.
  • next is only called when another element exists.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (copy into a flat list)O(N) constructor, O(1) per callO(N)
Optimal (row and column pointers)O(1) amortized per callO(1)

1Brute force (copy into a flat list)

TimeO(N) constructor, O(1) per callEvery one of the N values is copied once when the object is built.
SpaceO(N)The flat list duplicates all N values.

In the constructor, walk every row and append each value to one list. The iterator is then just an index into that list.

  1. Constructor: for every row, for every value, append it to flat.
  2. next(): return flat[pos] and advance pos.
  3. hasNext(): return pos < flat.size().
class Vector2D {
    private final List<Integer> flat = new ArrayList<>();
    private int pos = 0;

    public Vector2D(int[][] vec) {
        for (int[] row : vec)
            for (int x : row) flat.add(x);
    }

    public int next() {
        return flat.get(pos++);
    }

    public boolean hasNext() {
        return pos < flat.size();
    }
}

2Optimal (row and column pointers)

TimeO(1) amortized per callEach row is skipped at most once over the whole life of the iterator, so the skipping work is spread across all calls.
SpaceO(1)Only two integers are kept besides the reference to the input.

Keep a reference to the original 2D array plus two indices: the current row and the column inside it. A helper moves the row index forward while the current row has no values left, so after it runs the pointers either sit on the next value or past the last row.

  1. Store vec, row = 0, col = 0.
  2. advance(): while row < vec.length and col == vec[row].length, set row++ and col = 0.
  3. hasNext(): call advance(), then return row < vec.length.
  4. next(): call advance(), return vec[row][col] and increment col.
class Vector2D {
    private final int[][] vec;
    private int row = 0, col = 0;

    public Vector2D(int[][] vec) {
        this.vec = vec;
    }

    private void advance() {
        while (row < vec.length && col == vec[row].length) {
            row++;
            col = 0;
        }
    }

    public int next() {
        advance();
        return vec[row][col++];
    }

    public boolean hasNext() {
        advance();
        return row < vec.length;
    }
}

Edge cases to test

  • The whole input is empty, or contains only empty rows
  • Empty rows at the start, the middle and the end
  • Calling hasNext several times in a row must not skip anything
  • A single row holding every value

Hints

Hint 1

The simplest version copies every value into one flat list up front. What does that cost in memory?

Hint 2

Instead, remember a row index and a column index into the original data.

Hint 3

Before answering hasNext or next, move the row index forward past rows that are exhausted or empty.

FAQ

What is the best time complexity for Flatten 2D Vector?

Optimal (row and column pointers) runs in O(1) amortized per call time and O(1) extra space. Each row is skipped at most once over the whole life of the iterator, so the skipping work is spread across all calls.

Which pattern does Flatten 2D Vector use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Flatten 2D Vector?

Yes. Brute force (copy into a flat list) takes O(N) constructor, O(1) per call time and O(N) space. In the constructor, walk every row and append each value to one list.

Which edge cases should I test for Flatten 2D Vector?

The whole input is empty, or contains only empty rows; Empty rows at the start, the middle and the end; Calling hasNext several times in a row must not skip anything; A single row holding every value.