InMobi interview questions & answers

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

CodingMediumInMobiSoftware Engineer

1. 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.
CodingMediumInMobiSoftware Engineer

2. Reach a Number (LeetCode)

Model answer

The task

Starting at zero on an infinite number line, each move must travel a distance equal to its move number, in either direction. Find the fewest moves needed to land exactly on the target.

Key idea

By symmetry, only the target’s absolute value matters. After n moves, traveling right every time reaches n(n + 1) / 2; reversing directions changes that position by an even amount, so a target is reachable when the difference has even parity.

Approach

  1. Take the absolute value of the target.
  2. Double an upper bound until its triangular sum reaches or exceeds the target.
  3. Binary-search for the smallest move count with a large enough triangular sum.
  4. Increase the count until the sum and target have matching parity.
class Solution:
    def reachNumber(self, target: int) -> int:
        target = abs(target)

        def triangular(n: int) -> int:
            return n * (n + 1) // 2

        # Find an upper bound whose triangular sum reaches the target.
        high = 1
        while triangular(high) < target:
            high *= 2

        # Find the smallest n with triangular(n) >= target.
        low = 0
        while low < high:
            mid = (low + high) // 2
            if triangular(mid) >= target:
                high = mid
            else:
                low = mid + 1

        moves = low

        # Each move reversal changes the final position by an even amount.
        while (triangular(moves) - target) % 2 != 0:
            moves += 1

        return moves

Complexity:

  • Time: O(log target) — doubling and binary search take logarithmic iterations; parity adjustment takes at most two more moves.
  • Space: O(1) — only a fixed number of values are stored.

Common follow-ups

  • How would you produce an actual sequence of directions? Start with all moves right, then reverse moves whose lengths sum to half the excess.
  • What happens for a negative target? The answer is unchanged; reflect every direction.
  • Can you avoid binary search? Yes; increment the move count until the triangular sum reaches the target, then adjust parity.
CodingMediumInMobiSoftware Engineer

3. Capacity To Ship Packages Within D Days (LeetCode)

Model answer

The task

Find the smallest ship capacity that can transport all packages within the given number of days, shipping packages in their original order.

Key idea

If a capacity works, any larger capacity also works, so feasibility is monotonic and can be searched with binary search. For a candidate capacity, greedily load each day as many consecutive packages as fit.

Approach

  1. The capacity must be at least the heaviest package.
  2. The sum of all weights is always sufficient, since it can ship everything in one day.
  3. Binary-search this range.
  4. For each candidate, greedily count how many days are needed, starting a new day when the next package would exceed capacity.
  5. Keep the candidate if the required days are within the limit; otherwise, increase the capacity.
class Solution:
    def shipWithinDays(self, weights: list[int], days: int) -> int:
        def can_ship(capacity: int) -> bool:
            used_days = 1
            load = 0

            for weight in weights:
                if load + weight > capacity:
                    used_days += 1
                    load = 0

                load += weight

            return used_days <= days

        left = max(weights)
        right = sum(weights)

        while left < right:
            capacity = (left + right) // 2

            if can_ship(capacity):
                right = capacity
            else:
                left = capacity + 1

        return left

Complexity:

  • Time: O(n log(sum(weights) - max(weights) + 1)), for the binary search and feasibility checks.
  • Space: O(1), excluding the input.

Common follow-ups

  • What if packages can be reordered? The greedy check changes; for positive weights, packing the largest packages first may help, but the original-order constraint is essential to this solution.
  • Can you return the day-by-day assignments too? Record each greedy day’s packages during a final feasibility pass.
  • What if the number of days is very large? The same bounds and binary search apply; capacities below the heaviest package remain impossible.
CodingMediumInMobiSoftware Engineer

4. Count Number of Nice Subarrays (LeetCode)

Model answer

The task

Count contiguous subarrays that contain exactly k odd numbers. Even values may appear anywhere in those subarrays.

Key idea

Track the number of odd values seen in each prefix. A subarray has exactly k odds when the difference between its ending and starting prefix counts is k.

Approach

  1. Keep a running count of odd values in the prefix ending at the current position.
  2. Store how often each odd-count prefix has occurred.
  3. For the current prefix count odd_count, add the number of earlier prefixes with count odd_count - k.
  4. Record the current prefix count for future positions.
  5. Start with prefix count 0 seen once, to account for subarrays beginning at index 0.
