SyntaxPilot
Courses/DSA and Coding Problems/Lesson 87
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 87 of 90

Hard mix 1: first missing positive, longest valid parentheses

queued

These are the notes for DSA episode 87: two famous hard problems that look like they need a lot of time or a lot of memory, and are both solved in one pass. First missing positive (LeetCode 41): trying 1, 2, 3 with a scan each time times out on 40 million numbers, and a HashSet runs out of memory; the fix is to notice that the answer is always in 1 .. n + 1, so the array can be its own notebook: every value v is sent home to index v − 1 with swaps, O(n) time and O(1) extra memory. Longest valid parentheses (LeetCode 32): trying every start with a counter is O(n²) and times out on 500,000 brackets; a stack of indices with a base does it in one pass. Every program below was run with javac 21 (25-second limit and Java's default 1.5 GB heap on the recording machine, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).

The problems, in real life

Real life In code
A gym gives each new member the smallest locker number nobody holds the smallest positive number not in the array
Junk tags in the key basket: 0, a broken −1, duplicates, number 99 in a 4-locker gym values ≤ 0, repeats, values > n
The desk has no room for a second register O(1) extra memory
A calculator formula with messy brackets: highlight the longest correctly bracketed part longest valid substring of ( and )

Every word, from zero

  • Positive integer: a whole number that is 1 or more. 0 and negatives are not positive.
  • O(n) time: the work grows in step with n, the number of items (a few passes).
  • O(1) extra memory: only a few variables, no second array, set or map, whatever the input size.
  • HashSet: a collection that answers "is x in here?" in constant time on average, by storing items in a table of buckets.
  • Boxing: wrapping an int into an Integer object so it can go into a Java collection; each object costs extra bytes.
  • Heap (Java memory): where objects live; its maximum size is fixed when the program starts. OutOfMemoryError is thrown when it is full.
  • Home of a value: in this problem, the index v − 1 for a value v in 1..n.
  • Cyclic placement (cyclic sort): sending each value home by swapping it with whatever sits there, repeated until the value at i cannot move.
  • Amortised analysis: counting the cost over the whole run instead of per step; the inner while loop can run many times for one i, but at most n times in total.
  • Parentheses / brackets: the characters ( (opening) and ) (closing).
  • Valid (balanced) parentheses: every ( is closed by a later ), in the right order, like boxes inside boxes: (())() is valid, )( and (() are not.
  • Substring: a part of a string with no gaps, s[i..j].
  • Balance (counter): +1 for (, −1 for ). Negative means a ) with no partner; zero means everything so far is matched.
  • Stack: a pile where you push on top and pop from the top: last in, first out. Peek looks at the top without removing it.
  • ArrayDeque: Java's fast array-based stack/queue (push, pop, peek).
  • Base (sentinel) index: an index kept at the bottom of the stack, just before the current valid stretch; it starts at −1.

Problem 1: first missing positive (LeetCode 41)

Given an integer array a, return the smallest positive integer that is not in it, in O(n) time and O(1) extra memory.

Input Output Why
[1, 2, 0] 3 1 and 2 are taken
[3, 4, -1, 1] 2 1 is taken, 2 is free
[7, 8, 9, 11, 12] 1 nobody holds 1
[1] 2
[2] 1
[1, 1] 2 duplicates

Obvious idea 1: try 1, 2, 3, ... and scan each time

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        for (int k = 1; ; k++) {
            boolean found = false;
            for (int x : a)
                if (x == k) { found = true; break; }
            if (!found) return k;
        }
    }
    public static void main(String[] args) {
        System.out.println(firstMissing(new int[]{1, 2, 0}));
        System.out.println(firstMissing(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissing(new int[]{7, 8, 9, 11, 12}));
        System.out.println(firstMissing(new int[]{1}));
        System.out.println(firstMissing(new int[]{2}));
        System.out.println(firstMissing(new int[]{1, 1}));
    }
}

Output (real):

