FastPrepCount Linked-List Islands

Count Linked-List Islands

Google logoGoogle● MediumNEW GRADONSITE INTERVIEW
Learn

Problem statement

You are given several heads of finite, acyclic singly linked lists. Different lists may share node objects. Once two lists reach the same node, their remaining suffix is therefore shared.

Two heads belong to the same island when their reachable lists share at least one node. Return the number of distinct islands represented by the given heads.

Indexed representation

Nodes are identified by indices from 0 through next.length - 1. For node i, next[i] is the index of its next node, or -1 when i is a tail. Each value in heads is the index of one list head.

Duplicate heads and heads that point into the middle of another list are allowed. They do not create an additional island.

Function

countLinkedListIslands(next: int[], heads: int[]) → int

Examples

Example 1

next = [1,2,-1,4,2,-1]heads = [0,3,5]return = 2

The lists beginning at 0 and 3 merge at node 2, so both end at tail 2 and form one island. Head 5 ends at a different tail and forms the second island.

Example 2

next = [1,-1,3,1,-1]heads = [0,2,4,3]return = 2

Heads 0, 2, and 3 all reach tail 1. Head 4 reaches tail 4, so there are two islands.

Constraints

  • 1 <= next.length <= 200000.
  • 1 <= heads.length <= 100000.
  • Every next[i] is -1 or a valid node index.
  • Every heads[i] is a valid node index.
  • Following next from any node eventually reaches -1; no list contains a cycle.

More Google problems

See Google hiring insights
public int countLinkedListIslands(int[] next, int[] heads) {
    // Write your code here.
}
next[1,2,-1,4,2,-1]
heads[0,3,5]
expected2
Checking account…