Edges to Adjacency List Editorial

Practice Problem Link: Edges to Adjacency List

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given the nodes and edges of a graph, calculate the adjacency list for the graph.

You have a graph with n nodes indexed from 0 to n-1. You also have m bi-directional edges each connecting a couple of nodes.

You have to return the adjacency list for the given graph.

Approach

An adjacency list is a way of representing graphs, where each node corresponds to a list of nodes, to which it is connected.

• Create a 2-D array having n rows.
• Traverse the given edges. Let's say there is an edge between nodes i and j. Then add j in the ith row of the 2-D array and i in the jth row of the array.

Analysis

• Time Complexity: O(m)
• Auxiliary Space Complexity: O(1)

Implementation

C++

vector<vector<int>> edgesToAdjList(int n, vector<vector<int>> edges) {
    vector<vector<int>> adjList(n);
	for (int i = 0; i < edges.size(); i++) {
		adjList[edges[i][0]].push_back(edges[i][1]);
		if (edges[i][0] == edges[i][1]) {
			continue;
		}
		adjList[edges[i][1]].push_back(edges[i][0]);
	}
	return adjList;
}

Java

class Solution {
    ArrayList<Integer>[] edgesToAdjList(int n, int[][] edges) {
		ArrayList<Integer>[] adjList = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			adjList[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < edges.length; i++) {
			adjList[edges[i][0]].add(edges[i][1]);
			if (edges[i][0] == edges[i][1]) {
				continue;
			}
			adjList[edges[i][1]].add(edges[i][0]);
		}
		return adjList;
    }
}