20ms C++ Solution with Explanations


  • 2

    The idea is very simple. We keep two variables row and col for the range of rows and cols. Specifically, row is the number of rows of vec2d and col is the number of columns of the current 1d vector in vec2d. We also keep two variables r and c to point to the current element.

    In the constructor, we initialize row and col as above and initialize both r and c to be 0 (pointing to the first element).

    In hasNext(), we just need to check whether r and c are still in the range limited by row and col.

    In next(), we first record the current element, which is returned later. Then we update the running indexes and possibly the range if the current element is the last element of the current 1d vector.

    A final and important note, since in next(), we record the current element, we need to guarantee that there is an element. So we implement a helper function skipEmptyVector() to skip the empty vectors. It is also important to handle the case that vec2d is empty (in this case, we set col = -1).

    The time complexity of hasNext() is obviously O(1) and the time complexity of next is also O(1) in an amortized sense.

    The code is as follows.

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            data = vec2d;
            r = c = 0;
            row = vec2d.size();
            col = (row == 0 ? -1 : data[r].size());
            skipEmptyVector();
        }
    
        int next() {
            int elem = data[r][c];
            if (c == col - 1) {
                r++;
                c = 0;
                col = data[r].size();
            }
            else c++;
            skipEmptyVector();
            return elem;
        }
    
        bool hasNext() {
            return col != -1 && (r < row && c < col);
        }
    private:
        vector<vector<int>> data;
        int row, col, r, c;
        void skipEmptyVector(void) {
            while (!col) {
                r++;
                col = data[r].size();
            }
        }
    }; 
    
    /**
     * Your Vector2D object will be instantiated and called as such:
     * Vector2D i(vec2d);
     * while (i.hasNext()) cout << i.next();
     */
    

    Updates: Since we need to copy the vec2d, we can just copy it into a 1d vector<int>.

    class Vector2D { 
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            int row = vec2d.size();
            for (int r = 0; r < row; r++) {
                int col = vec2d[r].size();
                for (int c = 0; c < col; c++)
                    data.push_back(vec2d[r][c]);
            }
            idx = 0;
        }
    
        int next() {
            return data[idx++];
        }
    
        bool hasNext() {
            return idx < data.size();
        }
    private:
        vector<int> data;
        int idx;
    };  
    
    /**
     * Your Vector2D object will be instantiated and called as such:
     * Vector2D i(vec2d);
     * while (i.hasNext()) cout << i.next(); 
     */
    

    Of course, the problem can also be solved in O(1) memory (see here for a better solution).


  • 7

    Your data is a copy of vec2d. If you copy all the data anyway, you might as well just copy it into a single simple vector<int>. Makes things easier.

    class Vector2D {
        vector<int> data;
        int i = 0;
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            for (auto& v : vec2d)
                data.insert(end(data), begin(v), end(v));
        }
    
        int next() {
            return data[i++];
        }
    
        bool hasNext() {
            return i < data.size();
        }
    };
    

    Java

    public class Vector2D {
    
        private LinkedList<Integer> data = new LinkedList();
    
        public Vector2D(List<List<Integer>> vec2d) {
            for (List v : vec2d)
                data.addAll(v);
        }
    
        public int next() {
            return data.pop();
        }
    
        public boolean hasNext() {
            return !data.isEmpty();
        }
    }
    

    And Python :-)

    class Vector2D:
    
        def __init__(self, vec2d):
            self.data = sum(vec2d, [])[::-1]
    
        def next(self):
            return self.data.pop()
    
        def hasNext(self):
            return bool(self.data)
    

    Though self.data = [i for v in vec2d for i in v][::-1] would be faster for long vec2d.


  • 0

    Hi, Stefan. Great thanks! In fact, I have come up with this idea at the very beginning. Then I write down the following code, which however, meets Memory Limit Exceeded ...

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            int row = vec2d.size();
            for (int r = 0; r < row; r++) {
                int col = vec2d[r].size();
                for (int c = 0; c < col; c++)
                    data.push_back(vec2d[r][c]);
            }
            idx = 0;
        }
    
        int next() {
            return data[idx];
        }
    
        bool hasNext() {
            return idx < data.size();
        }
    private:
        vector<int> data;
        int idx;
    };
    

    Now I realize that the code has a bug in next, which should be return data[idx++];.

    Well, your use of insert is much more concise and the Python code is just cool :-)


  • 0

    Haha, yeah, I can see how that MLE can be misleading :-)

    If you learn to love range-based loops, it can be nice and concise without insert:

        for (auto& v : vec2d)
            for (int i : v)
                data.push_back(i);
    

  • 0

    Range-based loops are just cool :-)


  • 0

    Little fix: auto& instead of auto for vectors to prevent needless copies.

    for (auto& v : vec2d)

  • 0

    "since elements in vector are stored in a contiguous range of memory, the problem can be solved in O(1) memory"

    I don't understand. I could similarly solve it in O(1) memory with a linked list. How does the contiguous range of memory matter?


  • 0

    Hi, Stefan. Thank you for pointing out the mistake. I have updated my post.


  • 0

    Hi, Stefan. Thank you. I got it :-)


  • 0
    V

    @jianchao.li.fighter said in 20ms C++ Solution with Explanations:

    return col != -1 && (r < row && c < col);

    is col != -1 needed in the hasNext() return statement?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.