FastPrepLowest Common Ancestor with Parent Pointers
Problem · Tree

Lowest Common Ancestor with Parent Pointers

Learn this problem
● EasyAmazon logoAmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insights

Problem statement

A rooted tree has nodes numbered from 0 through parent.length - 1. The root has parent -1; every other entry points to its direct parent. A node may have any number of children.

Given two node indices first and second, return their lowest common ancestor. A node is considered an ancestor of itself.

Function

lowestCommonAncestorWithParents(parent: int[], first: int, second: int) → int

Examples

Example 1

parent = [-1,0,0,1,1,2,2]first = 3second = 4return = 1

Nodes 3 and 4 share direct parent 1.

Example 2

parent = [-1,0,0,1,1,2,2]first = 3second = 6return = 0

The two upward paths first meet at the root.

Example 3

parent = [-1,0,1,1,3,3]first = 1second = 5return = 1

Node 1 lies on node 5's ancestor chain and is its own ancestor.

Constraints

  • 2 <= parent.length <= 100000.
  • The parent links form one rooted tree with exactly one -1.
  • 0 <= first, second < parent.length.
  • first != second.

More Amazon problems

drafts saved locally
public int lowestCommonAncestorWithParents(int[] parent, int first, int second) {
  // write your code here
}
parent[-1,0,0,1,1,2,2]
first3
second4
expected1
checking account