如何降低搜索算法时间复杂度？CodeWars点灯问题优化求助

我在CodeWars遇到一个涉及搜索算法的问题——Light Switch。作为新手，我实现的代码能正常运行，但想提升速度，优化时间复杂度。

首次BFS实现 #

# n is the number of lights
# corresponding_lights_list is the array representing relationships between lights and switches
# returns a boolean, represents whether it is possible to turn all the lights on.
 
def light_switch(n, corresponding_lights_list):
    lights = [0]*n
    oldlights = []
    queue = []
    while True:
        for s in corresponding_lights_list :
            newlights = [1 - lights[l] if l in s else lights[l] for l in range(n)]
            if newlights == [1]*n :
                return True
            if not (newlights in oldlights or newlights in queue) :
                queue.append(newlights)
        oldlights.append(lights)
        lights = queue.pop(0)
        if len(queue) == 0 :
            return False

双向搜索尝试 #

from collections import deque
def light_switch(n, corresponding_lights_list):
    lights1 = [0]*n
    lights2 = [1]*n
    oldlights1 = []
    oldlights2 = []
    queue1 = deque()
    queue2 = deque()
    while True:
        oldlights1.append(lights1)
        oldlights2.append(lights2)
        for s in corresponding_lights_list :
            newlights1 = [1 - lights1[l] if l in s else lights1[l] for l in range(n)]
            newlights2 = [1 - lights2[l] if l in s else lights2[l] for l in range(n)]
            if not (newlights1 in oldlights1 or newlights1 in queue1) :
                queue1.append(newlights1)
            if not (newlights2 in oldlights2 or newlights2 in queue2) :
                queue2.append(newlights2)
            if newlights2 in queue1 :#or newlights2 in oldlights1 or newlights1 in queue2 or newlights1 in oldlights2 :
                return True
        lights1 = queue1.popleft()
        lights2 = queue2.popleft()
        if len(queue1) == 0 :
            return False

希望能获得代码改进建议或通用优化思路，请尽量保持通用性，我仍想自行解决该问题。

内容的提问来源于stack exchange，提问作者Mayssa Ghanmi