April Leet Code Selection

6 minute read

Leet Code Practice Selection

335. Self Crossing

You are given an array x of n positive numbers. You start at point (0,0) and moves x[0] metres to the north, then x[1] metres to the west, x[2] metres to the south, x[3] metres to the east and so on. In other words, after each move your direction changes counter-clockwise.

Write a one-pass algorithm with O(1) extra space to determine, if your path crosses itself, or not.

Solution

  • First, I tried thinking of ways the path can keep turning. It can grow indefinitely (when south>north and east>west). It can shrink for a while with following (south<north and east<west). It can also grow for a while and then shrink. Once it start shrinking that’s the path towards end. Either it will cross or it will stop. So my first idea was to follow this two states and ensure they are happening. I didn’t pursue this line of thinking.
  • It is important that all values are positive so the line keeps turning left. You can also rotate your point of view so that every move is a north move. This will help writing the recursion.
  • Later I realized that validity of current move depends only on the last 5 moves and wrote the conditions where there is no cut happening. (First I thought the current move only depends 4, then had to add a flag for the last move). The answer is O(1) space and O(N) run time.
  • After writing the solution realized that a better solution would be write the recursion answering the question: given past moves(5) does next move cut?. This could make the solution shorter and more legible.
    class Solution(object):
      def isSelfCrossing(self, x):
          """
          :type x: List[int]
          :rtype: bool
          """
          if len(x)<5:
              if len(x)==4:
                  x1, x2, x3, x4 = x
                  rules = [(x1>=x3 and x2>x4),
                           x3>x1]
                  return not any(rules)
              else:
                  return False
          last_lim = None
          for i in range(len(x)-4):
              # print(x[i:i+5], last_lim)
              x1, x2, x3, x4, x5 = x[i:i+5]
              safe_moves = [(x1>=x3 and x2>x4),
                            (x3>x1 and x2>x4 and x5<x3),
                            (x3>x1 and x2==x4 and (x5+x1)<x3),
                            (x3>x1 and x2<x4)]
              # print(safe_moves)
              if (not any(safe_moves)
                  or (last_lim is not None and x5>=last_lim)):
                  return True
              # Reset last_lim
              last_lim = None
              if (x3>x1 and x2<x4 and x5<=x3 and x5>=(x3-x1)):
                  last_lim = x4-x2
          return False
    

692. Top K Frequent Words

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Solution

  • Seems simple! It is, indeed. Especially with the collections.Counter.
  • One important observation is that the we want to get highest count words with lowest string value. So, they go in different direction. Since the counts are never zero, we can negate them to make the direction same. Now we can order in increasing order in both word and count. We create tuples so that the negative count comes first (that’s what we care first) and the word itself second to break the ties.
  • Now we can just use sorted which by default sort by the first element and go to the next one. We would return the first k words.
    def topKFrequent(self, words, k):
      """
      :type words: List[str]
      :type k: int
      :rtype: List[str]
      """
      from collections import Counter
      from operator import itemgetter
      unsorted_counter = ((-v, k) for k,v in Counter(words).items())
      return list(v for _, v in sorted(unsorted_counter))[:k]
    

51. N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.

Solution

  • N-queen problem has a simple backtracking solution. Where you start from first column and advance to the next column one by one. At each step changing the state and recurse to the next stage. After the call you would remove the move and try another move if possible. It is also possible to advance 1 row at a time, but we will stick into putting queens to the columns starting from the left most column.
  • State of a n-board: We can represent a the solution to a n-queen problem with nn matrix. However there would be bunch of zeros since we would have only n/n^2 non-zero elements in it. Here I would propose a different representation, where we color the board witch each move in 4 directions: row, column, right diagonal and left diagonal. There are 2n-1 many diagonal in each direction and placing a queen to location (i, j) on the board would correspond to painting row i, column j and right diagonal i+j and left diagonal n+i-j-1. And the catch is we can only place a column when all 4 element corresponding to the move (i,j) is zero. If we make a move, we set the corresponding these elements to 1.
  • Being able to reach to the last column and to make a move there means a solution has been found, so we will return the row of the last move. Each recursive call that returns a non-empty list would add its move(j) to the each element of the list and append to the results’s found so far on a particular call. So at the end when j=0 the list results would have solutions with size n.
    class Solution(object):
      def solveNQueens(self, n):
          """
          :type n: int
          :rtype: List[List[str]]
          """
          rows = [0]*n
          r_diag = [0]*(2*n-1)
          l_diag = [0]*(2*n-1)
          def place_col(i):
              result = []
              for j in range(n):
                  if rows[j] == 0 and r_diag[i+j] == 0 and l_diag[i-j+n-1] == 0:
                      if i == (n-1):
                          return [[j]]
                      rows[j] = r_diag[i+j] = l_diag[i-j+n-1] = 1
                      # Recurse
                      res = place_col(i+1)
                      for ls in res:
                          ls.append(j)
                          result.append(ls)
                      # Backtrack
                      rows[j] = r_diag[i+j] = l_diag[i-j+n-1] = 0
              return result
          result = place_col(0)
    
          f_q = lambda i: '.'*i + "Q" + '.'*max(n-i-1, 0)
          return map(lambda l: [f_q(e) for e in l], result)