Problem statement

https://binarysearch.com/problems/Number-of-Islands/

Solution

Almost the same as 204. Count Primes

Complexity

It is O(n log log n) here for time and O(n) for space.

Code

class Solution:
    def solve(self, n):
        sieve = [0, 0] + [1] * (n - 1) 
        for k in range(ceil(n**0.5) + 1):
            if sieve[k]:
                for i in range(k*k, n+1, k):
                    sieve[i] = 0
        return [x for x in range(n+1) if sieve[x] == 1]