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 the 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 the 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.
Examples:
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.Input: N = 1, Edge[] = {-1}
Output: 0
Explanation: weight of 0th cell is 0.
There is only one cell so cell 0 has maximum weight.
Naive Approach: The basic way to solve the problem is as follows:
Run a loop from 0 to N-1 and check the weight for every cell by traversing the whole Edge[] array.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: We can optimize the above approach by using the below steps.
- As we know that the range of the cells is from 0 to N-1.
- So we can use extra space of O(N) for optimizing our solution
- To do this initially we will set all the values to zero. Let’s understand this with the above example
- Let’s take an extra array temp of size N and set all values to zero:- temp {0, 0, 0, 0}
- Now the given array is {2, 0, -1, 2}.
- Traverse the array from the beginning.
- At first, we will get 2 at index 0. It means we can move from 0->2 and the weight on cell 2 is 0. So update entry of 2 in the temp array by adding the weight into this and as weight is 0 so the temp will remain the same that is {0, 0, 0, 0}
- After this we will go to index 1 which is 0 it means we can move from 1 to 0 and the weight on 0 will increase by 1 that is temp {1, 0, 0, 0}
- After this, we will go to index 2 which is -1 that is we can not go from 2 to anywhere.
- In the end, we will go to index 3 which is 2 it means there is a path between 3->2 and the weight on 2 will increase by 3 is temp {1, 0, 3, 0}
- In the end, we will find the index with the maximum value.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Function to find Max Weight Cellint maxWeightCell(int N, vector<int> Edge){ // Initializing temp with 0 vector<int> temp(N, 0); // Traversing the Edge array for (int i = 0; i < N; i++) { // Checking if the value is not // equal to -1 if (Edge[i] != -1) { // Adding weight to the // destination cell temp[Edge[i]] += i; } } // Getting the index with // maximum value int ans = max_element(temp.begin(), temp.end()) - temp.begin(); return ans;}// Drivers codeint main(){ // Size of Edge int N = 4; vector<int> Edge{ 2, 0, -1, 2 }; // Printing value cout << maxWeightCell(N, Edge) << endl; return 0;} |
Java
// Java code for the above approach:import java.util.*;class GFG { // Function to find Max Weight Cell public static int maxWeightCell(int N, List<Integer> Edge) { // Initializing temp with 0 int[] temp = new int[N]; // Traversing the Edge array for (int i = 0; i < N; i++) { // Checking if the value is not // equal to -1 if (Edge.get(i) != -1) { // Adding weight to the // destination cell temp[Edge.get(i)] += i; } } // Getting the index with // maximum value int ans = 0; int max = Integer.MIN_VALUE; for (int i = 0; i < N; i++) { if (temp[i] > max) { ans = i; max = temp[i]; } } return ans; } // Drivers code public static void main(String[] args) { // Size of Edge int N = 4; List<Integer> Edge = Arrays.asList(2, 0, -1, 2); // Printing value System.out.println(maxWeightCell(N, Edge)); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code for the above approach:# Function to find Max Weight Celldef maxWeightCell(N, Edge): # Initializing temp with 0 temp = [0] * N # Traversing the Edge array for i in range(N): # Checking if the value is not # equal to -1 if Edge[i] != -1: # Adding weight to the # destination cell temp[Edge[i]] += i # Getting the index with # maximum value ans = 0 max_val = float('-inf') for i in range(N): if temp[i] > max_val: ans = i max_val = temp[i] return ans# Size of EdgeN = 4Edge = [2, 0, -1, 2]# Function callprint(maxWeightCell(N, Edge))# This Code is Contributed by sankar. |
C#
// C# code for the above approachusing System;using System.Collections.Generic;public class GFG { // Function to find Max Weight Cell static int maxWeightCell(int N, List<int> Edge) { // Initializing temp with 0 int[] temp = new int[N]; // Traversing the Edge array for (int i = 0; i < N; i++) { // Checking if the value is not // equal to -1 if (Edge[i] != -1) { // Adding weight to the // destination cell temp[Edge[i]] += i; } } // Getting the index with // maximum value int ans = 0; int max = int.MinValue; for (int i = 0; i < N; i++) { if (temp[i] > max) { ans = i; max = temp[i]; } } return ans; } static public void Main() { // Code // Size of Edge int N = 4; List<int> Edge = new List<int>{ 2, 0, -1, 2 }; // Printing value Console.WriteLine(maxWeightCell(N, Edge)); }}// This code is contributed by karthik |
Javascript
// JS Codelet N = 4;let Edge = [2, 0, -1, 2];function maxWeightCell(N, Edge) { let temp = Array(N).fill(0); for (let i = 0; i < N; i++) { if (Edge[i] != -1) { temp[Edge[i]] += i; } } let ans = temp.indexOf(Math.max(...temp)); return ans;}console.log(maxWeightCell(N, Edge)); |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
