PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

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.

  • Medium
  • DocuSign
  • Coding & Algorithms
  • Software Engineer

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.

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

Expected Output: 18

Explanation: The island containing 4, -1, 7, and 8 has sum 18, which is maximum.

Input: ([[-5, 0, -2], [0, -3, 0]],)

Expected Output: -2

Explanation: All islands are single negative cells; the maximum sum is -2.

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

Expected Output: 6

Explanation: All non-zero cells are connected into one island with sum 1 + (-2) + 3 + 4 = 6.

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.

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

Expected Output: 0

Explanation: The island containing 2, -1, 3, and 4 is ignored because it has a negative cell. The bottom island has sum 10.

Input: ([[-1, 2], [0, 0]],)

Expected Output: 0

Explanation: The only island contains a negative cell, so it is ignored.

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

Expected Output: 2

Explanation: The left island with cells 1 and 1 is valid and has sum 2. Islands containing -2 or -3 are invalid.

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.

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

Expected Output: (12, (0, 3))

Explanation: The maximum island contains 2, 2, 4, and 4 for sum 12. The first encountered cell in that island is (0, 3).

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

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

Explanation: There are two negative singleton islands. The larger sum is -2 at coordinate (1, 0).

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

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

Explanation: Both singleton islands tie with sum 1. The first one in row-major scan is chosen.

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).

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

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

Explanation: Three islands tie with sum 5. Their last indices are (0, 0), (0, 2), and (2, 1), so (2, 1) wins.

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

Expected Output: (4, (2, 2))

Explanation: The island containing the two 2s has maximum sum 4 and last index (2, 2).

Input: ([[-1, 0, -1], [0, -2, 0]],)

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

Explanation: Two islands tie for maximum sum -1. The later last index is (0, 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.
Last updated: Jun 25, 2026

Related Coding Questions

  • Implement a key-value CRUD store - DocuSign (Medium)

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.