HackerRank "Service Lane" in Python

Question

Problem statement:

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the highway and the service lane is N units. The service lane consists of N segments of unit length, where each segment can have different widths.

Calvin can enter into and exit from any segment. Let's call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment(j>i) and i ≥ 0. Calvin has to pass through all segments from index i to indexj (both inclusive).

Calvin has three types of vehicles - bike, car and truck, represented by 1, 2 and 3 respectively. These numbers also denote the width of the vehicle. We are given an array width[] of length N, where width[k] represents the width of kth segment of our service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including entry and exit segments.

• If width[k] is 1, only the bike can pass through kth segment.
• If width[k] is 2, the bike and car can pass through kth segment.
• If width[k] is 3, any of the bike, car or truck can pass through kth segment.

Given the entry and exit point of Calvin's vehicle in the service lane, output the type of largest vehicle which can pass through the service lane (including the entry & exit segment)

Input Format

The first line of input contains two integers - N & T, where N is the length of the freeway, and T is the number of test cases. The next line has N space separated integers which represents the width array.

T test cases follow. Each test case contains two integers - i & j, where i is the index of segment through which Calvin enters the service lane and j is the index of the lane segment where he exits.

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

Constraints:

2 <= N <= 100000

1 <= T <= 1000

0 <= i < j < N

2 <= j-i+1 <= min(N,1000)

1 <= width[k] <= 3, where 0 <= k < N

Solution:

N, T = map(int, input().split())
widths = list(map(int, input().split()))
for _ in range(T):
    i, j = map(int, input().split())
    vehicle = 3
    for x in range(i, j+1):
        width = widths[x]
        if width == 1:
            vehicle = 1 # Only a bike can pass
            break
        elif width == 2:
            vehicle = 2 # Only a car or bike can pass
    print(vehicle)

I'm looking for any way to make this shorter, simpler or more Pythonic.

Answer 1

You have at most 1,000 test cases, and each service lane is at most 1,000 segments, so this approach is feasible, but we can do better.

Consider an array of indices where the service lane width is 1, and another where the width is 2.

N, T = map(int, input().split())

ones = []
twos = []

for i, width in enumerate(map(int, input().split())):
    if width == 1:
        ones.append(i)
    elif width == 2:
        twos.append(i)

You can then use binary search to see if each segment contains a 1 or a 2.

for _ in range(T):
    start, end = map(int, input().split())
    if segment_search(ones, start, end) != -1:
        print(1)
    elif segment_search(twos, start, end) != -1:
        print(2)
    else:
        print(3)

Our indices are already in order. Our search stops when an index lies in the range [start, end]:

def segment_search(xs, start, end):
    low = 0
    high = len(xs) - 1
    while low <= high:
        mid = (low + high) // 2
        x = xs[mid]
        if start <= x and x <= end:
            return mid
        if end < x:
            high = mid - 1
        else:
            low = mid + 1
    return -1

As ones and twos can't have more than 100,000 elements, each call to segment_search will take at most 17 steps.

Answer 2

Shorter, simpler, and more Pythonic would be:

N, T = map(int, input().split())
widths = list(map(int, input().split()))
for _ in range(T):
    i, j = map(int, input().split())
    vehicle = min(widths[segment] for segment in range(i, j + 1))
    print(vehicle)

You would miss out on the shortcut when encountering a bike-only segment, though.

I've also renamed x to segment for clarity.

Answer 3

My solution to the problem, provided you don't mind the time complexity and prefer a pythonic(precise) code -

def serviceLane(n, cases):
    for i,j in cases:
        return min(width[i:j+1])