Python, Simple with Explanation

  • 1

    We can separate the problem into two subproblems. The first subproblem is, given a 1 dimensional list of 0's and 1's, what is the longest chain of consecutive 1s? The second subproblem is to generate every line (row, column, diagonal, and anti-diagonal).

    The first problem is common. We keep track of the number of 1's we've seen before. If we see a 1, we add to our count and update our answer. If we see a 0, we reset. Alternatively, we can also use itertools.groupby. Straightforward code for the first part looks like this:

    def score(line):
      ans = count = 0
      for x in line:
        if x:
          count += 1
          ans = max(ans, count)
          count = 0
      return ans

    The second part is more complex. We can try to manipulate indices of the grid, but there is a trick. Each element in the grid belongs to exactly 4 lines: the r-th row, c-th column, (r+c)-th diagonal, and (r-c)-th anti-diagonal. We scan from left to right, top to bottom, adding each element's value to it's respective 4 groups. As we visited in reading order, our lines will be appended to in that order, which is suitable for our purposes.

    def longestLine(self, A):
        if not A: return 0
        def score(line):
            return max(len(list(v)) if k else 0 
                       for k, v in itertools.groupby(line))
        groups = collections.defaultdict(list)
        for r, row in enumerate(A):
            for c, val in enumerate(row):
                groups[0, r] += [val]
                groups[1, c] += [val]
                groups[2, r+c] += [val]
                groups[3, r-c] += [val]
        return max(map(score, groups.itervalues()))

  • 0

    This is awesome! I really appreciate your detailed explanations. Learnt a lot :)

Log in to reply

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