Model problem 13.11 as a graph

#1

I just want to share my idea that we can translate the problem 13.11 (find the longest contained interval or longest consecutive sequence) into a graph problem as follows:

Each number in the array corresponds to a node on a graph (or a number line) so that adjacent number nodes are connected. The longest contained interval is the maximum number of connected nodes (or longest segment) on the graph.

How to solve:

Add all node to an unvisited hash table (for fast lookup)
For each node
    If the node is not visited
        Mark the node as visited
        Explore all the connected nodes by DFS/BFS
        Update the maximum number of the connected nodes
Return the maximum of connected nodes
0 Likes
#2

Hey Duc,

I think your idea is very similar to the solution in the book. For the algorithm in the book, for each unvisited number, we search the lower bound and the upper bound which are exactly same as DFS/BFS part.

Solving this by graph modeling is a good practice of abstraction as many problems can be easily solved once applied that in graph.

0 Likes
#3

The solution for the graph model is indeed similar to the one in the book. I hope the model may provide an intuition why we can solve the problem by searching for lower and upper bounds.

0 Likes