from collections import defaultdict
from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        # Frequencies of odd counts among previously seen prefixes.
        prefix_frequency = defaultdict(int)
        prefix_frequency[0] = 1

        odd_count = 0
        total = 0

        for value in nums:
            if value % 2 == 1:
                odd_count += 1

            # Each earlier prefix with this count makes a subarray
            # containing exactly k odd numbers.
            total += prefix_frequency[odd_count - k]

            prefix_frequency[odd_count] += 1

        return total

Complexity:

  • Time: O(n), where n is the length of nums; each value is processed once.
  • Space: O(n), for the frequencies of prefix odd counts.

Common follow-ups

  • Can this use a sliding window? Yes. Count subarrays with at most k odds, then subtract the count with at most k - 1 odds.
  • What if k is zero? The same prefix-frequency method counts subarrays containing no odd values.
  • Can the frequency map be an array? Yes. Prefix odd counts range from 0 to n, so an array of length n + 1 can store their frequencies.
CodingHardInMobiSoftware Engineer

5. Lexicographically Maximum MEX Array (LeetCode)

Model answer

The task

The title suggests constructing a lexicographically largest sequence of MEX values from an array. The exact allowed operation is unclear; the approach and code below apply if the task is to partition the array into contiguous segments and output each segment’s MEX.

Key idea

For each remaining suffix, its MEX is the largest value any prefix segment can have. Greedily take the shortest prefix containing every smaller value; this emits that MEX while leaving as much of the array as possible for later segments.

Approach

  1. Count the frequencies of values from 0 through n; other values cannot affect a MEX.
  2. Keep a min-heap of values currently absent from the remaining suffix. Its minimum is the suffix MEX.
  3. Scan forward until the segment contains every value smaller than that MEX.
  4. If the MEX is zero, take one element so the scan always makes progress.
  5. Decrease frequencies as elements are consumed, adding values to the heap when their last occurrence is removed.
from collections import Counter
import heapq

def build(nums):
    """Build the maximum-MEX partition for the contiguous-segment formulation."""
    n = len(nums)
    freq = Counter(x for x in nums if 0 <= x <= n)

    # Values absent from the whole array are already missing from the suffix.
    missing = [x for x in range(n + 1) if freq[x] == 0]
    heapq.heapify(missing)

    result = []
    i = 0

    while i < n:
        target = missing[0]
        seen = set()
        start = i

        # A zero MEX needs no values to be seen; consume one element.
        if target == 0:
            i += 1
        else:
            while i < n and len(seen) < target:
                value = nums[i]
                if 0 <= value < target:
                    seen.add(value)
                i += 1

        result.append(target)

        # Update which values are absent from the unconsumed suffix.
        for value in nums[start:i]:
            if 0 <= value <= n:
                freq[value] -= 1
                if freq[value] == 0:
                    heapq.heappush(missing, value)

    return result

Complexity:

  • Time: O(n log n), from heap updates; each array element is consumed once.
  • Space: O(n), for frequencies, the heap, and per-segment tracking.

Common follow-ups

  • What if segments may be non-contiguous? The greedy scan no longer applies; the permitted grouping operation must be specified.
  • What if only the maximum MEX value is needed? Count frequencies and find the smallest absent nonnegative integer.
  • What if the input is streamed? Maintain counts and missing values as elements arrive, but partition decisions may require buffering a segment.
CodingHardInMobiSoftware Engineer

6. Minimum Time to Transport All Individuals (LeetCode)

Model answer

The task

The title suggests finding the least time needed to transport everyone, but the movement rules and time costs are not provided. The exact state and legal moves therefore cannot be determined from the title alone.

Key idea

Model each reachable configuration as a graph node. A state can include a bitmask for which individuals have been transported and any other information needed to determine legal moves; use Dijkstra’s algorithm when move times are nonnegative.

Approach

  1. Encode a complete transport configuration as a hashable state.
  2. Generate only legal moves from the current state, with each move’s time cost.
  3. Run Dijkstra’s algorithm from the initial configuration.
  4. Return the distance when a goal configuration is removed from the priority queue.
  5. Adapt the state representation and move generator to the problem’s actual rules.
from heapq import heappop, heappush
from itertools import count
from typing import Callable, Hashable, Iterable, TypeVar

State = TypeVar("State", bound=Hashable)

