C++ solution based on vector::iterator

  • 0

    This solution make uses of C++ style iterators. First, we keep two iterators: "outer" and "inner" that traverse on two dimensions of the array, respectively. In hasNext(), we move 'outer' to the next available element, skipping empty subarrays if there are any; In next(), we simply return the available element, and move inner forward to prepare for the search of the element after the current one.

    A special case is when vec2d is empty. In that case, the inner iterator cannot point to any subarray becaue there isn't any. To deal with that case, we create a empty dummy array which inner iterators could point to so that they would always be properly initialized.

    class Vector2D {
        vector<vector<int>>::iterator outer, outer_end;  // Outer iterators
        vector<int>::iterator inner, inner_end;         // Inner iterators
        vector<int> dummy;
        Vector2D(vector<vector<int>>& vec2d) {
             outer = vec2d.begin();
            outer_end = vec2d.end();
            if (outer!=outer_end) {
                inner = outer->begin();
                inner_end = outer->end();
            else {  // If vec2d is empty, then the inner iterators have nothing to point to
                inner = dummy.begin();  // therefore we create an empty array 'dummy'
                inner_end = dummy.end();  // which inner iterators could point to.
        int next() {
            hasNext();              // Find the next available element
            int val = *inner;       
            inner++;                // Increase the inner iterator so that next time 'hasNext()'
            return val;             // is called, we'd reach the element that comes after val.
        bool hasNext() {
            if (outer == outer_end) return false;   // If we have reached the end of array, return false
            while (inner == inner_end) {        // If the inner iterator reaches the end of a subarray
                outer ++;                       // then check the next subarray
                if (outer == outer_end) return false;   // If there is no subarray that follows, then there is no 'next' element
                inner = outer->begin();         //  otherwise we reinitialize the inner iterators
                inner_end = outer->end();
            return true;

  • 0

    Great code using iterators :-)

Log in to reply

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