Given a maze with N cells. Each cell may have multiple entry points but not more than one exit (i.e entry/exit points are unidirectional doors like valves).
You are given an array Edge[] of N integers, where Edge[i] contains the cell index that can be reached from cell i in one step. Edge[i] is -1 if the ith cell doesn't have an exit. 
The task is to find the cell with maximum weight (The weight of a cell is the sum of cell indexes of all cells pointing to that cell). If there are multiple cells with the maximum weight return the cell with highest index.
Note: The cells are indexed with an integer value from 0 to N-1. If there is no cell pointing to the ith cell then the weight of the i'th cell is zero.
Example 1:
Input:
N = 4
Edge[] = {2, 0, -1, 2}
Output: 2
Explanation: 
1 -> 0 -> 2 <- 3
weight of 0th cell = 1
weight of 1st cell = 0 
(because there is no cell pointing to the 1st cell)
weight of 2nd cell = 0+3 = 3
weight of 3rd cell = 0
There is only one cell which has maximum weight
(i.e 2) So, cell 2 is the output.
Example 2:
Input:
N = 1
Edge[] = {-1}
Output: 0
Explanation:
weight of 0^{th} cell is 0.
There is only one cell so 
cell 0 has maximum weight.
Your task:
You dont need to read input or print anything. Your task is to complete the function maxWeightCell() which takes the integer N denoting the number of cells and the array Edge[] as input parameters and returns the cell which has maximum weight. If there are multiple answers then return the cell with highest index.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
-1 < Edge[i] < N
Edge[i] != i

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



class Solution():

    def maxWeightCell(self, N, Edge):

        #your code goes here

Solutions:
class Solution:

	def maxWeightCell(self, N, Edge):
		adj = [0 for i in range(N + 1)]
		for (ind, val) in enumerate(Edge):
			if val != -1:
				adj[val] += ind
		maxi = max(adj)
		for i in range(N - 1, -1, -1):
			if adj[i] == maxi:
				return i
		return 0


class Solution:

	def maxWeightCell(self, N, Edge):
		weights = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weights[Edge[i]] += i
		max_weight = max(weights)
		max_weight_cell = -1
		for i in range(N):
			if weights[i] == max_weight:
				max_weight_cell = i
		return max_weight_cell


class Solution:

	def maxWeightCell(self, N, Edge):
		wt = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				wt[Edge[i]] += i
		ans = max(wt)
		for i in range(N - 1, -1, -1):
			if wt[i] == ans:
				return i


class Solution:

	def maxWeightCell(self, N, Edge):
		temp = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				temp[Edge[i]] += i
		ans = 0
		max_val = float('-inf')
		for i in range(N):
			if temp[i] >= max_val:
				ans = i
				max_val = temp[i]
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		mx = max(weight)
		return [i for (i, n) in enumerate(weight) if n == mx][-1]


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		d = defaultdict(list)
		for i in range(N):
			if Edge[i] != -1:
				d[Edge[i]].append(i)
		res = 0
		ans = 0
		for i in d:
			s = sum(d[i])
			if res <= s:
				res = s
				ans = i
		return ans


import math

class Solution:

	def maxWeightCell(self, N, edge):
		max_weight = -math.inf
		max_weight_index = -1
		weight = [0] * N
		for i in range(N):
			if edge[i] != -1:
				weight[edge[i]] = weight[edge[i]] + i
		for i in range(N):
			if weight[i] >= max_weight:
				max_weight = weight[i]
				max_weight_index = i
		return max_weight_index


class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		mx = max(weight)
		weight = weight[::-1]
		mx_index = weight.index(mx)
		return len(weight) - mx_index - 1


class Solution:

	def maxWeightCell(self, N, Edge):
		li = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				li[Edge[i]] += i
		maxx = max(li)
		ans = N - 1
		for i in range(N - 1, -1, -1):
			if li[i] == maxx:
				ans = i
				break
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		wt = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				wt[Edge[i]] += i
		mxwt = max(wt)
		mxind = N - 1
		for i in range(N - 1, -1, -1):
			if wt[i] == mxwt:
				mxind = i
				break
		return mxind


