FastPrepFewest Pointer Changes to Make Every Node Good
Problems/Fewest Pointer Changes to Make Every Node Good

Fewest Pointer Changes to Make Every Node Good

Indeed logoIndeed● MediumNEW GRADOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: A node is good if it is node 1, points to node 1, or points to another good node, and the task is the fewest pointer changes that make every node good. In the author's retelling, array position i holds the node, 1 to N, that node i points to, and the example has 5 nodes that each point to themselves, with answer 4.

The report does not say how the points-to-a-good-node rule works for nodes that point around a loop. Here, as in the example where self-pointing nodes must change, a node is good only if following its pointers reaches node 1. Node 1's own pointer does not matter. You get only the array, whose first value is node 1's pointer, and there are at most 5 * 10^4 nodes.

The judged task matches the report at about 90%.

There are n nodes numbered 1 to n. Every node points to exactly one node, possibly itself. You are given the array pointers, where pointers[i] is the node that node i + 1 points to.

A node is good if at least one of these holds:

  1. It is node 1.
  2. It points to node 1.
  3. It points to a good node.

In other words, a node other than node 1 is good when following the pointers from it eventually reaches node 1. Nodes that only point around a loop that never reaches node 1 are not good. Node 1 is good no matter where it points.

You may change where any node points. Return the smallest number of nodes whose pointers you must change so that every node is good.

Function

minimumChanges(pointers: int[]) → int

Examples

Example 1

pointers = [1,2,3,4,5]return = 4

Every node points to itself. Node 1 is good. Nodes 2, 3, 4 and 5 each only reach themselves, so each one must be changed, for example to point at node 1. The answer is 4.

Example 2

pointers = [3,1,2,5,4,4]return = 1

Node 2 points to node 1, and node 3 points to node 2, so both are good. Nodes 4 and 5 point at each other, and node 6 points into that loop, so none of the three reaches node 1. Changing node 4 to point at node 1 makes node 4 good, then node 5 and node 6 through it. The answer is 1.

Example 3

pointers = [4,1,2,3]return = 0

Node 4 points to 3, node 3 to 2, and node 2 to node 1, so every node reaches node 1. Node 1's own pointer does not matter. The answer is 0.

Constraints

  • 1 <= n == pointers.length <= 5 * 10^4
  • 1 <= pointers[i] <= n

More Indeed problems

  • Insert into an Unrolled Linked ListPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
  • Course Completion OrderPHONE SCREEN · Seen May 2025
  • Recipes You Can PreparePHONE SCREEN · Seen May 2025
All Indeed interview questionsSee Indeed hiring insights
Saved
class Solution {
    public int minimumChanges(int[] pointers) {
        // Write your code here.
    }
}
Checking account…