Welcome to Subscribe On Youtube

251. Flatten 2D Vector

Description

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 1:

Input
["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"]
[[[[1, 2], [3], [4]]], [], [], [], [], [], [], []]
Output
[null, 1, 2, 3, true, true, 4, false]

Explanation
Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]);
vector2D.next();    // return 1
vector2D.next();    // return 2
vector2D.next();    // return 3
vector2D.hasNext(); // return True
vector2D.hasNext(); // return True
vector2D.next();    // return 4
vector2D.hasNext(); // return False

 

Constraints:

  • 0 <= vec.length <= 200
  • 0 <= vec[i].length <= 500
  • -500 <= vec[i][j] <= 500
  • At most 105 calls will be made to next and hasNext.

 

Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

Solutions

Constructor: __init__

  • Initializes the instance variables self.i and self.j, which track the current list (row) and the current index within that list (column), respectively.
  • It also stores the given list of lists v in self.vector.

Method: next

  • Returns the next integer in the 2D vector.
  • Before returning the next element, it calls self.hasNext() to ensure the current indices self.i and self.j point to a valid element. If they don’t, self.hasNext() adjusts them to the next valid element.
  • Retrieves the value at the current indices, increments self.j to move to the next element in the current list, and returns the value.

Method: hasNext

  • Checks if there are any more integers to return in the 2D vector.
  • It does this by iterating through the lists (rows) in self.vector starting from the current row index self.i. For each list, it checks if the current column index self.j is within the bounds of the list.
  • If self.j is out of bounds for the current list, it moves to the next list by incrementing self.i and resetting self.j to 0 to start from the beginning of the next list.
  • If a list is found where self.j is within bounds, it means there are more elements to iterate through, so it returns True.
  • If the end of self.vector is reached without finding any more elements, it returns False.

Example Usage

Let’s say we have a 2D vector [[1, 2], [3], [], [4, 5, 6]] and we create an instance of Vector2D with this vector:

vector2D = Vector2D([[1, 2], [3], [], [4, 5, 6]])
  • Calling next() repeatedly would return elements in order: 1, 2, 3, 4, 5, 6.
  • Calling hasNext() at any point would check if there are more elements after the current one.
  • class Vector2D {
    private int i;
    private int j;
    private int[][] vec;

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

    public int next() {
        forward();
        return vec[i][j++];
    }

    public boolean hasNext() {
        forward();
        return i < vec.length;
    }

    private void forward() {
        while (i < vec.length && j >= vec[i].length) {
            ++i;
            j = 0;
        }
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D obj = new Vector2D(vec);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

  • class Vector2D {
public:
    Vector2D(vector<vector<int>>& vec) {
        this->vec = move(vec);
    }

    int next() {
        forward();
        return vec[i][j++];
    }

    bool hasNext() {
        forward();
        return i < vec.size();
    }

private:
    int i = 0;
    int j = 0;
    vector<vector<int>> vec;

    void forward() {
        while (i < vec.size() && j >= vec[i].size()) {
            ++i;
            j = 0;
        }
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(vec);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

  • """
@note: special case for empty list

[
    [1,2],
    [3],
    [4,5,6],
    [],
    [],
    []
]
"""

class Vector2D:
    def __init__(self, vec: List[List[int]]):
        self.flatten = []
        for item in vec:
            for e in item:
                self.flatten.append(e)
        self.cur = -1

    def next(self) -> int:
        self.cur += 1
        return self.flatten[self.cur]

    def hasNext(self) -> bool:
        return self.cur < len(self.flatten) - 1

############

class Vector2D:
    def __init__(self, v: List[List[int]]):
        self.i = 0 # which list
        self.j = 0 # which index of current list
        self.vector = v

    def next(self) -> int:
        self.hasNext()
        value = self.vector[self.i][self.j]
        self.j += 1 # in hasNext() guaranteed not end of row
        return value

    def hasNext(self) -> bool:
        while self.i < len(self.vector):
            if self.j < len(self.vector[self.i]):
                return True
            self.i += 1
            self.j = 0
        return False


# Your Vector2D object will be instantiated and called as such:
# obj = Vector2D(vec)
# param_1 = obj.next()
# param_2 = obj.hasNext()

############

class Vector2D(object):

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

  def next(self):
    """
    :rtype: int
    """
    self.y += 1
    return self.m[self.x][self.y - 1]

  def hasNext(self):
    """
    :rtype: bool
    """
    m = self.m
    while self.x < len(m) and self.y >= len(m[self.x]):
      self.x += 1
      self.y = 0
    return self.x < len(m)

# Your Vector2D object will be instantiated and called as such:
# i, v = Vector2D(vec2d), []
# while i.hasNext(): v.append(i.next())


  • type Vector2D struct {
	i, j int
	vec  [][]int
}

func Constructor(vec [][]int) Vector2D {
	return Vector2D{vec: vec}
}

func (this *Vector2D) Next() int {
	this.forward()
	ans := this.vec[this.i][this.j]
	this.j++
	return ans
}

func (this *Vector2D) HasNext() bool {
	this.forward()
	return this.i < len(this.vec)
}

func (this *Vector2D) forward() {
	for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) {
		this.i++
		this.j = 0
	}
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * obj := Constructor(vec);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */

  • class Vector2D {
    i: number;
    j: number;
    vec: number[][];

    constructor(vec: number[][]) {
        this.i = 0;
        this.j = 0;
        this.vec = vec;
    }

    next(): number {
        this.forward();
        return this.vec[this.i][this.j++];
    }

    hasNext(): boolean {
        this.forward();
        return this.i < this.vec.length;
    }

    forward(): void {
        while (this.i < this.vec.length && this.j >= this.vec[this.i].length) {
            ++this.i;
            this.j = 0;
        }
    }
}

/**
 * Your Vector2D object will be instantiated and called as such:
 * var obj = new Vector2D(vec)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */

All Problems

All Solutions