An answer to this question on Stack Overflow.

Question

I'm trying to accomplish a task in which you are given n (the size of a square chessboard, queens (the squares they occupy), and queries(a list of coordinates). I am to return a list of Boolean values saying whether or not each query is attackable by any of the queens. I know my algorithm works but I also know that it isn't efficient "enough". Through research, I'm guessing that the complexity is O(queensqueries)? So that's my first questions, is it O(queensqueries), if not why? Second, does anyone have an idea how I can optimize it possibly even down to O(queens + queries)? I apologize if this is a rudimentary question, but I am mainly self-taught and don't have anyone I can ask this. Thanks in advance!

def squaresUnderQueenAttack(n, queens, queries):
    output = []
    for i in queries:
        attackable = False
        for j in queens:
            if attackable != True and (i[0]==j[0] or i[1]==j[1] or abs(i[0]-j[0])==abs(i[1]-j[1])):
                attackable = True
                break
        output.append(attackable)
    return output

Answer

Your current code is O(queens * queries). You can improve it to O(queens + queries).

Make three arrays, each with 8 elements. Call them row, col, diagleft, and diagright.

Look at each queen, if it's in row 0, set that spot in row to true. If it's in col 3, set that spot to col in true. Label the diagonals 0-7 and make appropriate marks in them as well.

Now the arrays indicate all of the rows, columns, and diagonals that have queens.

Now, look at each query and check to see if any of the array entries corresponding to its location are marked true. If so, then a queen threatens it.

Note that in big-O notation, we're interested in which factor "dominates" the run-time, so the above solution is probably more appropriately thought of as operating in O(max(queens,queries)) time. That is, if you have many queries, the queens calculation takes only a little time. Similarly, if you have many queens and few queries, that operation will take most of your time.