Find Closest Node to Given Two Nodes

Basically, from each starting node, iterate through all the nodes you have not seen before, updating their distance as you go. Since some distances will not be updated, we can leave them as -1.

Then, you can iterate through all the nodes, ignoring the ones with distance -1, finding the minimum index of the node, where the maximum distance between node1 to that node and node2 to that node is minimized.

Example:

Index | Node 1 | Node 2
------|--------|-------
 0    |  1     |  3
 1    |  5     |  1
 2    |  4     |  0
 3    |  0     |  2
 4    |  3     |  5
 5    |  2     |  4
 6    | -1     | -1

In this case, you would choose index 3 since you minimize the maximum distance between itself and node1 & node2.

code

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        pair<int, int> ans = {INT32_MAX, INT32_MAX};
        vector<bool> seen(edges.size(), false);
        vector<pair<int, int>> distances(edges.size(), {-1, -1});
        distances[node1].first = 0;
        distances[node2].second = 0;

        int distance = 1;
        while (node1 != -1 && !seen[node1]) {
            seen[node1] = true;
            node1 = edges[node1];

            if (node1 != -1) {
                if (!seen[node1]) {
                    distances[node1].first = distance++;
                }
            }
        }

        fill(seen.begin(), seen.end(), false);

        distance = 1;
        while (node2 != -1 && !seen[node2]) {
            seen[node2] = true;
            node2 = edges[node2];

            if (node2 != -1) {
                if (!seen[node2]) {
                    distances[node2].second = distance++;
                }
            }
        }

        for (int i = 0; i < edges.size(); ++i) {
            if (distances[i].first >= 0 && distances[i].second >= 0) {
                int max_distance = max(distances[i].first, distances[i].second);
                if (max_distance < ans.second || (max_distance == ans.second && i < ans.first)) {
                    ans = {i, max_distance};
                }
            }
        }

        return ans.first == INT32_MAX ? -1 : ans.first;
    }
};

complexity

• Time: O(n) where n is the size of edges
• Space: O(n)

time taken

• 34 minutes
  • I took wayyyyy too long... I think I was distracted...