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
intinto anIntegerobject 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 − 1for a valuevin1..n. - Cyclic placement (cyclic sort): sending each value home by swapping it with whatever sits there, repeated until the value at
icannot move. - Amortised analysis: counting the cost over the whole run instead of per step; the inner
whileloop can run many times for onei, but at mostntimes 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
nnumbers can fill at most the lockers1..n, so the answer is between1andn + 1. Always.- So
0, negatives and values> nnever matter: they are junk. - The array has exactly
nslots: use it as the notebook. Valuevlives at indexv − 1. - Send every value home with swaps; then the first index
iwitha[i] != i + 1gives the answeri + 1. If every slot is right, the answer isn + 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 lengthi − 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
- Why is the answer of first missing positive always in
1..n + 1?nnumbers can cover at most1..n; if they all do, the answer isn + 1, otherwise it is a gap inside1..n. - The swap loop has a
whileinside afor. Why is it O(n)? Each swap puts one value in its home permanently, so at mostnswaps happen in total. - Can you solve it without swapping? Yes: first replace junk (
≤ 0or> n) withn + 1, then mark "value v seen" by makinga[v − 1]negative; the first positive index gives the answer. - Why does the parentheses stack hold indices and not characters? Lengths are differences of positions:
i − stack.peek(). - What does the base −1 mean? The index just before a stretch that starts at 0; an unmatched
)becomes the new base. - 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 whenopen > close). - There is also a DP solution. What is
dp[i]? The length of the longest valid substring ending ati; fors[i] == ')'it extends fromdp[i − 1]ordp[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
vhome to indexv − 1with swaps (at mostnswaps, 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.