LeetCode - Algorithms - 690. Employee Importance

Problem

690. Employee Importance

Java

BFS

1

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
		int r = 0;

		boolean[] visited = new boolean[employees.size()];
		Queue<Integer> queue = new LinkedList<Integer>();
		for(int i=0; i<employees.size(); i++) {
			Employee e = employees.get(i);
			if (e.id==id) {
				for(Integer subId:e.subordinates)
					queue.add(subId);
				r+=e.importance;
				visited[i]=true;
				break;
			}
		}

		while (!queue.isEmpty()) {
			int currId = queue.poll();
			for(int i=0; i<employees.size(); i++) {
				if (!visited[i]) {
					Employee e = employees.get(i);
					if (e.id==currId) {
						for(Integer subId:e.subordinates)
							queue.add(subId);
						r+=e.importance;
						visited[i]=true;
					}
				}
			}
		}

		return r;       
    }
}

Submission Detail

• 108 / 108 test cases passed.
• Runtime: 14 ms, faster than 12.95% of Java online submissions for Employee Importance.
• Memory Usage: 42.6 MB, less than 100.00% of Java online submissions for Employee Importance.

2

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
		int r = 0;

		Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		boolean[] visited = new boolean[employees.size()];
		for(int i=0; i<employees.size(); i++) {
			map.put(employees.get(i).id, i);
			visited[i] = false;
		}

		Queue<Integer> queue = new LinkedList<Integer>();

		int idx = map.get(id);
		Employee e = employees.get( idx );
		for(Integer subId:e.subordinates)
			queue.add(subId);
		r+=e.importance;
		visited[idx]=true;

		while (!queue.isEmpty()) {
			int currId = queue.poll();
			idx = map.get(currId);
			if (!visited[idx]) {
				e = employees.get(idx);
				for (Integer subId : e.subordinates)
					queue.add(subId);
				r += e.importance;
				visited[idx] = true;
			}
		}

		return r;        
    }
}

Submission Detail

• 108 / 108 test cases passed.
• Runtime: 5 ms, faster than 54.03% of Java online submissions for Employee Importance.
• Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Employee Importance.

DFS

/*
// Employee info
class Employee {
    // It's the unique id of each node;
    // unique id of this employee
    public int id;
    // the importance value of this employee
    public int importance;
    // the id of direct subordinates
    public List<Integer> subordinates;
};
*/
class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
		boolean[] visited = new boolean[employees.size()];
		for(int i=0; i<employees.size(); i++) {
			map.put(employees.get(i).id, i);
			visited[i] = false;
		}

		int idx = map.get(id);
		Employee e = employees.get( idx );
		int r = e.importance;
		visited[idx]=true;
		r += dfs(employees, e, map, visited);

		return r;
    }
    
    private int dfs(List<Employee> employees, Employee employee, Map<Integer,Integer> map, boolean[] visited) {
		int r = 0;
		for(Integer subId:employee.subordinates) {
			int idx = map.get(subId);
			if (!visited[idx]) {
				Employee e = employees.get(idx);
				r += e.importance;
				visited[idx]=true;
				r += dfs(employees, e, map, visited);
			}
		}
		return r;
	}
}

Submission Detail

• 108 / 108 test cases passed.
• Runtime: 4 ms, faster than 99.82% of Java online submissions for Employee Importance.
• Memory Usage: 40.9 MB, less than 100.00% of Java online submissions for Employee Importance.