Question

Formatted question description: https://leetcode.ca/all/251.html

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 10⁵ 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.

Algorithm

Maintain two variables x and y, and initialize x and y to 0.

For the hasNext() function, check whether the current x is less than the total number of rows, and whether y is the same as the number of columns in the current row,

If the same, it means that you want to go to the next line, then x increments by 1, y is initialized to 0
If x is still less than the total number of rows at this time, indicating that the next value can be taken out, then in the next function, you can directly take out the row x, list the number as y, and increment y by 1

Note: special case for empty list

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

Code

import java.util.List;

public class Flatten_2D_Vector {

    public class Vector2D {
        private int x; // which list
        private int y; // which index of current list
        private List<List<Integer>> list;

        /* constructor */
        public Vector2D(List<List<Integer>> vec2d) {
            this.x = 0;
            this.y = 0;
            this.list = vec2d;
        }

        /* API: next */
        public int next() {
            int result = list.get(x).get(y);
            if (y + 1 >= list.get(x).size()) {
                y = 0;
                x++;
            } else {
                y++;
            }
            return result;
        }

        /* API: hasNext */
        public boolean hasNext() {
            if (list == null) {
                return false;
            }

            /*
               @note: special case for empty list

                 [
                 [1,2],
                 [3],
                 [4,5,6],
                 [],
                 [],
                 []
                 ]
             */
            while (x < list.size() && list.get(x).size() == 0) {
                x++;
                y = 0;
            }
            if (x >= list.size()) {
                return false;
            }
            if (y >= list.get(x).size()) {
                return false;
            }
            return true;
        }
    }
}

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

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();
 */

// OJ: https://leetcode.com/problems/flatten-2d-vector/
// Time:
//      Vector2D: O(N)
//      next: O(1) amortized
//      hasNext: O(1)
// Space: O(1)
class Vector2D {
    vector<vector<int>> v;
    int i = 0, j = 0;
    void move() {
        while (i < v.size() && j == v[i].size()) {
            ++i;
            j = 0;
        }
    }
public:
    Vector2D(vector<vector<int>>& v) : v(v) {
        move();
    }
    int next() {
        int ans = v[i][j++];
        move();
        return ans;
    }
    bool hasNext() {
        return i < v.size();
    }
};

"""
@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()
 */

251 - Flatten 2D Vector

Question

Algorithm

Note: special case for empty list

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Note: special case for empty list

Code

All Problems

All Solutions