3
2
1
2
1
2

Correct. Now the big gym: 40 million tags, 40,000,000 down to 1, with tag 12,345,678 lost and replaced by 0:

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        for (int k = 1; ; k++) {
            boolean found = false;
            for (int x : a)
                if (x == k) { found = true; break; }
            if (!found) return k;
        }
    }
    public static void main(String[] args) {
        int n = 40_000_000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = n - i;
        a[n - 12_345_678] = 0;
        long t0 = System.nanoTime();
        int r = firstMissing(a);
        System.out.println(r + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}

Result (real): Time Limit Exceeded (killed after 25 s). About 12 million tries, each scanning up to 40 million tags: hundreds of trillions of comparisons. O(n²).

Obvious idea 2: a HashSet

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        Set<Integer> seen = new HashSet<>();
        for (int x : a) seen.add(x);
        int k = 1;
        while (seen.contains(k)) k++;
        return k;
    }
    public static void main(String[] args) {
        System.out.println(firstMissing(new int[]{1, 2, 0}));
        System.out.println(firstMissing(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissing(new int[]{7, 8, 9, 11, 12}));
        System.out.println(firstMissing(new int[]{1}));
        System.out.println(firstMissing(new int[]{2}));
        System.out.println(firstMissing(new int[]{1, 1}));
    }
}

Output (real):

3
2
1
2
1
2

On the 40 million tags:

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        Set<Integer> seen = new HashSet<>();
        for (int x : a) seen.add(x);
        int k = 1;
        while (seen.contains(k)) k++;
        return k;
    }
    public static void main(String[] args) {
        int n = 40_000_000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = n - i;
        a[n - 12_345_678] = 0;
        long t0 = System.nanoTime();
        int r = firstMissing(a);
        System.out.println(r + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}

Output (real):

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at java.base/java.util.HashMap.resize(HashMap.java:710)
    at java.base/java.util.HashMap.putVal(HashMap.java:669)
    at java.base/java.util.HashMap.put(HashMap.java:618)
    at java.base/java.util.HashSet.add(HashSet.java:229)

The int[] is about 160 MB, but every number in the set is a boxed Integer plus a map node plus a table slot: around 50 bytes each, about 2 GB. And the problem asked for O(1) extra memory anyway. (Sorting first also works, in O(n log n), but the problem asks for O(n).)

The key insight: the answer is in 1 .. n + 1, and every value has a home

  • n numbers can fill at most the lockers 1..n, so the answer is between 1 and n + 1. Always.
  • So 0, negatives and values > n never matter: they are junk.
  • The array has exactly n slots: use it as the notebook. Value v lives at index v − 1.
  • Send every value home with swaps; then the first index i with a[i] != i + 1 gives the answer i + 1. If every slot is right, the answer is n + 1.

By hand on [3, 4, -1, 1]:

Step Array What happened
start [3, 4, -1, 1]
i = 0 [-1, 4, 3, 1] 3 goes home to index 2
i = 0 [-1, 4, 3, 1] −1 has no home: move on
i = 1 [-1, 1, 3, 4] 4 goes home to index 3
i = 1 [1, -1, 3, 4] 1 goes home to index 0
scan index 1 holds −1, not 2 answer 2

Why the nested loop is still O(n): every swap puts one value in its home for good, and a value at home is never moved again. So there are at most n swaps in the whole run (amortised analysis). The check a[a[i] - 1] != a[i] also stops duplicates from swapping forever.

Solution in Java

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++)
            while (a[i] > 0 && a[i] <= n && a[a[i] - 1] != a[i]) {
                int v = a[i];
                a[i] = a[v - 1];
                a[v - 1] = v;
            }
        for (int i = 0; i < n; i++)
            if (a[i] != i + 1) return i + 1;
        return n + 1;
    }
    public static void main(String[] args) {
        System.out.println(firstMissing(new int[]{1, 2, 0}));
        System.out.println(firstMissing(new int[]{3, 4, -1, 1}));
        System.out.println(firstMissing(new int[]{7, 8, 9, 11, 12}));
        System.out.println(firstMissing(new int[]{1}));
        System.out.println(firstMissing(new int[]{2}));
        System.out.println(firstMissing(new int[]{1, 1}));
    }
}