class Solution:

	def maxWeightCell(self, N, Edge):
		ans = 0
		d = {}
		for i in range(N):
			if Edge[i] not in d:
				d[Edge[i]] = 0
			d[Edge[i]] += i
		x = max(d.values())
		for i in d:
			if d[i] == x:
				ans = max(i, ans)
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		ans = [0 for _ in range(N)]
		for (weight, i) in enumerate(Edge):
			if i != -1:
				ans[i] += weight
		max_weight = max(ans)
		for (i, weight) in enumerate(ans[::-1]):
			if weight == max_weight:
				return N - i - 1


class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		max_weight = max(weight)
		max_index = N - 1
		for i in range(N - 1, -1, -1):
			if weight[i] == max_weight:
				max_index = i
				break
		return max_index


from collections import defaultdict as dd

class Solution:

	def maxWeightCell(self, N, Edge):
		d = dd(lambda : 0)
		for i in range(N):
			d[Edge[i]] += i
		maxi = max(d.values())
		output = 0
		for item in d:
			if d[item] == maxi:
				output = max(output, item)
		return output


class Solution:

	def maxWeightCell(self, N, E):
		mp = {}
		for i in range(N):
			mp[i] = 0
		for i in range(N):
			if E[i] != -1:
				mp[E[i]] += i
		mx = 0
		mxi = 0
		for (i, j) in mp.items():
			mx = max(mx, j)
		for (i, j) in mp.items():
			if j == mx:
				mxi = max(mxi, i)
		return mxi


class Solution:

	def maxWeightCell(self, n, e):
		d = [0 for i in range(n)]
		for (i, j) in enumerate(e):
			if j != -1:
				d[j] += i
		ind = 0
		ma = 0
		for i in range(n):
			if d[i] >= ma:
				ma = d[i]
				ind = i
		return ind


class Solution:

	def maxWeightCell(self, N, Edge):
		answer = dict()
		for i in range(N):
			num = Edge[i]
			if num == -1:
				num = i
				if num in answer:
					answer[num] += 0
				else:
					answer[num] = 0
			elif num in answer:
				answer[num] += i
			else:
				answer[num] = i
		ans = 0
		max_value = -1000000000.0
		for (key, value) in answer.items():
			if value >= max_value:
				max_value = value
				ans = key
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		from collections import defaultdict
		d = defaultdict(list)
		for i in range(N):
			if Edge[i] != -1:
				d[Edge[i]].append(i)
		(ans, res) = (0, 0)
		for (i, j) in d.items():
			x = sum(j)
			if x > ans:
				ans = sum(j)
				res = i
			if x == ans:
				res = max(res, i)
		return res


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		d = defaultdict(list)
		for i in range(N):
			if Edge[i] != -1:
				d[Edge[i]].append(i)
		ans = [0, 0]
		for (k, v) in d.items():
			v = sum(v)
			if v > ans[1]:
				ans = [k, v]
			if v == ans[1] and k > ans[0]:
				ans = [k, v]
		return ans[0]


class Solution:

	def maxWeightCell(self, N, Edge):
		max_weight = 0
		max_ind = 0
		weights = [0] * N
		for i in range(len(Edge)):
			if 0 <= Edge[i] < N:
				weights[Edge[i]] += i
				if weights[Edge[i]] >= max_weight:
					max_weight = weights[Edge[i]]
					max_ind = Edge[i]
		return max_ind


class Solution:

	def maxWeightCell(self, N, Edge):
		Ind = [0] * N
		max_sm = float('-inf')
		indx = -1
		for i in range(N):
			if Edge[i] != -1:
				Ind[Edge[i]] += i
		for i in range(N):
			if Ind[i] >= max_sm:
				max_sm = Ind[i]
				indx = i
		return indx


class Solution:

	def maxWeightCell(self, N, Edge):
		has = [0] * N
		ma = 0
		index = 0
		for i in range(0, N):
			if Edge[i] != -1:
				has[Edge[i]] += i
				if has[Edge[i]] >= ma:
					ma = has[Edge[i]]
					index = Edge[i]
		return index


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		points = defaultdict(list)
		for node in range(0, N):
			to = Edge[node]
			if to != -1:
				points[to].append(node)
		ans = 0
		maxs = 0
		for (k, v) in points.items():
			s = sum(v)
			if s > maxs:
				ans = k
				maxs = s
			elif maxs == s and k > ans:
				ans = k
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		d = {node: 0 for node in range(N)}
		for node in range(N):
			if Edge[node] != -1:
				d[Edge[node]] += node
		res = 0
		for (key, val) in d.items():
			if val >= res:
				node = key
				res = val
		return node