def shortest_transport_time(
    start: State,
    is_goal: Callable[[State], bool],
    transitions: Callable[[State], Iterable[tuple[State, int]]],
) -> int | None:
    """Return the minimum cost to reach any goal, or None if unreachable.

    `transitions(state)` yields (next_state, nonnegative_move_time) pairs.
    """
    distances: dict[State, int] = {start: 0}
    serial = count()
    queue: list[tuple[int, int, State]] = [(0, next(serial), start)]

    while queue:
        time_so_far, _, state = heappop(queue)

        # Ignore outdated entries left in the heap.
        if time_so_far != distances[state]:
            continue

        if is_goal(state):
            return time_so_far

        for next_state, move_time in transitions(state):
            if move_time < 0:
                raise ValueError("Dijkstra's algorithm requires nonnegative costs")

            new_time = time_so_far + move_time
            if new_time < distances.get(next_state, float("inf")):
                distances[next_state] = new_time
                heappush(queue, (new_time, next(serial), next_state))

    return None

Complexity:

  • Time: O((V + E) log V), where V and E are the reachable states and legal transitions.
  • Space: O(V) for distances and the priority queue.

Common follow-ups

  • What if all moves have equal cost? Use BFS instead of Dijkstra.
  • What if there are many individuals? Investigate symmetry or other state compression.
  • What if move costs can be negative? Dijkstra is unsuitable; use an algorithm that supports negative edges.
  • How should the state be designed? Include every detail that can affect future legal moves or costs.
CodingHardInMobiSoftware Engineer

7. Frog Position After T Seconds (LeetCode)

Model answer

The task

Find the probability that a frog starting at node 1 is at target after t seconds. Each second, it moves uniformly to an unvisited neighbor, or stays put if none are available.

Key idea

In a tree, each node has a unique path from the root, so its probability is the product of the transition probabilities along that path. If the frog reaches the target before time t, it can still be there only if the target has no unvisited children.

Approach

  1. Build an adjacency list for the tree.
  2. Run BFS from node 1, tracking each node’s parent, probability, and arrival time.
  3. If a state is at the target exactly at time t, return its probability.
  4. If it reaches the target early with no unvisited neighbors, it stays there; otherwise, it must leave and cannot return.
  5. For other nodes, divide their probability evenly among unvisited neighbors.
from collections import deque
from typing import List

class Solution:
    def frogPosition(
        self, n: int, edges: List[List[int]], t: int, target: int
    ) -> float:
        graph = [[] for _ in range(n + 1)]
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        # Each state stores: node, parent, probability, elapsed time.
        queue = deque([(1, 0, 1.0, 0)])

        while queue:
            node, parent, probability, elapsed = queue.popleft()

            if node == target:
                if elapsed == t:
                    return probability

                # With no unvisited neighbors, the frog stays here.
                if len(graph[node]) == (1 if parent else 0):
                    return probability

                # Otherwise it must leave and cannot return in a tree.
                continue

            if elapsed == t:
                continue

            children = [neighbor for neighbor in graph[node]
                        if neighbor != parent]

            if not children:
                continue

            next_probability = probability / len(children)
            for child in children:
                queue.append(
                    (child, node, next_probability, elapsed + 1)
                )

        return 0.0

Complexity:

  • Time: O(n), since each node is processed at most once.
  • Space: O(n), for the adjacency list and BFS queue.

Common follow-ups

  • What if the graph contains cycles? Track visited nodes per path, since a single parent is no longer enough.
  • What if probabilities are not uniform? Multiply by each edge’s transition probability instead of dividing evenly.
  • How can you avoid exploring the whole tree? Search only the target’s root-to-node path and compute the branching probabilities along it.
CodingHardInMobiSoftware Engineer

8. Strange Printer (LeetCode)

Model answer

The task

Find the fewest turns needed to print a string when each turn prints one character across a contiguous interval, possibly overwriting characters printed earlier.

Key idea

Use interval dynamic programming. If two positions contain the same character, one printing turn can cover both, so combine their subproblems rather than paying for a separate turn for each.

Approach

  1. Remove consecutive duplicate characters; they do not change the minimum number of turns.
  2. Let dp[i][j] be the minimum turns to print the substring from i through j.
  3. Start with the option of printing s[i] separately, then printing the rest.
  4. For each later position k matching s[i], consider sharing its printing turn: combine the middle substring with dp[k][j].
  5. Fill intervals from shortest to longest and return the value for the whole string.
