Your Social Network

Problem Overview

Each user from 2 to n points to one friend with a smaller number, so the links form a tree rooted at user 1.

Intuition

Each user from 2 to n points to one friend with a smaller number, so the links form a tree rooted at user 1. The users reachable from i are exactly the friends along the chain from i down to 1, and the distance is the number of links taken. Because every link goes to a smaller number, the chain is already in decreasing order. Writing it from the back of a small array gives increasing order with no sort, and the total work matches the size of the output.

Algorithm

1Compute the depth of every user in one pass. User 1 has depth 0, and user i has the depth of its friend plus one.
2The sum of all depths is the number of output rows, so presize the result list to it.
3For each user i, follow the friend links depth[i] times, writing each reached user into a scratch array from the last slot toward the first.
4Read the scratch array from the front. The user at position k is at distance depth[i] minus k, so append the row [i, user, distance].
5Box every number from 0 to n once and reuse those objects for every row.

Example Walkthrough

Input: arr = [1,1,2]

1. User 2 follows user 1 and user 3 follows user 1, so each gives one row with distance 1.
2. User 4 follows user 2, which follows user 1. The chain is 2 then 1.
3. Reversed, user 4 reaches 1 at distance 2 and 2 at distance 1.

Output: [[2,1,1],[3,1,1],[4,1,2],[4,2,1]]

Common Pitfalls

• Rows for one user must list the reached users in increasing order. Reversing the chain gives that without sorting.
• The friend of user i is arr[i minus 2], because the array starts at user 2.
• A long single chain produces about n squared over 2 rows. That is the output size, so no method can avoid it.
• Boxing the same small range of numbers for every row creates many objects. A shared array of boxed values avoids that.

Your Social Network.java

Java

// Approach: User i follows the chain i -> arr[i - 2] -> ... down to user 1.
// Every friend has a smaller number, so the chain is strictly decreasing.
// Writing it into a scratch array from the back puts the reachable users in
// increasing order with no sort. Depths are computed once up front, so the
// chain length and every distance are known before the walk, and the result
// list is presized to the exact number of pairs. User ids and distances all
// lie in 1..n, so each Integer is boxed once and shared across rows.
// Complexity: O(n + P) time, where P is the number of reachable pairs (the
// output size), O(n) extra space beyond the output.

import java.util.ArrayList;

class Solution {

    public ArrayList<ArrayList<Integer>> socialNetwork(int[] arr) {
        int n = arr.length + 1;
        int[] depth = new int[n + 1];
        long pairs = 0;
        for (int i = 2; i <= n; i++) {
            depth[i] = depth[arr[i - 2]] + 1;
            pairs += depth[i];
        }

        Integer[] boxed = new Integer[n + 1];
        for (int v = 0; v <= n; v++)
            boxed[v] = v;

        ArrayList<ArrayList<Integer>> res = new ArrayList<>((int) pairs);
        int[] chain = new int[n];
        for (int i = 2; i <= n; i++) {
            int d = depth[i];
            Integer self = boxed[i];
            int curr = i;
            for (int k = d - 1; k >= 0; k--) {
                curr = arr[curr - 2];
                chain[k] = curr;
            }
            for (int k = 0; k < d; k++) {
                ArrayList<Integer> row = new ArrayList<>(3);
                row.add(self);
                row.add(boxed[chain[k]]);
                row.add(boxed[d - k]);
                res.add(row);
            }
        }
        return res;
    }
}

Was this solution helpful?