Quick Overview

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.

Find maximum island sum and required indices

Company: DocuSign

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

Part 1: Maximum Island Sum

You are given a rectangular m x n integer grid. A cell with value 0 is water, and any non-zero value is land. Two land cells are connected if they share an edge vertically or horizontally. An island is a maximal connected group of land cells. Return the maximum sum of cell values among all islands. If the grid contains no land cells, return 0.

Constraints

  • 0 <= m, n <= 500
  • 0 <= m * n <= 200000
  • -10^6 <= grid[r][c] <= 10^6
  • grid is rectangular when non-empty
  • 0 represents water; any non-zero value represents land

Examples

Input: ([],)

Expected Output: 0

Explanation: The grid is empty, so there are no islands.

Input: ([[0, 0], [0, 0]],)

Expected Output: 0

Explanation: All cells are water.

Hints

  1. Treat every unvisited non-zero cell as the start of a new connected component.
  2. Use DFS or BFS to visit the whole island while accumulating its sum.

Part 2: Maximum Valid Island Sum Ignoring Islands With Negative Cells

You are given a rectangular m x n integer grid. A cell with value 0 is water, and any non-zero value is land. Two land cells are connected if they share an edge vertically or horizontally. An island is a maximal connected group of land cells. An island is valid only if none of its land cells has a negative value. Ignore every island that contains at least one negative cell, and return the maximum sum among the remaining valid islands. If there is no valid island, return 0.

Constraints

  • 0 <= m, n <= 500
  • 0 <= m * n <= 200000
  • -10^6 <= grid[r][c] <= 10^6
  • grid is rectangular when non-empty
  • 0 represents water; any non-zero value represents land
  • A valid island must contain no negative land cells

Examples

Input: ([],)

Expected Output: 0

Explanation: The grid is empty, so there are no valid islands.

Input: ([[1, 2, 0], [0, 3, 0], [4, 0, 5]],)

Expected Output: 6

Explanation: The island containing 1, 2, and 3 has sum 6, greater than the singleton islands 4 and 5.

Hints

  1. You still need to traverse an invalid island completely so its cells are marked visited.
  2. While exploring an island, track both its sum and whether any cell is negative.

Part 3: Maximum Island Sum With Any Cell Index

You are given a rectangular m x n integer grid. A cell with value 0 is water, and any non-zero value is land. Two land cells are connected if they share an edge vertically or horizontally. An island is a maximal connected group of land cells. Return the maximum island sum together with one 0-based coordinate (r, c) of any cell in an island achieving that maximum sum. If there is no land, return (0, (-1, -1)). For deterministic grading, if multiple islands have the same maximum sum, return a cell from the first such island encountered by scanning rows top-to-bottom and columns left-to-right.

Constraints

  • 0 <= m, n <= 500
  • 0 <= m * n <= 200000
  • -10^6 <= grid[r][c] <= 10^6
  • grid is rectangular when non-empty
  • 0 represents water; any non-zero value represents land
  • Returned coordinates must be 0-based

Examples

Input: ([],)

Expected Output: (0, (-1, -1))

Explanation: There are no islands.

Input: ([[0, 5, 0], [0, 5, 0]],)

Expected Output: (10, (0, 1))

Explanation: The vertical island has sum 10, and (0, 1) is a cell in it.

Hints

  1. When starting DFS or BFS for an island, save the starting coordinate as a valid representative cell.
  2. Update the best answer after finishing a whole island, not while you are still exploring it.

Part 4: Maximum Island Sum With Row-Major Last Index Tie-Breaker

You are given a rectangular m x n integer grid. A cell with value 0 is water, and any non-zero value is land. Two land cells are connected if they share an edge vertically or horizontally. An island is a maximal connected group of land cells. For each island, define its last index as the lexicographically largest coordinate (r, c) among its cells, comparing row first and then column. Return the maximum island sum and the last index of the chosen island. If multiple islands tie for maximum sum, choose the island whose last index is largest. If there is no land, return (0, (-1, -1)).

Constraints

  • 0 <= m, n <= 500
  • 0 <= m * n <= 200000
  • -10^6 <= grid[r][c] <= 10^6
  • grid is rectangular when non-empty
  • 0 represents water; any non-zero value represents land
  • The last index of an island is the maximum coordinate by row-major order

Examples

Input: ([],)

Expected Output: (0, (-1, -1))

Explanation: There are no islands.

Input: ([[1, 2, 0], [0, 3, 4]],)

Expected Output: (10, (1, 2))

Explanation: All land cells are connected with sum 10. The last index in that island is (1, 2).

Hints

  1. During DFS or BFS of an island, keep updating the largest coordinate seen in that island.
  2. When comparing islands, compare sums first; only if sums are equal compare their last indices.

Loading coding console...