class Solution:
    def strangePrinter(self, s: str) -> int:
        # Consecutive copies can be printed in the same turn.
        chars = []
        for ch in s:
            if not chars or chars[-1] != ch:
                chars.append(ch)

        n = len(chars)
        if n == 0:
            return 0

        # dp[i][j] is the minimum turns to print chars[i:j + 1].
        dp = [[0] * n for _ in range(n)]

        for i in range(n - 1, -1, -1):
            dp[i][i] = 1

            for j in range(i + 1, n):
                # Print chars[i] separately, then print the rest.
                dp[i][j] = dp[i + 1][j] + 1

                # If chars[k] matches chars[i], share a turn that prints
                # both positions; print any intervening substring separately.
                for k in range(i + 1, j + 1):
                    if chars[k] == chars[i]:
                        middle = dp[i + 1][k - 1] if k > i + 1 else 0
                        dp[i][j] = min(dp[i][j], middle + dp[k][j])

        return dp[0][n - 1]

Complexity:

  • Time: O(m³), where m is the length after removing consecutive duplicates; each interval checks possible matching positions.
  • Space: O(m²) for the DP table.

Common follow-ups

  • How would you recover a sequence of printing turns? Store which recurrence choice achieves each minimum, then trace those choices.
  • Why remove only consecutive duplicates? They can share a turn immediately; separated equal characters may still be useful to merge through the DP.
  • What happens for an empty string? The answer is zero turns.
CodingHardInMobiSoftware Engineer

9. Critical Connections in a Network (LeetCode)

Model answer

The task

Given an undirected network, find every connection whose removal would make the network less connected. Return those connections as pairs of node IDs.

Key idea

A DFS assigns each node a discovery time and tracks the earliest discovery time reachable from its subtree using tree edges and back edges. A DFS tree edge is a bridge exactly when the child subtree cannot reach the parent or any ancestor through a back edge.

Approach

  1. Build an adjacency list that stores each edge’s unique ID alongside its neighboring node.
  2. Run DFS from each unvisited node, recording discovery times and low-link values.
  3. Skip only the exact edge used to enter a node, so parallel edges are handled correctly.
  4. After visiting a child, mark its tree edge as a bridge if the child’s low-link value exceeds the parent’s discovery time.
  5. Return all marked edges.
from typing import List
import sys

class Solution:
    def criticalConnections(
        self, n: int, connections: List[List[int]]
    ) -> List[List[int]]:
        sys.setrecursionlimit(max(1000, 2 * n + 10))

        # Store edge IDs so parallel edges are distinguished.
        graph = [[] for _ in range(n)]
        for edge_id, (u, v) in enumerate(connections):
            graph[u].append((v, edge_id))
            graph[v].append((u, edge_id))

        discovery = [-1] * n
        low = [0] * n
        bridges = []
        time = 0

        def dfs(node: int, parent_edge: int) -> None:
            nonlocal time
            discovery[node] = low[node] = time
            time += 1

            for neighbor, edge_id in graph[node]:
                if edge_id == parent_edge:
                    continue

                if discovery[neighbor] == -1:
                    dfs(neighbor, edge_id)
                    low[node] = min(low[node], low[neighbor])

                    if low[neighbor] > discovery[node]:
                        bridges.append([node, neighbor])
                else:
                    # A back edge reaches an already discovered node.
                    low[node] = min(low[node], discovery[neighbor])

        for node in range(n):
            if discovery[node] == -1:
                dfs(node, -1)

        return bridges

Complexity:

  • Time: O(V + E), since each node and edge is processed a constant number of times.
  • Space: O(V + E), for the adjacency list and DFS state.

Common follow-ups

  • How would you find articulation points too? Use the same low-link values; apply the articulation-point conditions for DFS roots and non-roots.
  • What if the graph is disconnected? Start DFS from every unvisited node, as in this solution.
  • What if there are parallel edges? Track edge IDs and skip only the exact parent edge, not every edge to the parent.
CodingHardInMobiSoftware Engineer

10. Longest Valid Parentheses (LeetCode)

Model answer

The task

Given a string of opening and closing parentheses, find the length of its longest contiguous substring that forms a correctly balanced sequence.

Key idea

Keep a stack of indices marking positions that cannot belong to the current valid substring. A sentinel index of -1 handles valid substrings that start at the beginning of the string.