Output (real):

3
2
1
2
1
2

And the 40 million tags that timed out and ran out of memory:

import java.util.*;

public class Main {
    static int firstMissing(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++)
            while (a[i] > 0 && a[i] <= n && a[a[i] - 1] != a[i]) {
                int v = a[i];
                a[i] = a[v - 1];
                a[v - 1] = v;
            }
        for (int i = 0; i < n; i++)
            if (a[i] != i + 1) return i + 1;
        return n + 1;
    }
    public static void main(String[] args) {
        int n = 40_000_000;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = n - i;
        a[n - 12_345_678] = 0;
        long t0 = System.nanoTime();
        int r = firstMissing(a);
        System.out.println(r + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}

Output (real):

12345678, 77 ms

A real bug: checking the index instead of the home

            while (a[i] > 0 && a[i] <= n && a[i] != i + 1) {

Output (real): 3 2 1 2 1 on separate lines, then Time Limit Exceeded. On [1, 1] the second 1 wants to go home to index 0, swaps with the first 1, and nothing ever changes. Check the home: a[a[i] - 1] != a[i].

Another real bug: no upper bound

Dropping a[i] <= n sends large values to a home that does not exist:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 5
    at Main.firstMissing(Main.java:7)

(after printing 3 and 2: the value 7 in [7, 8, 9, 11, 12] has "home" index 6).

Problem 2: longest valid parentheses (LeetCode 32)

Given a string of only ( and ), return the length of the longest valid substring.

Input Output Longest valid part
"(()" 2 "()"
")()())" 4 "()()"
"" 0
"()(())" 6 the whole string
"(((" 0
"()(()" 2 "()"

Brute force: every start, walk with a counter

For each start i, walk j to the right with a balance. Stop when it goes negative; when it is zero, s[i..j] is valid.

import java.util.*;

public class Main {
    static int longest(String s) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            int bal = 0;
            for (int j = i; j < s.length(); j++) {
                bal += s.charAt(j) == '(' ? 1 : -1;
                if (bal < 0) break;
                if (bal == 0) best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longest("(()"));
        System.out.println(longest(")()())"));
        System.out.println(longest(""));
        System.out.println(longest("()(())"));
        System.out.println(longest("((("));
        System.out.println(longest("()(()"));
    }
}

Output (real):

2
4
0
6
0
2

A big formula: 250,000 ( followed by 250,000 ):

import java.util.*;

public class Main {
    static int longest(String s) {
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            int bal = 0;
            for (int j = i; j < s.length(); j++) {
                bal += s.charAt(j) == '(' ? 1 : -1;
                if (bal < 0) break;
                if (bal == 0) best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
    public static void main(String[] args) {
        String s = "(".repeat(250_000) + ")".repeat(250_000);
        long t0 = System.nanoTime();
        int r = longest(s);
        System.out.println(r + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}

Result (real): Time Limit Exceeded. Every start in the first half walks almost to the end: about n²/4 ≈ 60 billion steps. O(n²).

The key insight: remember WHERE, not how many

The counter only knows how many brackets are open, so we restart from every i. A stack of indices remembers where:

  • Push the index of every (. A ) pops its partner, the most recent unmatched (.
  • At the bottom keep a base: the index just before the current valid stretch. Start with −1.
  • After a pop, if the stack is empty, this ) had no partner: push its index as the new base. Otherwise the current valid stretch has length i − stack.peek().

By hand on ")()())":

i char action stack (bottom → top) length best
start [-1] 0
0 ) pop −1, empty → push 0 (new base) [0] 0
1 ( push 1 [0, 1] 0
2 ) pop 1, top 0 [0] 2 − 0 = 2 2
3 ( push 3 [0, 3] 2
4 ) pop 3, top 0 [0] 4 − 0 = 4 4
5 ) pop 0, empty → push 5 [5] 4

Solution in Java

import java.util.*;

public class Main {
    static int longest(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1);
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') st.push(i);
            else {
                st.pop();
                if (st.isEmpty()) st.push(i);
                else best = Math.max(best, i - st.peek());
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longest("(()"));
        System.out.println(longest(")()())"));
        System.out.println(longest(""));
        System.out.println(longest("()(())"));
        System.out.println(longest("((("));
        System.out.println(longest("()(()"));
    }
}

Output (real):

2
4
0
6
0
2

And the big formula that timed out:

import java.util.*;

public class Main {
    static int longest(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(-1);
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') st.push(i);
            else {
                st.pop();
                if (st.isEmpty()) st.push(i);
                else best = Math.max(best, i - st.peek());
            }
        }
        return best;
    }
    public static void main(String[] args) {
        String s = "(".repeat(250_000) + ")".repeat(250_000);
        long t0 = System.nanoTime();
        int r = longest(s);
        System.out.println(r + ", " + (System.nanoTime() - t0) / 1000000 + " ms");
    }
}

Output (real):

500000, 46 ms

A real bug: forgetting the base −1

import java.util.*;

public class Main {
    static int longest(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') st.push(i);
            else {
                st.pop();
                if (st.isEmpty()) st.push(i);
                else best = Math.max(best, i - st.peek());
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(longest("(()"));
        System.out.println(longest(")()())"));
        System.out.println(longest(""));
    }
}

Output (real):

2
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.ArrayDeque.removeFirst(ArrayDeque.java:361)
    at java.base/java.util.ArrayDeque.pop(ArrayDeque.java:592)
    at Main.longest(Main.java:10)
    at Main.main(Main.java:19)

The very first ) of ")()())" pops an empty stack. The base makes the first bracket safe and measures a stretch that starts at index 0.

The same solutions in C++

#include <bits/stdc++.h>
using namespace std;

// Problem 1: first missing positive. Send every value v in 1..n home to index v - 1.
int firstMissing(vector<int> a) {
    int n = a.size();
    for (int i = 0; i < n; i++)
        while (a[i] > 0 && a[i] <= n && a[a[i] - 1] != a[i])
            swap(a[i], a[a[i] - 1]);
    for (int i = 0; i < n; i++)
        if (a[i] != i + 1) return i + 1;
    return n + 1;
}

// Problem 2: longest valid parentheses. A stack of indices with a base.
int longest(const string& s) {
    vector<int> st = {-1};
    int best = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') st.push_back(i);
        else {
            st.pop_back();
            if (st.empty()) st.push_back(i);
            else best = max(best, i - st.back());
        }
    }
    return best;
}