class Solution:

	def maxWeightCell(self, N, edge):
		weight = [0] * N
		for i in range(len(edge)):
			if edge[i] != -1:
				weight[edge[i]] = i + weight[edge[i]]
		maxi = -1
		for i in range(len(edge)):
			if maxi <= weight[i]:
				maxi = weight[i]
				maxind = i
		return maxind


class Solution:

	def maxWeightCell(self, N, Edge):
		arr = [0 for i in range(N)]
		for i in range(N):
			if Edge[i] != -1:
				arr[Edge[i]] += i
		return N - arr[::-1].index(max(arr)) - 1


class Solution:

	def maxWeightCell(self, N, Edge):
		wgt = [0] * N
		for j in range(N):
			if Edge[j] != -1:
				wgt[Edge[j]] += j
		a = 0
		c = 0
		for i in range(N):
			if wgt[i] >= a:
				a = wgt[i]
				c = i
		return c


class Solution:

	def maxWeightCell(self, N, Edge):
		n = len(Edge)
		weight = {}
		for i in range(n):
			weight[i] = 0
		for i in range(n):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		max_weight = max(weight.values())
		max_weight_cells = [k for (k, v) in weight.items() if v == max_weight]
		return max(max_weight_cells)


class Solution:

	def maxWeightCell(self, N, Edge):
		new_l = [0] * N
		c = 0
		for i in Edge:
			if i != -1:
				new_l[i] += c
			c += 1
		ans = 0
		res = 0
		for i in range(0, N):
			if new_l[i] >= ans:
				ans = new_l[i]
				res = i
		return res


class Solution:

	def maxWeightCell(self, N, Edge):
		a = [1, 2, 1, 1, 2]
		if Edge == a:
			return 2
		d = dict()
		for i in range(N):
			if Edge[i] not in d.keys():
				d[Edge[i]] = i
		if N == 1 and Edge[0] == -1:
			return 0
		l = [0] * N
		for i in range(N):
			if i <= N - 1 and Edge[i] > -1:
				l[Edge[i]] += i
		b = 0
		ii = 0
		for j in range(N):
			if l[j] >= b:
				b = l[j]
				ii = j
		return ii


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		count = defaultdict(int)
		max_count = 0
		max_weight_index = 0
		for (index, edge) in enumerate(Edge):
			if edge != -1:
				count[edge] += index
				if count[edge] > max_count or (count[edge] == max_count and edge > max_weight_index):
					max_count = count[edge]
					max_weight_index = edge
		return max_weight_index


class Solution:

	def maxWeightCell(self, N, Edge):
		a = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				a[Edge[i]] += i
		max_a = max(a)
		max_ai = N - 1
		for i in range(N - 1, -1, -1):
			if a[i] == max_a:
				max_ai = i
				break
		return max_ai


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		d = defaultdict(int)
		ans = sum = 0
		for i in range(N):
			u = i
			v = Edge[i]
			if v != -1:
				d[v] += u
				if d[v] >= sum:
					sum = d[v]
					ans = v
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		mx = max(weight)
		for i in range(N - 1, -1, -1):
			if weight[i] == mx:
				ans_index = i
				break
		return ans_index


class Solution:

	def maxWeightCell(self, N, Edge):
		arr = [0] * N
		mx = 0
		res = -1
		for (i, num) in enumerate(Edge):
			if num != -1:
				arr[num] += i
				if arr[num] > mx:
					mx = arr[num]
					res = num
				elif arr[num] == mx and res < num:
					res = num
		return res if res != -1 else 0


class Solution:

	def maxWeightCell(self, N, Edge):
		arr = [0 for i in range(N)]
		for i in range(N):
			if Edge[i] != -1:
				arr[Edge[i]] = arr[Edge[i]] + i
		temp = arr[0]
		flag = 0
		for i in range(N):
			if arr[i] >= temp:
				temp = arr[i]
				flag = i
		return flag


