PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
Given an N \times M grid, filled with integers, find the largest connected area (side adjacent elements) filled with same numbers. If there are more than one such connected areas, find the one filled with the minimum number. Print the Value and Area of that region.
QUICK EXPLANATION:
Key to AC: Run a Depth First Search on the elements of the grid to find the various connected components, and then just find the one with maximum elements connected, if there are more than one such areas, find the one with minimum number written on them.
EXPLANATION:
To solve this problem, one needs to know about what connected components are. And the best approach would be a DFS through the grid to find all connected components in this grid (connected in a sense that same elements which are side adjacent are parts of one single component). To find the region with the maximum number of elements is just an added task here, we just need to keep a track of it, that’s it. Moreover, finding the region with largest area (number of elements) and having the least possible element value if there exist more than one regions with the maximum area, is another added task.
Almost all the solutions that achieved only 30 points (sub-task 1), either missed on some edge cases, failed to keep track of optimal region correctly, or were unable to control recursion for their recursive DFS implementation (improper user of the visited nodes).
This problem can easily be solved in O(N \times M) time with O(N \times M) auxiliary space for keeping a track of the visited nodes, just to control excessive recursion (for recursive approaches) or excessive searching (for iterative approaches).
This problem is very similar to the Number of Islands problem, the difference here is just that here we need to keep a track of the area and value involved for a particular region found. Also, a similar problem is the Largest Region problem.
COMPLEXITY:
O(N \times M) time with O(N \times M) auxiliary space.
SOLUTION:
Setter’s Solution [Plain Text]
RELATED PROBLEMS:
Two Flowers (This one is way more complex because it involves DSU, as we can have at most two different numbers in a region, a very good problem to practice).
Feel free to share your approach. If you have any queries, they are always welcome.