int main() {
    for (auto v : vector<vector<int>>{{1, 2, 0}, {3, 4, -1, 1}, {7, 8, 9, 11, 12}, {1}, {2}, {1, 1}})
        cout << firstMissing(v) << "\n";
    for (string s : {"(()", ")()())", "", "()(())", "(((", "()(()"})
        cout << longest(s) << "\n";
}

Output (real, g++ -O2):

3
2
1
2
1
2
2
4
0
6
0
2

The same solutions in Python

def first_missing(a):
    """Problem 1: send every value v in 1..n home to index v - 1."""
    n = len(a)
    for i in range(n):
        while 0 < a[i] <= n and a[a[i] - 1] != a[i]:
            v = a[i]
            a[i], a[v - 1] = a[v - 1], v
    for i in range(n):
        if a[i] != i + 1:
            return i + 1
    return n + 1


def longest(s):
    """Problem 2: a stack of indices with a base."""
    st = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == '(':
            st.append(i)
        else:
            st.pop()
            if not st:
                st.append(i)
            else:
                best = max(best, i - st[-1])
    return best


for a in ([1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12], [1], [2], [1, 1]):
    print(first_missing(a))
for s in ("(()", ")()())", "", "()(())", "(((", "()(()"):
    print(longest(s))

Output (real, Python 3):

