Flatten 2D Vector LeetCode Solution

Problem Statement

Flatten 2D Vector LeetCode Solution – 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.

Example

Test Case 1:

Input:

[“Vector2D”, “next”, “next”, “next”, “hasNext”, “hasNext”, “next”, “hasNext”]

[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]

Output:

[null, 1, 2, 3, true, true, 4, false]

Explanation

1. Invariant: We will maintain the next correct index for x,y before the next call
2. hasNext is called before we call next
3. Remember we can have empty rows
4. At next, we extract x = vec2d[x,y]. If y+1 is less than the length of the current row, then set y to y+1. Otherwise, increment x to the next row. Make sure you adjust for empty rows at this point (and at initialization).
5. hasNext just needs to check the valid row number.

The idea is to keep two iterators, it1 is an Iterator<List> to iterate through the List of Lists. it2 is an Iterator which is the iterator of the List that it1 currently visiting. Whenever we call hasNext we try to find the next appropriate it2. If the current it2 hasNext then we keep using the same it2, otherwise we go down the List of Lists via it1 till we find a List that hasNext. If we reach the end (!it1.hasNext) that means we’ve exhausted all the possibilities and we return false. next() simply returns it2.next() since hasNext() guarantees that it2 hasNext.

1. Use two pointers, x -> index of subarray. y -> index of num in subarray
2. Inside next(), record the current number, then move pointers. (* After next() is called, x & y will always be pointing to its next location)
3. Move x to the next non-empty array, or outside of the vector if there is none

Code for Flatten 2D Vector

Java Program

import java.util.NoSuchElementException;

class Vector2D {
    
    private int[][] v;
    private int row;
    private int col;

    public Vector2D(int[][] v) {
        this.v = v;
        row = 0;
        col = 0;
    }
    
    public int next() {
        skipEmptyRows();
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        int next = v[row][col++];
        // Increment row if col reaches the end of the current row
        if (col == v[row].length) {
            row++;
            col = 0;
        }
        return next;
    }
    
    public boolean hasNext() {
        skipEmptyRows();
        return row < v.length - 1 || (row == v.length - 1 && col < v[row].length);
    }
    
    private void skipEmptyRows() {
        // Skip empty rows
        while (row < v.length && v[row].length == 0) {
            row++;
        }
    }
}

Python Program

class Vector2D(object):
    def skip_empty_rows_x(self):
        while self.x < len(self.vec2d) and len(self.vec2d[self.x]) == 0:
            self.x = self.x + 1
        return

    def __init__(self, vec2d):
        """
        Initialize your data structure here.
        :type vec2d: List[List[int]]
        """
        self.vec2d = vec2d
        self.x, self.y = 0, 0
        self.skip_empty_rows_x()

    def next(self):
        """
        :rtype: int
        """
        x = self.vec2d[self.x][self.y]
        self.y = self.y+1
        if self.y == len(self.vec2d[self.x]):
            self.x, self.y = self.x+1, 0
            self.skip_empty_rows_x()
        return x

    def hasNext(self):
        """
        :rtype: bool
        """
        if self.x >= len(self.vec2d):
            return False
        return True

Complexity Analysis for Flatten 2D Vector LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(1) as we are using constant space.