LeetCode 134. Gas Station, 135. Candy
This post was migrated from Tistory. You can find the original here.
Problem
134. https://leetcode.com/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150
135. https://leetcode.com/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150
134. Approach
The only thing I could come up with was an O(n^2) solution.
1
2
3
4
5
6
7
8
9
10
11
12
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
sum_gas = 0
start_idx = 0
for i in range(len(gas)):
sum_gas += gas[i] - cost[i]
if (sum_gas < 0):
start_idx = i+1
sum_gas = 0
return start_idx
Run the for loop only once, and
sum_gas += gas[i] - cost[i]
whenever sum_gas goes negative, update start_idx.
There’s no condition asking for the smallest index or the most efficient trip — the problem guarantees “If there exists a solution, it is guaranteed to be unique,” meaning there’s only one possible answer.
Looking at it from that angle: if gas[i] - cost[i] is positive at i and also positive at i+1, there’s no reason to consider start_idx = i and start_idx = i+1 separately. If both i and i+1 are positive, starting at i gives a better chance of completing the trip successfully.
135. Approach
Walking through the array comparing i and i+1:
when ratings[i] < ratings[i+1] — i.e., the left side is bigger — you have to keep updating the candy count going leftward. That makes it O(n^2), but since the length is only up to 10^4 I figured I’d try it anyway, and it hit Time Limit Exceeded.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Time Limit Exceeded
def candy(self, ratings: List[int]) -> int:
result = [ 1 for _ in range(len(ratings)) ]
for i in range(len(ratings)-1):
left, right = ratings[i], ratings[i+1]
if left < right:
result[i+1] = result[i] + 1
elif right < left:
if result[i] > result[i+1]:
continue
result[i] = result[i+1] + 1
j = i-1
while j>-1:
if ratings[j] <= ratings[j+1]:
break
if result[j] <= result[j+1]:
result[j] = result[j+1] + 1
j -= 1
# print(result)
return sum(result)
I thought about how to get this down to a single pass of the for loop.
My approach: push the left > right case onto a stack, and
when left <= right, flush the stack that’s built up.
The stack builds a list that corresponds to a segment of result,
and flushing replaces that segment of result via a slice with the list we built.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# improvement 1
def candy(self, ratings: List[int]) -> int:
result = [ 1 for _ in range(len(ratings)) ]
left_stack = [1]
for i in range(len(ratings)-1):
left, right = ratings[i], ratings[i+1]
if left > right:
left_stack.append(left_stack[-1] + 1)
else:
# left_stack flush
if len(left_stack) > 1:
if left_stack[-1] < result[i-len(left_stack)+1]:
left_stack[-1] = result[i-len(left_stack)+1]
result[i-len(left_stack)+1:i+1] = left_stack[::-1]
left_stack = [1]
if left < right:
result[i+1] = result[i] + 1
# print(result, left_stack)
# left_stack finish flush
if len(left_stack) > 1:
leng = len(result)
if left_stack[-1] < result[leng - len(left_stack)]:
left_stack[-1] = result[leng - len(left_stack)]
result[leng-len(left_stack):leng] = left_stack[::-1]
# print(result)
return sum(result)
In the logic above, the left == right case also triggers a flush. Appending the same value as left_stack[-1] also causes a problem.
If you append the same value, ratings [3,2,2,1] turns into candy [3,2,2,1]. But it should come out as candy [2,1,2,1], hence the flush.
If the sequence ends on a left > right step, no flush happens, so that case has to be handled separately after the loop.
It passes and the runtime is decent, but with all the slicing and index-juggling during flush, there’s a high chance of missing an edge case somewhere.
I looked at another solution.
1
2
3
4
5
6
7
8
9
10
# improvement 2
def candy(self, ratings: List[int]) -> int:
candy=[1]*len(ratings)
for i in range(1,len(ratings)):
if ratings[i-1]<ratings[i]:
candy[i]=candy[i-1]+1
for i in range(len(ratings)-2,-1,-1):
if ratings[i+1]<ratings[i] and candy[i+1]>=candy[i]:
candy[i]=candy[i+1]+1
return sum(candy)
First pass left to right, capturing the rising parts of the result,
then pass right to left, capturing the falling parts of the result.
Improvement 2 is O(2n) while improvement 1 is O(n), but improvement 1 has slicing overhead, which made it slightly slower than improvement 2.
Runtime aside, improvement 2 is far better in terms of having no room for the code to leak bugs.