Random indice of a boolean grid

Let's say I have a square boolean grid (2D array) of size N. Some of the values are true and some are false (the <true values> / <false values> ratio is unspecified). I want to randomly choose an indice (x, y) so that grid[x][y] is true. If I wanted a time-efficient solution, I'd do something like this (Python):

x, y = random.choice([(x, y) for x in range(N) for y in range(N) if grid[x][y]])

But this is O(N^2), which is more than sufficient for, say, a tic-tac-toe game implementation, but I'm guessing it would get much more memory-consuming for large N.

If I wanted something that's not memory consuming, I'd do:

x, y = 0, 0
t = N - 1
while True:
    x = random.randint(0, t)
    y = random.randint(0, t)
    if grid[x][y]:
        break

But the issue is, if I have a grid of size of order 10^4 and there is only one or two true values in it, it could take forever to "guess" which indice is the one I'm interested in. How should I go about making this algorithm optimal?