FastPrep
Problem · Array

Mark a Deleted Forest Subtree

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

A forest of nodes numbered from 0 through n - 1 is represented by parent. Every root points to itself, and every nonroot entry is the index of its parent.

Delete the subtree rooted at deleteIndex by returning a copy of parent in which that node and every descendant have value -1. Preserve every entry outside the deleted subtree exactly.

Function

markDeletedSubtree(parent: int[], deleteIndex: int) → int[]

Examples

Example 1

parent = [0,0,0,2,4,4]deleteIndex = 2return = [0,0,-1,-1,4,4]

Nodes 2 and 3 are the selected subtree and become -1.

Example 2

parent = [0,0,1,1]deleteIndex = 3return = [0,0,1,-1]

Only the selected leaf is marked.

Example 3

parent = [0,0,2,2,4]deleteIndex = 2return = [0,0,-1,-1,4]

The other rooted trees retain their original parent entries.

Constraints

  • 1 <= parent.length <= 200000.
  • 0 <= parent[i] < parent.length.
  • The parent links form a valid forest whose only cycles are self-pointing roots.
  • 0 <= deleteIndex < parent.length.

More Pinterest problems

drafts saved locally
public int[] markDeletedSubtree(int[] parent, int deleteIndex) {
  // write your code here
}
parent[0,0,0,2,4,4]
deleteIndex2
expected[0,0,-1,-1,4,4]
checking account