1901_line_trip.py

# logic
def can_take_the_trip() -> int:
    """
    logic:
    calculate gaps between each petrol stations, the max gap is the minimum fuel(1unit = 1lt) needed to complete the trip
    """
    n, x = map(int, input().split())
    petrol_stations = list(map(int, input().split()))

    # approach 1
    # fuel = capacity

    # # from src -> destn
    # for i in range(1, x + 1):
    #     fuel -= 1
    #     if fuel < 0:
    #         return False
    #     if i in petrol_stations:
    #         fuel = capacity

    # # from destn -> source - 1
    # for i in range(x - 1, 0, -1):
    #     fuel -= 1
    #     if fuel < 0:
    #         return False
    #     if i in petrol_stations:
    #         fuel = capacity

    # # to source
    # fuel -= 1
    # return fuel >= 0

    # approach 2
    # gap = 0

    # _petrol_stations = [0] * (n + 2)
    # _petrol_stations[1 : n + 1] = petrol_stations[:]
    # # compute the gap between last station to last point + last point to last station -> virtual point
    # _petrol_stations[n + 1] = x + (x - petrol_stations[n - 1])

    # for i in range(0, n + 1):
    #     gap = max(gap, (_petrol_stations[i + 1] - _petrol_stations[i]))

    # return gap

    # approach 3
    gap = petrol_stations[0]
    for i in range(1, n):
        gap = max(gap, petrol_stations[i] - petrol_stations[i - 1])

    # handle the case for last station to last point + last point to last station
    gap = max(gap, 2 * (x - petrol_stations[n - 1]))

    return gap


t = int(input())

for _ in range(t):

    # capacity = 0
    # while True:
    #     res = can_take_the_trip(capacity, petrol_stations, x)
    #     if res:
    #         print(capacity)
    #         break
    #     else:
    #         capacity += 1

    print(can_take_the_trip())

This takes O(n) time and O(n) space