MEX -- Interview Preparation¶

Junior Questions (1-15)¶

Middle Questions (16-30)¶

Senior Questions (31-40)¶

Professional Questions (41-50)¶

Coding Challenge -- Prefix MEX in O(n)¶

Given an array a[0..n-1] of non-negative integers, return an array m[0..n-1] where m[i] = MEX(a[0..i]).

Time: O(n) total. Space: O(n).

Test: - [2, 0, 1, 3] -> [0, 0, 3, 4] - [1, 2, 3] -> [0, 0, 0] - [0] -> [1] - [] -> [] - [0, 0, 0, 1, 2] -> [1, 1, 1, 2, 3]

The trick: keep a single mex pointer and a bucket. After each insert, advance the pointer while the bucket bit is set. Total pointer advances across all inserts is bounded by n (the pointer is monotone non-decreasing under inserts and bounded by n), so total work is O(n).

Go¶

package main

import "fmt"

// PrefixMEX returns m where m[i] = MEX(a[0..i]).
// Time: O(n) amortized. Space: O(n).
func PrefixMEX(a []int) []int {
    n := len(a)
    m := make([]int, n)
    seen := make([]bool, n+1)
    mex := 0
    for i, v := range a {
        if v >= 0 && v <= n {
            seen[v] = true
        }
        for mex <= n && seen[mex] {
            mex++
        }
        m[i] = mex
    }
    return m
}

func main() {
    tests := [][]int{
        {2, 0, 1, 3},
        {1, 2, 3},
        {0},
        {},
        {0, 0, 0, 1, 2},
    }
    for _, t := range tests {
        fmt.Printf("input=%v mex=%v\n", t, PrefixMEX(t))
    }
}

Java¶

import java.util.Arrays;

public class PrefixMEX {
    /**
     * Returns m where m[i] = MEX(a[0..i]).
     * The mex pointer is monotone non-decreasing under inserts, so total
     * advances are bounded by n -- O(n) total work, O(1) amortized per index.
     *
     * Time: O(n). Space: O(n).
     */
    public static int[] prefixMex(int[] a) {
        int n = a.length;
        int[] m = new int[n];
        boolean[] seen = new boolean[n + 1];
        int mex = 0;
        for (int i = 0; i < n; i++) {
            int v = a[i];
            if (v >= 0 && v <= n) seen[v] = true;
            while (mex <= n && seen[mex]) mex++;
            m[i] = mex;
        }
        return m;
    }

    public static void main(String[] args) {
        int[][] tests = {
            {2, 0, 1, 3},
            {1, 2, 3},
            {0},
            {},
            {0, 0, 0, 1, 2},
        };
        for (int[] t : tests) {
            System.out.printf("input=%s mex=%s%n",
                Arrays.toString(t), Arrays.toString(prefixMex(t)));
        }
    }
}

Python¶

"""Prefix MEX in O(n) total time."""

from typing import List


def prefix_mex(a: List[int]) -> List[int]:
    """
    Return m where m[i] = MEX(a[0..i]).

    Single bucket of size n+1 + a monotone mex pointer. The pointer is
    advanced lazily: only the work needed to confirm the current value's
    presence is paid. Total pointer advances across all inserts <= n,
    giving O(n) total work.

    Time: O(n). Space: O(n).
    """
    n = len(a)
    m = [0] * n
    seen = [False] * (n + 1)
    mex = 0
    for i, v in enumerate(a):
        if 0 <= v <= n:
            seen[v] = True
        while mex <= n and seen[mex]:
            mex += 1
        m[i] = mex
    return m


if __name__ == "__main__":
    tests = [
        [2, 0, 1, 3],
        [1, 2, 3],
        [0],
        [],
        [0, 0, 0, 1, 2],
    ]
    for t in tests:
        print(f"input={t} mex={prefix_mex(t)}")

Whiteboard Walkthrough -- First Missing Positive (LeetCode 41)¶

A classic MEX-flavored interview question with an elegant O(n) time, O(1) extra space solution.

Problem. Given an unsorted integer array nums, return the smallest missing positive integer.

Example. [3, 4, -1, 1] -> 2.

