Find maximum island sum and required indices

Q: Find maximum island sum and required indices

This question evaluates grid-based graph traversal and connected-component aggregation skills, including handling positive and negative cell values, tie-breaking by row-major indices, and computing maximum component sums.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given an m×n integer grid where 0 denotes water and any non-zero value denotes land. Two land cells are connected if they share an edge (4-directional). An island is a maximal set of connected land cells. Tasks:

Return the maximum sum of cell values over all islands.
Variant A: An island is considered valid only if all its cells are non-negative; any island containing at least one negative value must be ignored. Recompute and return the maximum sum under this rule.
For the island that achieves the returned maximum sum, also return one index (r, c) of any cell in that island (0-based).
Variant B: Instead of any index, return the last index of that island in row-major order (the lexicographically largest pair (r, c) by r first, then c). If multiple islands tie on sum, choose the island whose last index is largest under the same order.
Describe your algorithm and analyze its time and space complexity.

Find maximum island sum and required indices

Overview

Comments (0)