kindred mauve
I was doing a problem on a leetcode style website but I was failing some of the test cases due to my program being too slow. I will list the problem and my sudo code below. I would appreciate someone helping me find how I could have reduced the time complexity.
Problem:
You are given a number line of length length. You are given a list of instructions prompts that contains tuples of length 2. prompts[i][0] is a number corresponding with a number on the number line. prompts[i][1] is a number corresponding with a color. Go through the prompts and for each prompt color the number on the number line the given color. Then add the number of sequential pairs (zero does not count) to a results array. EX: line = [0,1,1] = 1 pair, line = [1,1,1] = 2 pair, line = [1,2,3] = 0 pair.
My strategy
def solution(length, prompts):
nums = {p[0] for p in prompts}
results = []
line = {}
for p in prompts:
if p[0] - 1 not in nums and p[0] + 1 not in nums:
results.append(results[-1])
continue
line[p[0]] = p[1]
count = 0
for key in line.keys():
if key == line.get(key + 1):
count += 1
results.append(count)
return results
cosmic nacelle
elder orchid
outer pollen