Key insight. The answer is in [1, n+1] (1-indexed pigeonhole). Use the array itself as the bucket: for each i, swap nums[i] to its target index nums[i] - 1 (if it is in range and not already there). After the pass, the first index i where nums[i] != i + 1 is the answer (i + 1); if all match, the answer is n + 1.

Go¶

package main

import "fmt"

func FirstMissingPositive(nums []int) int {
    n := len(nums)
    for i := 0; i < n; i++ {
        for nums[i] >= 1 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
            nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i := 0; i < n; i++ {
        if nums[i] != i+1 {
            return i + 1
        }
    }
    return n + 1
}

func main() {
    fmt.Println(FirstMissingPositive([]int{3, 4, -1, 1})) // 2
    fmt.Println(FirstMissingPositive([]int{1, 2, 0}))     // 3
    fmt.Println(FirstMissingPositive([]int{7, 8, 9, 11})) // 1
}

Java¶

public class FirstMissingPositive {
    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int t = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = t;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }

    public static void main(String[] args) {
        System.out.println(firstMissingPositive(new int[]{3, 4, -1, 1})); // 2
        System.out.println(firstMissingPositive(new int[]{1, 2, 0}));     // 3
        System.out.println(firstMissingPositive(new int[]{7, 8, 9, 11})); // 1
    }
}

Python¶

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1


print(first_missing_positive([3, 4, -1, 1]))  # 2
print(first_missing_positive([1, 2, 0]))      # 3
print(first_missing_positive([7, 8, 9, 11]))  # 1

Why this is O(n). Each swap places at least one value at its correct index. There are n indices, so the total number of swaps across the outer loop is at most n. The inner while looks unbounded but is amortized O(1) per outer iteration.

Whiteboard Walkthrough -- Grundy Values for Nim Variants¶

Another common interview topic: compute Grundy numbers and use XOR to decide the winner.

Problem (Bouton's Nim). Three piles of sizes (a, b, c). Each turn, remove any positive number of stones from one pile. Last to move wins. Who wins under optimal play?

Answer. XOR of pile sizes. If a XOR b XOR c == 0, the player to move loses; else they win.

Why. For a single pile of size k, the reachable Grundies are {0, 1, ..., k-1} (move to any smaller pile), so Grundy(k) = MEX({0..k-1}) = k. By Sprague-Grundy, the Grundy of the three-pile sum is Grundy(a) XOR Grundy(b) XOR Grundy(c) = a XOR b XOR c.

Python: Nim with arbitrary move sets¶

from functools import lru_cache


def nim_grundy(piles, moves):
    """Grundy number of a multi-pile Nim variant with restricted moves."""
    @lru_cache(maxsize=None)
    def g(n):
        if n == 0:
            return 0
        reach = set()
        for m in moves:
            if n >= m:
                reach.add(g(n - m))
        gv = 0
        while gv in reach:
            gv += 1
        return gv

    xor = 0
    for p in piles:
        xor ^= g(p)
    return xor


# Standard Nim: any positive removal.
# We approximate by moves = 1..max(piles) for small piles.
def standard_nim_winner(piles):
    return "first" if (piles[0] ^ piles[1] ^ piles[2]) else "second"


print(standard_nim_winner([3, 4, 5]))  # first (3^4^5 = 2 != 0)
print(standard_nim_winner([1, 2, 3]))  # second (1^2^3 = 0)

The MEX-of-reachable-grundies pattern is the same in every impartial-game problem. Memorize it.

Mistakes Interviewers Watch For¶

How to Approach a New MEX Problem¶

A four-step recipe to verbalize:

1. Static or dynamic? If the set never changes, bucket. If it does, TreeSet of missing or segment tree.
2. Value range bounded? If unbounded, hash set scanning upward. If bounded by n, bucket of size n + 1.
3. One MEX or many? One: just compute. Many on the same array: prefix-MEX in O(n) or range-MEX with persistent seg tree.
4. Game theory? If the problem mentions players, moves, or "last to move wins," it is Sprague-Grundy -- compute Grundies via MEX-of-reachable and XOR them.

Verbalizing these four questions before coding shows clear thinking, which is half of what is graded.

Quick-Recall Cheat Sheet¶

If you remember the table, you can pick the right MEX variant for any prompt under interview pressure.