3
2
1
2
1
2
2
4
0
6
0
2

Complexity

Problem Approach Time Extra memory Big test
First missing try 1, 2, 3 with a scan O(n²) O(1) 40 million: Time Limit Exceeded
First missing HashSet O(n) average O(n) 40 million: OutOfMemoryError
First missing sort first O(n log n) O(1) to O(log n) works, but not O(n)
First missing send every value home O(n) (at most n swaps) O(1) fast
Parentheses every substring, check each O(n³) O(1) –
Parentheses every start + a counter O(n²) O(1) 500,000: Time Limit Exceeded
Parentheses stack of indices with a base O(n) O(n) fast
Parentheses two counters, two passes (practice 2) O(n) O(1) fast

Common mistakes

Mistake What you see (real) Why Fix
Try k = 1, 2, 3 ... with a scan Time Limit Exceeded O(n²) send values home with swaps
HashSet of 40 million numbers OutOfMemoryError: Java heap space boxed Integers, ~50 bytes each the array is the notebook
while (... a[i] != i + 1) Time Limit Exceeded on [1, 1] duplicate swaps forever a[a[i] - 1] != a[i]
No a[i] <= n check ArrayIndexOutOfBoundsException: Index 6 out of bounds for length 5 value bigger than the array has no home keep a[i] <= n
Scanning for the answer from index 1 wrong answer for [2] the home of 1 is index 0 start the scan at 0
Every start + a counter Time Limit Exceeded O(n²) a stack of indices
No st.push(-1) java.util.NoSuchElementException pop on an empty stack start with base −1
Pushing characters instead of indices cannot compute a length the stack must remember positions push i

Mini project: the gym desk

The episode's problem is a one-time question about an array. A real gym desk answers it again and again while members join and leave. Keep the returned lockers in a min-heap (PriorityQueue) and a counter next for the first locker never used:

import java.util.*;

public class Main {
    // Mini project: the gym desk. Members join and leave; each new member gets the smallest free locker.
    // Free lockers that were returned live in a min-heap; "next" is the first locker never used.
    static PriorityQueue<Integer> returned = new PriorityQueue<>();
    static int next = 1;
    static int join() { return returned.isEmpty() ? next++ : returned.poll(); }
    static void leave(int locker) { returned.add(locker); }
    public static void main(String[] args) {
        int a = join(), b = join(), c = join();
        System.out.println("joined: " + a + " " + b + " " + c);
        leave(2);
        leave(1);
        System.out.println("next three: " + join() + " " + join() + " " + join());
    }
}

Output (real):

joined: 1 2 3
next three: 1 2 4

Extend it: refuse to leave a locker that is not taken, and print the free lockers at any time.

Practice

1. Find All Duplicates in an Array (LeetCode 442): values are in 1..n, each appears once or twice. Return the ones that appear twice, in O(n) time and O(1) extra memory.

2. Longest valid parentheses in O(1) extra memory: two counters, a left-to-right pass and a right-to-left pass.

3. Missing Number (LeetCode 268): n distinct numbers from 0..n; one is missing.

Solutions
import java.util.*;

