Campus Shuttle Loop Coverage

Published atDate not available

Array Medium 0 views

Like0

This problem feels like a little puzzle you can solve one step at a time. In Campus Shuttle Loop Coverage, you are trying to work toward the right number by following one clear idea.

Here, you are mostly deciding whether a rule stays true while you look through the input. Sometimes that means checking if things are connected, balanced, or allowed. Sometimes it means noticing the first place where the rule breaks. The answer depends on being careful from beginning to end.

For example, if the input is n = 6, walkways = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0, the answer is 6. The shuttle stops in every building along the loop without revisiting any stops. Another example is n = 4, walkways = [[0,1],[2,3]], start = 1, which gives 2. The loop covers buildings 1 and 0, while the other set stays untouched.

This problem needs a little more patience than a very easy one. The key is noticing the exact moment when the rule stays true or breaks.

Example Input & Output

Example 1

Input

n = 6, walkways = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0

Output

Explanation

The shuttle stops in every building along the loop without revisiting any stops.

Example 2

Input

n = 4, walkways = [[0,1],[2,3]], start = 1

Output

Explanation

The loop covers buildings 1 and 0, while the other set stays untouched.

Example 3

Input

n = 5, walkways = [[0,1],[1,2],[2,0],[3,4]], start = 2

Output

Explanation

Buildings 0, 1, and 2 are visited; the remaining pair sits in another component.

Algorithm Flow

Recommendation Algorithm Flow for Campus Shuttle Loop Coverage

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;

class Solution {
    public int shuttle_loop_coverage(int n, int[][] walkways, int start) {
        if (n == 0) return 0;
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] path : walkways) {
            int u = path[0], v = path[1];
            if (u < n && v < n) {
                adj[u].add(v);
                adj[v].add(u);
            }
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj[curr]) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return visited.size();
    }
}

javascript

function shuttle_loop_coverage(n, walkways, start) {
    if (n === 0) return 0;
    const adj = Array.from({ length: n }, () => []);
    for (const [u, v] of walkways) {
        if (u < n && v < n) {
            adj[u].push(v);
            adj[v].push(u);
        }
    }
    const visited = new Set([start]);
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
        const curr = queue[head++];
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

php

function shuttle_loop_coverage($n, $walkways, $start) {
    if ($n == 0) return 0;
    $adj = array_fill(0, $n, []);
    foreach ($walkways as $path) {
        $u = $path[0]; $v = $path[1];
        if ($u < $n && $v < $n) {
            $adj[$u][] = $v;
            $adj[$v][] = $u;
        }
    }
    $visited = [$start => true];
    $queue = [$start];
    $head = 0;
    while ($head < count($queue)) {
        $curr = $queue[$head++];
        foreach ($adj[$curr] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
    return count($visited);
}

python

from typing import List
from collections import deque

def shuttle_loop_coverage(n: int, walkways: List[List[int]], start: int) -> int:
    if n == 0: return 0
    adj = [[] for _ in range(n)]
    for u, v in walkways:
        if u < n and v < n:
            adj[u].append(v)
            adj[v].append(u)
    
    visited = {start}
    queue = deque([start])
    while queue:
        curr = queue.popleft()
        for neighbor in adj[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return len(visited)

rust

use std::collections::{VecDeque, HashSet};

pub fn shuttle_loop_coverage(n: i32, walkways: Vec<Vec<i32>>, start: i32) -> i32 {
    if n == 0 { return 0; }
    let mut adj = vec![vec![]; n as usize];
    for bridge in walkways {
        let u = bridge[0] as usize;
        let v = bridge[1] as usize;
        if u < n as usize && v < n as usize {
            adj[u].push(v);
            adj[v].push(u);
        }
    }
    let mut visited = HashSet::new();
    visited.insert(start as usize);
    let mut queue = VecDeque::new();
    queue.push_back(start as usize);
    while let Some(curr) = queue.pop_front() {
        for &neighbor in &adj[curr] {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
            }
        }
    }
    visited.len() as i32
}

typescript

function shuttle_loop_coverage(n: number, walkways: number[][], start: number): number {
    if (n === 0) return 0;
    const adj: number[][] = Array.from({ length: n }, () => []);
    for (const [u, v] of walkways) {
        if (u < n && v < n) {
            adj[u].push(v);
            adj[v].push(u);
        }
    }
    const visited = new Set<number>([start]);
    const queue = [start];
    let head = 0;
    while (head < queue.length) {
        const curr = queue[head++];
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

Related Array Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Campus Shuttle Loop Coverage

Example Input & Output

Algorithm Flow

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Array Challenges

Harbor Ferry Route Planner

Skyway Signal Cluster

Museum Corridor Sweep

City Signal Span

Celestial Skyline Layout

Aurora Diary Synthesis

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.