Domain 2MediumMEDIUM

Web Crawler

Traverse a web graph starting from startUrl, collecting all reachable URLs that share the same hostname using DFS/BFS with visited set management.

Domain: medium•Updated: 2026-09-11
#DFS#BFS#Graph Traversal#Set

Problem Breakdown

The problem requires traversing a directed graph where nodes are URLs and edges represent hyperlinks found via HtmlParser.getUrls. The core constraints are:

  1. Hostname Filtering: Only visit links that share the exact hostname (domain) of the starting URL. Paths, query parameters, or ports must be ignored for matching purposes.
  2. Cycle Prevention & Deduplication: Web graphs often contain cycles and multiple paths to the same page. We must ensure each valid URL is processed exactly once using a visited set.
  3. Traversal Order: The problem allows returning URLs in any order, so Depth-First Search (DFS) or Breadth-First Search (BFS) are both acceptable choices for traversal logic.

Intuition

This is a graph exploration problem with specific filtering constraints.

  1. We start at startUrl and extract its hostname to establish the target domain.
  2. For every URL we visit, we fetch all outgoing links (getUrls).
  3. Each link must be checked against two conditions:
    • Does it belong to the same hostname? (Hostname parsing).
    • Have we already visited this specific URL? (Visited set check).
  4. If both are true, we add the new URL to our collection and mark it as visited before pushing onto the stack/queue. Marking upon discovery prevents duplicate entries in the traversal structure, optimizing space complexity compared to checking on pop.

Approach

  1. Hostname Extraction: Create a helper function that parses http://hostname/path into just hostname. Since ports are not specified per constraints, we look for the substring starting after // and ending at the next /.
  2. Initialization:
    • Parse startUrl to get target_hostname.
    • Initialize a stack (for DFS) or queue with startUrl.
    • Maintain a set of visited URLs initialized with startUrl. This ensures we don’t process the start node multiple times if it appears as its own link.
  3. Traversal:
    • While the traversal structure is not empty, pop/peek current URL.
    • Call getUrls to get neighbors.
    • Iterate through neighbors: Check hostname match and visited status. If valid and unvisited, add to stack and mark as visited immediately.
  4. Result: Convert the set of visited URLs into a list for return.

Complexity Analysis

  • Time Complexity: O(N⋅L)O(N \cdot L), where NN is the number of reachable nodes under the hostname constraint (valid crawled pages), and LL is the average length of a URL string required for parsing hostnames. Each edge in the valid subgraph is processed once because we mark nodes as visited immediately upon discovery.
  • Space Complexity: O(N⋅L)O(N \cdot L) to store the visited set, which contains all unique URLs found under the same hostname, and the stack/queue used for traversal.

Solution

class Solution:
    def crawl(self, startUrl):
        # Helper function to extract hostname from URL string 
        # assuming http:// protocol without port specified (per problem constraints)
        def get_hostname(url):
            idx = url.find('//') + 2
            
            if idx >= len(url):
                return ""
            
            slash_idx = url.find('/', idx)
            end_idx = slash_idx if slash_idx != -1 else len(url)
            
            return url[idx:end_idx]

        target_hostname = get_hostname(startUrl)
        
        # Visited set tracks all valid URLs found under the same hostname.
        visited = {startUrl} 
        stack = [startUrl]
        
        while stack:
            curr_url = stack.pop()
            
            try:
                neighbors = HtmlParser.getUrls(curr_url) 
            except Exception:
                continue
                
            for neighbor in neighbors:
                # Check if not visited first to avoid redundant hostname parsing and checks
                if neighbor not in visited:
                    hostname = get_hostname(neighbor)
                    
                    # Only crawl if same hostname matches startUrl's hostname
                    if hostname == target_hostname:
                        stack.append(neighbor)
                        visited.add(neighbor)

        return list(visited)

Edge Cases Handled

  • **Start URL with