Flatten 2D Vector - Practice Coding Problems

Flatten 2D Vector - Problem

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.

Implement the Vector2D class:

Vector2D(int[][] vec) initializes the object with the 2D vector vec.
next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
hasNext() returns true if there are still some elements in the vector, and false otherwise.

Input & Output

Example 1 — Basic 2D Vector

$ Input: vec = [[1,2],[3],[4]], operations = ["Vector2D","next","next","next","hasNext","hasNext","next","hasNext"]

› Output: [null,1,2,3,true,true,4,false]

💡 Note: Vector2D iterator flattens [[1,2],[3],[4]]. next() returns 1,2,3,4 in sequence. hasNext() checks if more elements exist.

Example 2 — Empty Rows

$ Input: vec = [[1,2],[],[3]], operations = ["Vector2D","next","next","hasNext","next","hasNext"]

› Output: [null,1,2,true,3,false]

💡 Note: Empty middle row is skipped automatically. Elements 1,2,3 are returned in order despite empty row.

Example 3 — Single Row

$ Input: vec = [[1,2,3,4,5]], operations = ["Vector2D","hasNext","next","hasNext"]

› Output: [null,true,1,true]

💡 Note: Single row with multiple elements. hasNext() returns true, next() returns 1, still has more elements.

Constraints

1 ≤ vec.length ≤ 200
0 ≤ vec[i].length ≤ 500
-500 ≤ vec[i][j] ≤ 500
At most 10⁵ calls to next and hasNext

Visualization

Tap to expand

Understanding the Visualization

Input

2D vector [[1,2],[3],[4]] with mixed row lengths

Iterator

Provides next() and hasNext() methods for sequential access

Output

Elements returned in row-major order: 1,2,3,4

Key Takeaway

🎯 Key Insight: Use two pointers (row, col) to navigate 2D structure while providing 1D iterator interface

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

Design an iterator for a 2D vector using two pointers to track row and column positions. The key insight is to automatically skip empty rows and maintain O(1) space complexity. Best approach uses row/column pointers with O(1) time per operation and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Flatten All at Once	O(n)	O(n)	Pre-flatten the entire 2D vector into a 1D list during initialization
Two Pointers (Row & Column)	O(1)	O(1)	Use two pointers to track current row and column position in the 2D vector

Flatten All at Once — Algorithm Steps

Step 1: Flatten all elements into a single list
Step 2: Use index pointer for iteration

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Flatten [[1,2],[3],[4]] into [1,2,3,4]

Iterate

Use index pointer to track current position

Operations

next() returns current element and increments index

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* flattened;
    int size;
    int index;
} Vector2D;

Vector2D* vector2DCreate(int** vec, int vecSize, int* vecColSize) {
    Vector2D* obj = (Vector2D*)malloc(sizeof(Vector2D));
    obj->size = 0;
    for (int i = 0; i < vecSize; i++) {
        obj->size += vecColSize[i];
    }
    
    obj->flattened = (int*)malloc(obj->size * sizeof(int));
    obj->index = 0;
    
    int pos = 0;
    for (int i = 0; i < vecSize; i++) {
        for (int j = 0; j < vecColSize[i]; j++) {
            obj->flattened[pos++] = vec[i][j];
        }
    }
    
    return obj;
}

int vector2DNext(Vector2D* obj) {
    return obj->flattened[obj->index++];
}

bool vector2DHasNext(Vector2D* obj) {
    return obj->index < obj->size;
}

void vector2DFree(Vector2D* obj) {
    free(obj->flattened);
    free(obj);
}

int main() {
    // Simplified example
    int row1[] = {1, 2};
    int row2[] = {3};
    int row3[] = {4};
    int* vec[] = {row1, row2, row3};
    int vecColSize[] = {2, 1, 1};
    
    Vector2D* obj = vector2DCreate(vec, 3, vecColSize);
    printf("[null,%d,%d,%d,%s,%s,%d,%s]\n", 
           vector2DNext(obj), vector2DNext(obj), vector2DNext(obj),
           vector2DHasNext(obj) ? "true" : "false",
           vector2DHasNext(obj) ? "true" : "false",
           vector2DNext(obj),
           vector2DHasNext(obj) ? "true" : "false");
    
    vector2DFree(obj);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

O(n) for initialization to flatten all elements, O(1) for each next/hasNext call

✓ Linear Growth

Space Complexity

O(n)

Extra list stores all n elements from the 2D vector

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Flatten All at Once — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler