UiPath interview questions & answers

13 real UiPath interview questions with full model answers — Coding. Drawn from the same verified bank ChannelPulse drills from (13 UiPath questions in total).

CodingMediumUiPathSoftware Engineer

1. Satisfiability of Equality Equations (LeetCode)

Model answer

The task

Given equations involving lowercase single-letter variables and equality or inequality, determine whether all equations can hold simultaneously.

Key idea

First merge variables that must be equal using a disjoint-set union (DSU). Then check every inequality: if its two variables are in the same set, the equations are inconsistent.

Approach

  1. Initialize each letter as its own DSU set.
  2. For every equality, union the sets of its two variables.
  3. For every inequality, compare the roots of its variables.
  4. Return False if any inequality’s variables share a root; otherwise return True.
class Solution:
    def equationsPossible(self, equations: list[str]) -> bool:
        parent = list(range(26))
        rank = [0] * 26

        def find(x: int) -> int:
            # Path compression keeps trees shallow.
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]

        def union(a: int, b: int) -> None:
            root_a = find(a)
            root_b = find(b)

            if root_a == root_b:
                return

            # Union by rank keeps trees shallow.
            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1

        # Apply all required equalities before checking inequalities.
        for equation in equations:
            if equation[1:3] == "==":
                a = ord(equation[0]) - ord("a")
                b = ord(equation[3]) - ord("a")
                union(a, b)

        for equation in equations:
            if equation[1:3] == "!=":
                a = ord(equation[0]) - ord("a")
                b = ord(equation[3]) - ord("a")
                if find(a) == find(b):
                    return False

        return True

Complexity:

  • Time: O(n α(26)), where n is the number of equations and α is the inverse Ackermann function.
  • Space: O(1), since the DSU stores a fixed number of lowercase letters.

Common follow-ups

  • What if variables are arbitrary strings? Map each distinct variable to a DSU index.
  • What if equations arrive incrementally? Add equalities to the DSU as they arrive; an inequality can be checked against the current sets.
  • Why process equalities before inequalities? A later equality can connect variables that an earlier inequality would otherwise appear to permit.
CodingMediumUiPathSoftware Engineer

2. As Far from Land as Possible (LeetCode)

Model answer

The task

Given a binary grid of land and water, find the water cell whose nearest land cell is farthest away. Return that distance, or -1 if the grid has no land or no water.

Key idea

Start a breadth-first search from every land cell at once. This multi-source BFS reaches each water cell in order of its distance from the nearest land, so the greatest recorded distance is the answer.

Approach

  1. Add every land cell to a queue with distance 0.
  2. If there is no land, return -1.
  3. Visit each unvisited neighboring water cell, recording its distance and adding it to the queue.
  4. Track the largest distance assigned.
  5. If no water cell was reached, return -1; otherwise return the largest distance.
from collections import deque
from typing import List

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        distances = [[-1] * cols for _ in range(rows)]
        queue = deque()

        # Treat every land cell as a BFS starting point.
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:
                    distances[r][c] = 0
                    queue.append((r, c))

        if not queue:
            return -1

        farthest = -1
        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        while queue:
            r, c = queue.popleft()

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and distances[nr][nc] == -1
                ):
                    distances[nr][nc] = distances[r][c] + 1
                    farthest = max(farthest, distances[nr][nc])
                    queue.append((nr, nc))

        return farthest

Complexity:

  • Time: O(rows × cols), since each cell is visited at most once.
  • Space: O(rows × cols) for the distance matrix and BFS queue.

Common follow-ups

  • Can the grid be modified to save space? Yes; mark water cells as visited in place instead of keeping a separate distance matrix.
  • Why use multi-source BFS? It computes each cell’s distance to its nearest land, rather than repeatedly searching from each water cell.
  • How would you handle non-uniform movement costs? Use a shortest-path algorithm such as Dijkstra’s algorithm instead of BFS.
CodingMediumUiPathSoftware Engineer

3. Longest Repeating Character Replacement (LeetCode)

Model answer

The task

Find the length of the longest substring that can be made entirely of one repeated character by changing at most k characters.

Key idea

Use a sliding window and track the most frequent character in it. The number of replacements needed is the window length minus that frequency, so shrink the window whenever this exceeds k.

Approach

  1. Keep a frequency count for characters in the current window.
  2. Expand the right edge one character at a time and update the highest frequency seen.
  3. If the window would need more than k replacements, move its left edge forward.
  4. Record the largest window length.

The maximum frequency is intentionally not recomputed when the window shrinks. It may be stale, but this still gives the correct maximum length: the window only stays large when its length is supported by a frequency seen in a previously valid window.

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        counts = {}
        left = 0
        max_frequency = 0
        longest = 0

        for right, char in enumerate(s):
            counts[char] = counts.get(char, 0) + 1
            max_frequency = max(max_frequency, counts[char])

            # Shrink until the window can be made uniform with at most k changes.
            if (right - left + 1) - max_frequency > k:
                counts[s[left]] -= 1
                left += 1

            longest = max(longest, right - left + 1)

        return longest

Complexity:

  • Time: O(n), where n is the string length; each pointer moves at most n times.
  • Space: O(1), since the frequency map has at most 26 entries for uppercase English letters.

Common follow-ups

  • What if the string can contain arbitrary Unicode characters? Use a dictionary for counts; the space then depends on the number of distinct characters.
  • Can the method return the substring as well as its length? Store the best window’s start and end indices whenever the best length increases.
  • What if replacements have different costs? Track the minimum cost to make the window uniform and shrink while that cost exceeds the budget.
CodingMediumUiPathSoftware Engineer

4. Subsets II (LeetCode)

Model answer

The task

Given an integer array that may contain duplicates, return every distinct subset. The subsets can be returned in any order.

Key idea

Sort the array so equal values are adjacent. During backtracking, skip an equal value when it appears at the same decision depth; this avoids generating duplicate subsets while still allowing repeated values in a subset.

Approach

  1. Sort the input array.
  2. Start a depth-first search with an empty current subset.
  3. Add a copy of the current subset to the results at every search call.
  4. Try each remaining array element as the next choice.
  5. Skip an element if it equals the previous one at this depth, then recurse from the next index.
  6. Remove the chosen element after returning from recursion.
from typing import List

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result: List[List[int]] = []
        current: List[int] = []

        def backtrack(start: int) -> None:
            # Every node in the search tree represents a valid subset.
            result.append(current.copy())

            for i in range(start, len(nums)):
                # Avoid choosing the same value twice at this search depth.
                if i > start and nums[i] == nums[i - 1]:
                    continue

                current.append(nums[i])
                backtrack(i + 1)
                current.pop()

        backtrack(0)
        return result

Complexity:

  • Time: O(n · 2ⁿ), since there can be up to 2ⁿ subsets and copying each takes up to O(n).
  • Space: O(n) auxiliary space for recursion and the current subset, excluding the returned results.

Common follow-ups

  • What if the input is already sorted? The initial sort can be omitted.
  • How can duplicates be handled without sorting? Track chosen values at each recursion depth using a set.
  • Can the subsets be generated iteratively? Extend existing subsets for each value, skipping extensions that would duplicate subsets at the current step.
CodingMediumUiPathSoftware Engineer

5. Integer to Roman (LeetCode)

Model answer

The task

Convert a positive integer into its standard Roman numeral representation, using subtractive forms such as IV and CM where appropriate.

Key idea

Process Roman numeral values from largest to smallest, including the six subtractive combinations as single entries. At each value, emit it as many times as possible, then continue with the remainder.

Approach

  1. List the values and their Roman numeral symbols in descending order.
  2. For each value, use integer division to determine how many times it fits in the remaining number.
  3. Append that many copies of its symbol.
  4. Subtract the represented amount and continue.
  5. Join the symbols to form the result.
class Solution:
    def intToRoman(self, num: int) -> str:
        # Include subtractive pairs alongside the ordinary symbols.
        values = [
            (1000, "M"),
            (900, "CM"),
            (500, "D"),
            (400, "CD"),
            (100, "C"),
            (90, "XC"),
            (50, "L"),
            (40, "XL"),
            (10, "X"),
            (9, "IX"),
            (5, "V"),
            (4, "IV"),
            (1, "I"),
        ]

        result = []

        for value, symbol in values:
            count, num = divmod(num, value)
            result.append(symbol * count)

        return "".join(result)

Complexity:

  • Time: O(1) for the standard bounded integer range; each of the fixed 13 values is checked.
  • Space: O(1) auxiliary space; the result uses O(1) space for the bounded output.

Common follow-ups

  • How would you convert a Roman numeral back to an integer? Scan symbols and subtract a value when it is less than the next symbol.
  • What if the input can exceed the standard Roman numeral range? Define an extension convention, such as overlines for thousands, before adapting the mapping.
  • How would you validate a Roman numeral string? Parse it, convert it to an integer, then convert that integer back and compare with the original.
CodingMediumUiPathSoftware Engineer

6. Min Stack (LeetCode)

Model answer

The task

Design a stack that supports pushing and removing values, inspecting the top value, and retrieving the minimum value currently stored. Each operation should take constant time.

Key idea

Alongside each value, store the minimum seen at that point in the stack. The top entry then contains enough information to answer a minimum query without scanning the stack.

Approach

  1. Keep a list of (value, minimum_so_far) pairs.
  2. On push, compare the new value with the current minimum and store the smaller one.
  3. On pop, remove the top pair.
  4. Return the value or minimum from the top pair for top and getMin.
class MinStack:
    def __init__(self):
        # Each entry is (value, minimum among entries up to this one).
        self.stack = []

    def push(self, val: int) -> None:
        current_min = val
        if self.stack:
            current_min = min(val, self.stack[-1][1])
        self.stack.append((val, current_min))

    def pop(self) -> None:
        self.stack.pop()

    def top(self) -> int:
        return self.stack[-1][0]

    def getMin(self) -> int:
        return self.stack[-1][1]

Complexity:

  • Time: O(1) per operation; each method accesses or updates only the top entry.
  • Space: O(n); each stack entry stores its value and the minimum so far.

Common follow-ups

  • Can you reduce the extra space? Store only values and keep a second stack of minimums, pushing a minimum when it is no greater than the current one.
  • How should duplicate minimums be handled? Track duplicates in the minimum stack too, so popping one leaves the other available.
  • What if the stack can be empty when queried? Define the API’s empty-stack behavior, such as raising an exception or returning a sentinel.
CodingMediumUiPathSoftware Engineer

7. Sorting Three Groups (LeetCode)

Model answer

The task

Given an array containing only 1, 2, and 3, find the fewest elements that must be changed so the array becomes non-decreasing.

Key idea

Keep the largest possible subsequence that is already non-decreasing; change every other element. Track the longest such subsequence ending in each of the three values.

Approach

  1. Keep dp[v] as the longest valid subsequence ending in value v.
  2. Process the array from left to right.
  3. For a value v, extend the best subsequence ending in any value at most v.
  4. The answer is the array length minus the longest subsequence found.
class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        # dp[i] is the longest non-decreasing subsequence
        # seen so far that ends with value i + 1.
        dp = [0, 0, 0]

        for value in nums:
            # A subsequence ending in value can extend one
            # ending in any value no greater than value.
            best_prefix = max(dp[:value])
            index = value - 1
            dp[index] = max(dp[index], best_prefix + 1)

        kept = max(dp)
        return len(nums) - kept

Complexity:

  • Time: O(n), processing each element with constant work.
  • Space: O(1), storing state for only three values.

Common follow-ups

  • How would you handle more than three ordered values? Use a longest non-decreasing subsequence algorithm, typically with binary search.
  • What if the target sequence must be strictly increasing? Track a longest increasing subsequence instead.
  • Can the original array be changed in place? Yes; replace each element outside a chosen longest valid subsequence with values that preserve non-decreasing order.
CodingHardUiPathSoftware Engineer

8. Burst Balloons (LeetCode)

Model answer

The task

Choose an order for bursting all balloons, where each burst earns the product of the balloon and its current neighbors. Return the maximum total score.

Key idea

The best choice to consider for a range is the balloon burst last, not first. At that point its neighbors are the fixed boundaries of the range, and the balloons on either side can be optimized independently.

Approach

  1. Add a 1 at each end of the balloon values to represent the boundaries.
  2. Let dp[left][right] be the best score from bursting all balloons in that inclusive range.
  3. Process ranges from shortest to longest so their smaller subranges are already computed.
  4. For each possible last balloon, add the scores of the two remaining subranges and the coins from bursting that balloon last.
  5. Return the score for the range containing all original balloons.
from typing import List

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        if not nums:
            return 0

        values = [1] + nums + [1]
        n = len(nums)
        dp = [[0] * (n + 2) for _ in range(n + 2)]

        # Build solutions for increasingly large intervals.
        for length in range(1, n + 1):
            for left in range(1, n - length + 2):
                right = left + length - 1

                # Choose which balloon in this interval is burst last.
                for last in range(left, right + 1):
                    coins = (
                        dp[left][last - 1]
                        + dp[last + 1][right]
                        + values[left - 1] * values[last] * values[right + 1]
                    )
                    dp[left][right] = max(dp[left][right], coins)

        return dp[1][n]

Complexity:

  • Time: O(n³), checking each possible last balloon for every interval.
  • Space: O(n²), for the interval DP table.

Common follow-ups

  • How can you recover an optimal bursting order? Store the best last choice for each interval, then recursively construct the orders for its two subintervals and burst last last.
  • Can this be improved to O(n²)? The standard interval-DP solution checks every possible final balloon; it does not generally reduce to quadratic time.
  • What if the input is empty? The maximum score is 0, handled directly at the start of the method.
CodingHardUiPathSoftware Engineer

9. Binary Tree Cameras (LeetCode)

Model answer

The task

Place the fewest cameras in a binary tree so every node is watched. A camera watches its own node, its parent, and its immediate children.

Key idea

A postorder traversal lets each node decide based on whether its children are uncovered, have cameras, or are already covered. Place a camera only when a child is uncovered; if the root remains uncovered, add one there.

Approach

  1. Traverse the tree in postorder so child states are known before processing a node.
  2. Return one of three states: NEEDS_CAMERA, HAS_CAMERA, or COVERED.
  3. Treat a missing child as covered.
  4. If either child needs a camera, place one at the current node.
  5. Otherwise, if either child has a camera, the current node is covered; if neither does, it needs a camera.
  6. After traversal, place a camera at the root if it still needs one.
# TreeNode is assumed to provide left and right attributes.

class Solution:
    def minCameraCover(self, root):
        NEEDS_CAMERA = 0
        HAS_CAMERA = 1
        COVERED = 2

        cameras = 0

        def dfs(node):
            nonlocal cameras

            # A missing child is already covered.
            if node is None:
                return COVERED

            left_state = dfs(node.left)
            right_state = dfs(node.right)

            # An uncovered child must be watched by a camera here.
            if left_state == NEEDS_CAMERA or right_state == NEEDS_CAMERA:
                cameras += 1
                return HAS_CAMERA

            # A child camera also watches this node.
            if left_state == HAS_CAMERA or right_state == HAS_CAMERA:
                return COVERED

            # No child has a camera, so this node may need one above.
            return NEEDS_CAMERA

        if dfs(root) == NEEDS_CAMERA:
            cameras += 1

        return cameras

Complexity:

  • Time: O(n), since each node is visited once.
  • Space: O(h), for the recursion stack, where h is the tree height.

Common follow-ups

  • How can this avoid recursion-depth limits? Use an explicit stack to perform postorder traversal.
  • What if cameras have different costs? Use tree DP with minimum-cost states instead of a single camera count.
  • What if cameras can watch beyond immediate neighbors? Redefine the states to track the required coverage distance.
CodingHardUiPathSoftware Engineer

10. Russian Doll Envelopes (LeetCode)

Model answer

The task

Given envelope dimensions, find the largest chain in which each envelope fits strictly inside the next in both width and height.

Key idea

Sort by width ascending, breaking ties by height descending. Then a strictly increasing subsequence of heights gives a valid nesting chain: the descending tie-break prevents equal-width envelopes from being used together.

Use the patience-sorting method to compute the longest increasing subsequence (LIS) length in \(O(n \log n)\).

Approach

  1. Sort envelopes by (width, -height).
  2. Keep a list of the smallest possible ending heights for increasing subsequences of each length.
  3. For each height, use binary search to find its insertion position.
  4. Replace the value there, or append if the height extends the longest subsequence.
  5. Return the list’s length.
from bisect import bisect_left
from typing import List

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        # Descending height for equal widths prevents nesting those envelopes.
        ordered = sorted(envelopes, key=lambda envelope: (envelope[0], -envelope[1]))

        # tails[k] is the smallest ending height for an increasing subsequence
        # of length k + 1 seen so far.
        tails: List[int] = []

        for _, height in ordered:
            position = bisect_left(tails, height)

            if position == len(tails):
                tails.append(height)
            else:
                tails[position] = height

        return len(tails)

Complexity:

  • Time: O(n log n), from sorting and binary searches for all envelopes.
  • Space: O(n), for the sorted envelopes and the LIS tails.

Common follow-ups

  • How would you return an actual nesting chain? Track predecessor indices and the envelope index that last extended each subsequence length.
  • How would you count the maximum-length chains? Use a coordinate-compressed segment tree or Fenwick tree storing both best length and number of ways.
  • What if equal widths could nest? Then the tie-breaking rule changes; the strict-fit requirement is what makes descending heights necessary here.
CodingHardUiPathSoftware Engineer

11. Collect Coins in a Tree (LeetCode)

Model answer

The task

Given a tree and a coin indicator for each node, find the minimum number of edge traversals needed to collect every coin. A node’s coin can be collected by visiting a node within distance two.

Key idea

First remove leaf branches that contain no coins; they are unnecessary. Then remove two layers of leaves: those coins can be collected from nearby without traversing the outer layers. Every edge left in the tree must be traversed in both directions.

Approach

  1. Build an adjacency list and record each node’s degree.
  2. Queue all coinless leaves and repeatedly remove them, adding newly exposed coinless leaves.
  3. Queue the leaves of the remaining tree.
  4. Remove two full layers of those leaves.
  5. Count the remaining edges and return twice that count.
from collections import deque
from typing import List

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(coins)
        graph = [[] for _ in range(n)]
        degree = [0] * n

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
            degree[a] += 1
            degree[b] += 1

        # Remove branches that contain no coins.
        queue = deque(
            node for node in range(n)
            if degree[node] == 1 and coins[node] == 0
        )

        while queue:
            node = queue.popleft()
            if degree[node] == 0:
                continue

            degree[node] = 0
            for neighbor in graph[node]:
                if degree[neighbor] == 0:
                    continue
                degree[neighbor] -= 1
                if degree[neighbor] == 1 and coins[neighbor] == 0:
                    queue.append(neighbor)

        # Coins in the outer two layers can be collected from the core.
        queue = deque(node for node in range(n) if degree[node] == 1)

        for _ in range(2):
            layer_size = len(queue)
            for _ in range(layer_size):
                node = queue.popleft()
                if degree[node] != 1:
                    continue

                degree[node] = 0
                for neighbor in graph[node]:
                    if degree[neighbor] == 0:
                        continue
                    degree[neighbor] -= 1
                    if degree[neighbor] == 1:
                        queue.append(neighbor)

        remaining_edges = sum(degree) // 2
        return 2 * remaining_edges

Complexity:

  • Time: O(n), since each node and edge is processed a constant number of times.
  • Space: O(n) for the adjacency list, degrees, and queues.

Common follow-ups

  • What if collection distance changes? Remove that many leaf layers after pruning coinless branches.
  • What if the tree is very large? The algorithm is already iterative and linear, avoiding recursion depth issues.
  • What if the route need not return to its starting point? Revisit whether the final remaining tree can be covered by a path, potentially saving a diameter’s worth of traversal.
CodingHardUiPathSoftware Engineer

12. Escape a Large Maze (LeetCode)

Model answer

The task

Given a huge square grid, a small set of blocked cells, and two unblocked positions, determine whether a path connects them without crossing blocked cells.

Key idea

A small number of blocked cells cannot enclose an arbitrarily large region. With b blocked cells, the largest enclosed area is at most b * (b - 1) // 2. A search that visits more cells than this bound has escaped any possible enclosure.

Check reachability from both ends: the source must not be trapped, and the target must not be trapped.

Approach

  1. Store blocked coordinates in a set for constant-time membership checks.
  2. Compute the maximum possible enclosed area from the number of blocked cells.
  3. Run a bounded BFS from the source toward the target.
  4. Repeat from the target toward the source.
  5. Return true only if both searches reach the opposite position or explore beyond the enclosure bound.
from collections import deque
from typing import List

