Quadrant Queries challenge Running the same test 10,000 times with cProfile tells me that most of the damage happens in the count() function. This is my attempt at a solution to the Quadrant Queries challenge from InterviewStreet (the problem statement can be found here). 

According to InterviewStreet, I passed 3/11 testcases and I ran out of CPU time. I have no way of knowing whether I was 3 for 3 and ran out of time or say, 3 for 6 and ran out of time. I don't know if my code works on all input.

Please help me optimize this code:

def reflect_x(i, j, coordinates):
    for pair in xrange(i-1, j):
        coordinates[pair][1] = -coordinates[pair][1]
    return coordinates

def reflect_y(i, j, coordinates):
    for pair in xrange(i-1, j):
        coordinates[pair][0] = -coordinates[pair][0]
    return coordinates

def count(i, j, coordinates):
    quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0
    for pair in xrange(i-1, j):
        x, y = coordinates[pair][0], coordinates[pair][1]

        if x &gt;= 0 and y &gt;= 0:
            quad_one += 1
        elif x &lt; 0 and y &gt;= 0:
            quad_two += 1
        elif x &lt; 0 and y &lt; 0:
            quad_three += 1
        elif x &gt;= 0 and y &lt; 0:
            quad_four += 1

    print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):

    for query in queries:
        if query[0] == "X": 
            reflect_x(query[1], query[2], coordinates)
        elif query[0] == "Y":
            reflect_y(query[1], query[2], coordinates)
        elif query[0] == "C":
            count(query[1], query[2], coordinates)
        else:
            print query

if __name__ == "__main__":
    N = int(raw_input())
    coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]

    Q = int(raw_input())
    queries = [[query[0], int(query[1]), int(query[2])] for query in (query.split() for query in (raw_input() for i in xrange(Q)))]

    reflect(coordinates, queries)
def reflect_x(i, j, coordinates):
    for pair in xrange(i-1, j):
        coordinates[pair][1] = -coordinates[pair][1]
    return coordinates


Something like:

def reflect_x(i, j, coordinates):
    coordinates[i-1:j] = ((x,-y) for x,y  in coordinates[i-1,j])


Is clearer and possibly slightly faster. Also, modify or return, don't do both.

def count(i, j, coordinates):
    quad_one, quad_two, quad_three, quad_four = 0, 0, 0, 0


If you have a count attached to your variable, the probably means it should be a list

    quad = [0] * 4

    for pair in xrange(i-1, j):


You may be better off slicing the list. That will be happen entirely in C, but looking up the value each time happens in python.

        x, y = coordinates[pair][0], coordinates[pair][1]


Same as:

        x, y = coordinates[pair]


...

        if x &gt;= 0 and y &gt;= 0:
            quad_one += 1
        elif x &lt; 0 and y &gt;= 0:
            quad_two += 1
        elif x &lt; 0 and y &lt; 0:
            quad_three += 1
        elif x &gt;= 0 and y &lt; 0:
            quad_four += 1

    print "%d %d %d %d" % (quad_one, quad_two, quad_three, quad_four)

def reflect(coordinates, queries):


bad name, this function doesn't only reflect

    for query in queries:
        if query[0] == "X": 
            reflect_x(query[1], query[2], coordinates)
        elif query[0] == "Y":
            reflect_y(query[1], query[2], coordinates)
        elif query[0] == "C":
            count(query[1], query[2], coordinates)
        else:
            print query

if __name__ == "__main__":
    N = int(raw_input())
    coordinates = [[int(pair[0]), int(pair[1])] for pair in (pair.split() for pair in (raw_input() for i in xrange(N)))]


You don't need to do everything on one line. You can also unpack the tuple in the for clause.

    coordinate_lines = (raw_input() for i in xrange(N))
    coordinates = [(int(x),int(y)) for x,y in line.split for line in coordinate_lines]


As for optimisation: Firstly, you need to realise that you don't actually care what the coordinates are. All you care about is the quadrants. The reflection operations merely move you from one quadrant to the other.

I have to disagree with Jeff Mercado, as I don't think his approach will work. (maybe I've missed what he's hinting at.) Basically what you have is a worst case O(N*Q) running time. Since both N and Q are large numbers you cannot get away with doing that. His approach reduces the complexity to O(1) for the count operation, but leaves O(N) for the reflect operations. That's still going to give you O(N*Q).

We need to reduce the cost of the reflect operations as well.

Basically, for each quadrant we need to keep track of the points in that quadrant. We'll put them in some sort of data structure. We need a data structure that will allow the efficient implementation of:


Finding all points with indexes between a start/stop index
Swapping those points between two different versions of the data structure
Finding the count of all points currently in the data structure


Basically, we need all of these operations in logarithmic time or better. Figuring out what kind of data structure gives you that is left as an exercise for the reader.