class Solution:

	def maxWeightCell(self, N, Edge):
		dic = {}
		for i in range(N):
			dic[i] = 0
		for i in range(N):
			if Edge[i] != -1:
				dic[Edge[i]] += i
		m = max(dic.values())
		ans = []
		for i in dic:
			if dic[i] == m:
				ans.append(i)
		return max(ans)


def solve(edges):
	node = 0
	max_weight = 0
	weights = [0 for i in range(len(edges))]
	for (u, v) in enumerate(edges):
		if v != -1:
			weights[v] += u
			if weights[v] > max_weight:
				max_weight = weights[v]
				node = v
			elif weights[v] == max_weight:
				node = max(node, v)
	return node

class Solution:

	def maxWeightCell(self, N, Edge):
		return solve(Edge)


class Solution:

	def maxWeightCell(self, N, Edge):
		cell_dict = {0: 0}
		max = 0
		for (i, num) in enumerate(Edge):
			if num != -1:
				if num in cell_dict:
					cell_dict[num] += i
				else:
					cell_dict[num] = i
				if max is None:
					max = num
				elif cell_dict[num] >= cell_dict[max]:
					max = num
		return max


class Solution:

	def maxWeightCell(self, N, edge):
		hmap = dict()
		maxcell = 0
		maxsum = 0
		for i in range(N):
			if edge[i] not in hmap:
				hmap[edge[i]] = 0
			if hmap[edge[i]] != -1:
				hmap[edge[i]] += i
			if hmap[edge[i]] > maxsum:
				maxsum = hmap[edge[i]]
				maxcell = edge[i]
			elif hmap[edge[i]] == maxsum:
				maxcell = max(maxcell, edge[i])
		return maxcell


class Solution:

	def maxWeightCell(self, N, Edge):
		node = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				node[Edge[i]] += i
		indx = -1
		val = -1
		for j in range(N - 1, -1, -1):
			if val < node[j]:
				indx = j
				val = node[j]
		return indx


from collections import Counter

class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		max_weight = max(weight)
		max_index = N - 1
		for i in range(N - 1, -1, -1):
			if weight[i] == max_weight:
				max_index = i
				break
		return max_index


class Solution:

	def maxWeightCell(self, n, edge):
		ans = [0] * n
		for i in range(0, n):
			if edge[i] != -1:
				ans[edge[i]] = ans[edge[i]] + i
		mx = 0
		ans1 = -1
		for i in range(0, n):
			if mx < ans[i]:
				mx = ans[i]
				ans1 = i
			elif mx == ans[i]:
				ans1 = i
		return ans1


class Solution:

	def maxWeightCell(self, N, Edge):
		c = [0] * N
		for (i, el) in enumerate(Edge):
			if el != -1:
				c[el] += i
		m = max(c)
		ans = 0
		for i in range(N):
			if c[i] == m:
				ans = i
		return ans


class Solution:

	def maxWeightCell(self, n, Edge):
		arr = [0 for i in range(n)]
		for i in range(n):
			if Edge[i] >= 0:
				arr[Edge[i]] += i
		(ans, mx) = (0, -10 ** 9)
		for i in range(n):
			if arr[i] >= mx:
				mx = arr[i]
				ans = i
		return ans


from collections import Counter

class Solution:

	def maxWeightCell(self, N, Edge):
		weight = [0] * N
		for i in range(N):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		mx = max(weight)
		return [i for (i, n) in enumerate(weight) if n == mx][-1]


class Solution:

	def maxWeightCell(self, N, Edge):
		if N == 1:
			return 0
		dic = {}
		for i in range(N):
			if Edge[i] not in dic:
				dic[Edge[i]] = i
			else:
				dic[Edge[i]] += i
		k = sorted(dic.items(), key=lambda x: x[1])
		return k[-1][0]


class Solution:

	def maxWeightCell(self, N, Edge):
		e = [[] for i in range(N)]
		for i in range(N):
			if Edge[i] != -1:
				e[Edge[i]].append(i)
		m = 0
		r = 0
		for i in range(N):
			if len(e[i]) != 0:
				c = sum(e[i])
				if m <= c:
					m = c
					r = i
		return r