public class Main {
    // 1. Find All Duplicates in an Array (LeetCode 442): values are 1..n, each appears once or twice.
    //    Send every value home with swaps; afterwards a value sitting in someone else's home is a duplicate.
    static List<Integer> duplicates(int[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++)
            while (a[a[i] - 1] != a[i]) { int v = a[i]; a[i] = a[v - 1]; a[v - 1] = v; }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) if (a[i] != i + 1) res.add(a[i]);
        return res;
    }
    // 2. Longest valid parentheses with O(1) extra memory: two counters, two passes.
    static int longestO1(String s) {
        int best = 0, open = 0, close = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') open++; else close++;
            if (open == close) best = Math.max(best, 2 * close);
            else if (close > open) { open = 0; close = 0; }
        }
        open = 0; close = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') open++; else close++;
            if (open == close) best = Math.max(best, 2 * open);
            else if (open > close) { open = 0; close = 0; }
        }
        return best;
    }
    // 3. Missing Number (LeetCode 268): n distinct numbers from 0..n, one is missing. XOR everything.
    static int missingNumber(int[] a) {
        int x = a.length;
        for (int i = 0; i < a.length; i++) x ^= i ^ a[i];
        return x;
    }
    public static void main(String[] args) {
        System.out.println(duplicates(new int[]{4, 3, 2, 7, 8, 2, 3, 1}));
        for (String s : new String[]{"(()", ")()())", "", "()(())", "(((", "()(()"})
            System.out.print(longestO1(s) + " ");
        System.out.println();
        System.out.println(missingNumber(new int[]{3, 0, 1}) + " " + missingNumber(new int[]{9, 6, 4, 2, 3, 5, 7, 0, 1}));
    }
}

Output (real):

[3, 2]
2 4 0 6 0 2 
2 8

Quick quiz

What does firstMissing(new int[]{2, 3, 4, 5}) return? A) 1 B) 6 C) 5 D) 0

Answer

A) 1. No value is 1, so index 0 never holds 1 and the scan stops at index 0. The answer would be 6 only if 1 to 5 were all present.

Interview questions

  1. Why is the answer of first missing positive always in 1..n + 1? n numbers can cover at most 1..n; if they all do, the answer is n + 1, otherwise it is a gap inside 1..n.
  2. The swap loop has a while inside a for. Why is it O(n)? Each swap puts one value in its home permanently, so at most n swaps happen in total.
  3. Can you solve it without swapping? Yes: first replace junk (≤ 0 or > n) with n + 1, then mark "value v seen" by making a[v − 1] negative; the first positive index gives the answer.
  4. Why does the parentheses stack hold indices and not characters? Lengths are differences of positions: i − stack.peek().
  5. What does the base −1 mean? The index just before a stretch that starts at 0; an unmatched ) becomes the new base.
  6. Can longest valid parentheses be done with O(1) memory? Yes, two counters scanned left to right (reset when close > open) and right to left (reset when open > close).
  7. There is also a DP solution. What is dp[i]? The length of the longest valid substring ending at i; for s[i] == ')' it extends from dp[i − 1] or dp[i − 2].

Glossary

Term Meaning
Positive integer A whole number ≥ 1
O(n) time Work grows in step with the input size
O(1) extra memory Only a few variables, whatever the input size
HashSet A set with average constant-time "contains"
Boxing Wrapping an int in an Integer object
Heap / OutOfMemoryError Java's object memory, and the error when it is full
Home of a value Index v − 1 for a value v in 1..n
Cyclic placement Swapping each value into its home
Amortised analysis Counting the total cost over the whole run
Valid parentheses Every ( closed later, in the right order
Substring A part of a string with no gaps
Balance +1 for (, −1 for )
Stack (push / pop / peek) Last in, first out pile
ArrayDeque Java's fast array-based stack and queue
Base (sentinel) index Index just before the current valid stretch, starting at −1
Time Limit Exceeded The program was stopped for running too long (25 s here)

Summary

  • First missing positive: the answer is always in 1..n + 1, so junk can be ignored and the array becomes the notebook.
  • Send every value v home to index v − 1 with swaps (at most n swaps, O(n) amortised), checking the home to stop on duplicates; then the first wrong slot is the answer. O(n) time, O(1) extra memory.
  • Longest valid parentheses: remember where, not how many. A stack of indices with a base −1; a lone ) becomes the new base; length = i − peek. O(n) time.
  • Both brute forces fail on big inputs: O(n²) time limits and a HashSet that does not fit in memory.
  • Next episode: hard mix 2: the alien dictionary and the minimum cost to cut a stick.