Python O(1) space+time, very simple solution


  • 0
    C

    No copying or misuse of the hasNext() function as iterator.

    class Vector2D(object):
    
        def __init__(self, vec2d):
            self.vec2d = vec2d
            self.x, self.y = -1, 0
            self._move_to_next_valid_position()
    
        def _move_to_next_valid_position(self):
            # Move to the next possible element
            # If there are no elements left, this moves self.y to the
            # end of vec2d, so hasNext() will return False and next() will fail
            if self.hasNext:
                self.x += 1
                while self.y < len(self.vec2d) and self.x >= len(self.vec2d[self.y]):
                    self.x = 0
                    self.y += 1
    
        def next(self):
            if self.hasNext:
                result = self.vec2d[self.y][self.x]
                self._move_to_next_valid_position()
                return result
            return None
    
        def hasNext(self):
            return self.y < len(self.vec2d)
    

    Any ideas on how to refactor this to make it easier to read? I feel like this looks complicated.


  • 0

    Once you realize that if self.hasNext: isn't doing what you want, there's an obvious improvement :-)


  • 0
    B

    Same idea: not using extra space, nor built in iterator.
    Slightly different handling on hasNext() and next().

    def _move_down(self):
        self.x += 1
        while self.x < len(self.q) and len(self.q[self.x]) == 0:
            self.x += 1
    
    def __init__(self, vec2d):
        """
        Initialize your data structure here.
        :type vec2d: List[List[int]]
        """
        self.q = vec2d
        self.x, self.y = -1, 0
        self._move_down()        
    
    def next(self):
        """
        :rtype: int
        """
        ret = self.q[self.x][self.y]
        if self.y + 1 == len(self.q[self.x]):
            self.y = 0
            self._move_down()
        else:
            self.y += 1
            
        return ret
        
    def hasNext(self):
        """
        :rtype: bool
        """
        
        return self.x < len(self.q) and self.y < len(self.q[self.x])

Log in to reply
 

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