Approach

  1. Initialize the stack with -1 and the best length with zero.
  2. For each character, push its index if it is an opening parenthesis.
  3. For a closing parenthesis, pop the top index.
  4. If the stack is empty, push the current index as the new boundary.
  5. Otherwise, the current valid suffix spans from one position after the stack’s top through the current index; update the best length.
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # Indices in the stack mark invalid boundaries.
        stack = [-1]
        longest = 0

        for i, char in enumerate(s):
            if char == "(":
                stack.append(i)
            else:
                stack.pop()

                if not stack:
                    # This closing parenthesis cannot be matched.
                    stack.append(i)
                else:
                    # The segment after the boundary is valid.
                    longest = max(longest, i - stack[-1])

        return longest

Complexity:

  • Time: O(n), where n is the string length; each index is pushed and popped at most once.
  • Space: O(n), for the stack of boundary and opening-parenthesis indices.

Common follow-ups

  • How can this be solved with dynamic programming? Track the longest valid suffix ending at each index, using prior suffix lengths to connect matching pairs.
  • Can the extra space be reduced to O(1)? Scan in both directions, tracking opening and closing counts; reverse the roles on the second scan.
  • What if the input contains multiple bracket types? A stack can match bracket types, but the boundary logic must ensure only correctly nested substrings contribute.
CodingHardInMobiSoftware Engineer

11. Cherry Pickup (LeetCode)

Model answer

The task

Given a square grid with cherries and impassable cells, find the maximum cherries collectable on a trip from the top-left to the bottom-right and back. A cherry can be collected only once, and neither leg may pass through an impassable cell.

Key idea

Treat the two legs as two travelers moving from the top-left to the bottom-right at the same time. After the same number of moves, both travelers are on the same diagonal, so their positions can be tracked by their row indices. Dynamic programming finds the best total cherries while counting a shared cell only once.

Approach

  1. Let dp[r1][r2] be the best total after the current number of moves, with the travelers in rows r1 and r2.
  2. Derive each column from the move count and row.
  3. For each pair of valid, non-thorn cells, consider the four combinations of previous rows.
  4. Add the cherries at both positions, counting them once if the travelers coincide.
  5. Return the best value at the destination, or zero if no valid round trip exists.
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if n == 0 or grid[0][0] == -1:
            return 0

        neg = float("-inf")
        dp = [[neg] * n for _ in range(n)]
        dp[0][0] = grid[0][0]

        # Both travelers make one move per step.
        for steps in range(1, 2 * n - 1):
            curr = [[neg] * n for _ in range(n)]

            # A row is possible only if its corresponding column is in bounds.
            low = max(0, steps - (n - 1))
            high = min(n - 1, steps)

            for r1 in range(low, high + 1):
                c1 = steps - r1
                if grid[r1][c1] == -1:
                    continue

                for r2 in range(low, high + 1):
                    c2 = steps - r2
                    if grid[r2][c2] == -1:
                        continue

                    best_previous = neg
                    # Each traveler either moved right (same row) or down
                    # (previous row was one less).
                    for p1 in (r1, r1 - 1):
                        for p2 in (r2, r2 - 1):
                            if 0 <= p1 < n and 0 <= p2 < n:
                                best_previous = max(
                                    best_previous, dp[p1][p2]
                                )

                    if best_previous == neg:
                        continue

                    cherries = grid[r1][c1]
                    if r1 != r2:  # Different rows mean different cells.
                        cherries += grid[r2][c2]

                    curr[r1][r2] = best_previous + cherries

            dp = curr

        return max(0, dp[n - 1][n - 1])

Complexity:

  • Time: O(n³), for O(n²) row pairs across O(n) move steps.
  • Space: O(n²), for the two rolling DP tables.

Common follow-ups

  • How would you handle larger, sparse grids? Store only reachable states or use sparse maps when few cells are open.
  • What if cells have arbitrary rewards? Add both cell values, still counting a shared cell once.
  • What if there are more than two travelers? Track each traveler’s position, though the state size grows quickly.
CodingHardInMobiSoftware Engineer

12. Trionic Array II (LeetCode)

Model answer

The task

Find the maximum sum of a contiguous part of the array whose values rise strictly, then fall strictly, then rise strictly. Each of the three phases must contain at least one step.

Key idea

Scan once while tracking the best sum of a valid partial pattern ending at the current position: rising, rising-then-falling, or the complete pattern. Each state extends the same phase or transitions from the preceding phase.

Approach

  1. Track the best sum ending at the previous index for each of the three phases.
  2. For a rising adjacent pair, start or extend the rising phase.
  3. For a falling pair, start or extend the falling phase from a rising phase.
  4. For a rising pair after a falling phase, start or extend the complete pattern.
  5. Record the best complete-pattern sum.
