Katkat
Back

Find maximum island sum and required indices

DocuSignSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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:

  1. Return the maximum sum of cell values over all islands.
  2. 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.
  3. For the island that achieves the returned maximum sum, also return one index (r, c) of any cell in that island (0-based).
  4. 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.
  5. Describe your algorithm and analyze its time and space complexity.