class Solution:
    def isEscapePossible(
        self,
        blocked: List[List[int]],
        source: List[int],
        target: List[int],
    ) -> bool:
        grid_size = 1_000_000
        blocked_set = {tuple(cell) for cell in blocked}
        source_pos = tuple(source)
        target_pos = tuple(target)

        if source_pos in blocked_set or target_pos in blocked_set:
            return False
        if source_pos == target_pos:
            return True

        # More visited cells than this means the search escaped any enclosure.
        limit = len(blocked) * (len(blocked) - 1) // 2

        def can_escape(start: tuple, goal: tuple) -> bool:
            queue = deque([start])
            visited = {start}

            while queue and len(visited) <= limit:
                x, y = queue.popleft()

                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    next_pos = (nx, ny)

                    if next_pos == goal:
                        return True

                    if (
                        0 <= nx < grid_size
                        and 0 <= ny < grid_size
                        and next_pos not in blocked_set
                        and next_pos not in visited
                    ):
                        visited.add(next_pos)
                        queue.append(next_pos)

            return len(visited) > limit

        return (
            can_escape(source_pos, target_pos)
            and can_escape(target_pos, source_pos)
        )

Complexity:

  • Time: O(B²), where B is the number of blocked cells; each search explores at most about B² cells.
  • Space: O(B²) for the BFS queue and visited set.

Common follow-ups

  • Why search from both positions? The source might escape while the target is enclosed, or vice versa.
  • What if there are no blocked cells? The bound is zero, so each search immediately confirms it is not enclosed.
  • Could bidirectional BFS help? It can reduce work when searching toward a known target, but the bounded-enclosure checks are still needed.
CodingHardUiPathSoftware Engineer

13. Making A Large Island (LeetCode)

Model answer

The task

Given a binary square grid, you may change at most one water cell into land. Return the largest island size achievable, where an island consists of horizontally or vertically connected land cells.

Key idea

First label each existing island with a unique ID and record its area. Flipping a water cell joins the distinct islands directly beside it, so its resulting area is one plus the sum of their areas.

Approach

  1. Scan the grid and iteratively traverse each unvisited land component.
  2. Replace its cells with a unique ID and store the component’s area.
  3. Track the largest existing island, which also covers the option of making no change.
  4. For each water cell, collect the IDs of its neighboring islands and sum their areas plus one.
  5. Return the largest area found. If the grid has no water, the existing island already covers the entire grid.
from typing import List

class Solution:
    def largestIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        areas = {}
        island_id = 2  # Keep component IDs distinct from 0 and 1.
        largest = 0
        directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

        # Label each land component and record its area.
        for row in range(n):
            for col in range(n):
                if grid[row][col] != 1:
                    continue

                stack = [(row, col)]
                grid[row][col] = island_id
                area = 0

                while stack:
                    r, c = stack.pop()
                    area += 1

                    for dr, dc in directions:
                        nr, nc = r + dr, c + dc
                        if (
                            0 <= nr < n
                            and 0 <= nc < n
                            and grid[nr][nc] == 1
                        ):
                            grid[nr][nc] = island_id
                            stack.append((nr, nc))

                areas[island_id] = area
                largest = max(largest, area)
                island_id += 1

        # Try turning each water cell into land.
        for row in range(n):
            for col in range(n):
                if grid[row][col] != 0:
                    continue

                adjacent_ids = set()
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < n and 0 <= nc < n:
                        if grid[nr][nc] >= 2:
                            adjacent_ids.add(grid[nr][nc])

                merged_area = 1 + sum(areas[i] for i in adjacent_ids)
                largest = max(largest, merged_area)

        return largest

Complexity:

  • Time: O(n²), since each cell is visited a constant number of times.
  • Space: O(n²) in the worst case for the traversal stack and component areas.

Common follow-ups

  • What if the grid is all land? The initial largest-area value is already n².
  • Why use a set of neighboring IDs? A component can touch the water cell from multiple sides and should only be counted once.
  • Can this avoid modifying the input? Keep component labels in a separate matrix instead.
  • What if cells connect diagonally too? Add the four diagonal directions to the neighbor checks and component traversal.

Practice these out loud, don't memorise them

Reading an answer is not the same as being able to give one under pressure. ChannelPulse plays the interviewer, asks the follow-ups, and scores each answer with feedback and a model answer so you can hear the gap between what you said and what lands.

Get ChannelPulse Browse all questions