from typing import List

class Solution:
    def maxSumTrionic(self, nums: List[int]) -> int:
        # Best sums ending at the previous index in each phase.
        rising = falling = complete = None
        answer = None

        for i in range(1, len(nums)):
            a, b = nums[i - 1], nums[i]

            # Compute new states using only states from the prior index.
            next_rising = next_falling = next_complete = None

            if a < b:
                # Start a rising phase on this edge, or extend one.
                next_rising = a + b
                if rising is not None:
                    next_rising = max(next_rising, rising + b)

                # A falling phase may transition into the final rise.
                if falling is not None:
                    next_complete = falling + b

                # The complete phase can extend its final rise.
                if complete is not None:
                    candidate = complete + b
                    if next_complete is None:
                        next_complete = candidate
                    else:
                        next_complete = max(next_complete, candidate)

            elif a > b:
                # Start falling after a rise, or extend the falling phase.
                if rising is not None:
                    next_falling = rising + b
                if falling is not None:
                    candidate = falling + b
                    if next_falling is None:
                        next_falling = candidate
                    else:
                        next_falling = max(next_falling, candidate)

            rising, falling, complete = (
                next_rising,
                next_falling,
                next_complete,
            )

            if complete is not None:
                answer = complete if answer is None else max(answer, complete)

        # The problem guarantees a valid trionic subarray.
        return answer if answer is not None else 0

Complexity:

  • Time: O(n), with one pass through the array.
  • Space: O(1), using a fixed number of state values.

Common follow-ups

  • How would you return the subarray’s indices? Store the start index and predecessor choice whenever a state improves.
  • How would you count all valid trionic subarrays? Track counts of partial patterns alongside their sum optimizations.
  • What changes if each phase must have a minimum length? Add phase-length state or counters and allow transitions only after the required length.
CodingHardInMobiSoftware Engineer

13. Zuma Game (LeetCode)

Model answer

The task

Find the fewest balls from a limited hand that must be inserted into a board to clear it completely. Return -1 if clearing the board is impossible.

Key idea

Breadth-first search explores states in order of the number of balls used, so the first cleared board gives the minimum. After each insertion, remove any run of three or more matching balls and repeat, since removals may cause further runs to form.

Approach

  1. Count the available balls of each color and represent a state as (board, hand_counts).
  2. Start BFS from the initial board and hand.
  3. For each state, try each available color at every board position.
  4. After insertion, repeatedly remove qualifying runs; enqueue unseen states with one fewer ball of that color.
  5. Return the number of insertions when the board is empty, or -1 if BFS runs out of states.
from collections import Counter, deque
from typing import List, Tuple

class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        colors = "RYBGW"
        initial_counts = tuple(Counter(hand)[color] for color in colors)

        def remove_runs(text: str) -> str:
            # Remove one qualifying run at a time, then rescan for cascades.
            while True:
                i = 0
                removed = False

                while i < len(text):
                    j = i + 1
                    while j < len(text) and text[j] == text[i]:
                        j += 1

                    if j - i >= 3:
                        text = text[:i] + text[j:]
                        removed = True
                        break
                    i = j

                if not removed:
                    return text

        queue = deque([(remove_runs(board), initial_counts, 0)])
        seen = {(queue[0][0], initial_counts)}

        while queue:
            current, counts, steps = queue.popleft()

            if not current:
                return steps

            for color_index, color in enumerate(colors):
                if counts[color_index] == 0:
                    continue

                next_counts = list(counts)
                next_counts[color_index] -= 1
                next_counts = tuple(next_counts)

                for position in range(len(current) + 1):
                    inserted = current[:position] + color + current[position:]
                    next_board = remove_runs(inserted)
                    state = (next_board, next_counts)

                    if state not in seen:
                        seen.add(state)
                        queue.append((next_board, next_counts, steps + 1))

        return -1

Complexity:

  • Time: O(S · C · L³) in this implementation, where S is the number of reachable states, C is the number of colors, and L is the maximum board length. Each state tries every insertion position; run removal may take O(L²).
  • Space: O(S) for the BFS queue and visited states.

Common follow-ups

  • How can the search avoid duplicate insertions? Skip equivalent positions within an identical run; they produce the same board state.
  • Can DFS be used instead? Yes; memoize states and track the best number of balls used, while pruning paths no better than the current answer.
  • How does the approach change with more colors? Use the distinct hand colors as the alphabet; the branching factor grows with the number of available colors.

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