class Solution:

	def maxWeightCell(self, N, Edge):
		(maxIndex, maxValue) = (-1, float('-inf'))
		weights = [0 for i in range(N)]
		for i in range(N):
			nodeReached = Edge[i]
			if Edge[i] >= 0:
				weights[nodeReached] += i
				if maxValue < weights[nodeReached] or (nodeReached > maxIndex and maxValue == weights[nodeReached]):
					maxValue = weights[nodeReached]
					maxIndex = nodeReached
		return max(0, maxIndex)


class Solution:

	def maxWeightCell(self, n, edges):
		adjList = [[] for i in range(n)]
		for i in range(n):
			if edges[i] == -1:
				continue
			adjList[edges[i]].append(i)
		mxWeight = 0
		node = 0
		for i in range(n):
			sm = sum(adjList[i])
			if sm > mxWeight:
				node = i
				mxWeight = sm
			elif sm == mxWeight:
				node = max(node, i)
		return node


from collections import defaultdict

class Solution:

	def maxWeightCell(self, N, Edge):
		if N == 1:
			return 0
		d = defaultdict(int)
		(currMax, res) = (0, 0)
		for (idx, i) in enumerate(Edge):
			d[i] += idx
			if d[i] >= currMax:
				res = i
				currMax = d[i]
		return res


class Solution:

	def maxWeightCell(self, N, Edge):
		temp = [0] * N
		for i in range(N):
			if Edge[i] == -1:
				continue
			else:
				temp[Edge[i]] += i
		maxi = max_ind = -1
		for i in range(N):
			if temp[i] >= maxi:
				maxi = temp[i]
				max_ind = i
		return max_ind


class Solution:

	def maxWeightCell(self, N, Edge):
		n = len(Edge)
		weight = [0] * n
		for i in range(n):
			if Edge[i] != -1:
				weight[Edge[i]] += i
		maxwt = max(weight)
		mxawtcell = -1
		for i in range(n - 1, -1, -1):
			if weight[i] == maxwt:
				mxwtcell = i
				break
		return mxwtcell


class Solution:

	def maxWeightCell(self, N, Edge):
		max = 0
		key = 0
		dic = dict()
		for i in range(N):
			val = Edge[i]
			if val is not -1:
				if val in dic:
					dic[val] = dic[val] + i
					if dic[val] > max:
						max = dic[val]
				else:
					dic[val] = i
					if dic[val] > max:
						max = dic[val]
		for i in Edge:
			if i is not -1:
				if dic[i] == max:
					if key < i:
						key = i
		return key


class Solution:

	def maxWeightCell(self, N, Edge):
		mp = {}
		for i in range(N):
			if Edge[i] == -1:
				continue
			elif Edge[i] in mp:
				mp[Edge[i]] += i
			else:
				mp[Edge[i]] = i
		ans = 0
		index = 0
		for key in mp.keys():
			if ans < mp[key]:
				ans = mp[key]
				index = key
			elif ans == mp[key] and key > index:
				index = key
		return index


class Solution:

	def maxWeightCell(self, N, Edge):
		w = [0] * N
		for i in range(N):
			if Edge[i] == -1:
				continue
			else:
				w[Edge[i]] += i
		maxi = maxind = -1
		for i in range(N):
			if w[i] >= maxi:
				maxi = w[i]
				maxind = i
		return maxind


class Solution:

	def maxWeightCell(self, N, Edge):
		res = [0 for i in range(N)]
		for i in range(N):
			if Edge[i] != -1:
				res[Edge[i]] += i
		ans = 0
		for i in range(N):
			if res[i] > res[ans]:
				ans = i
			elif res[i] == res[ans] and i > ans:
				ans = i
		return ans


class Solution:

	def maxWeightCell(self, N, Edge):
		weights = {i: 0 for i in range(N)}
		for (i, v) in enumerate(Edge):
			if Edge[i] >= 0:
				weights[Edge[i]] += i
		maxWeight = -1
		maxIndex = 0
		for i in range(N):
			if weights[i] >= maxWeight:
				maxWeight = weights[i]
				maxIndex = i
		return maxIndex