🎯 PHP Stack & Queue — Top 25 Interview Questions

---

Q1 — Valid Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Opening bracket → push; closing bracket → must match stack top.

Step 2 — Brute force (what NOT to do): Count opens vs closes — fails for mismatched order.

Step 3 — Optimal insight: Stack ensures LIFO matching order.

Step 4 — Algorithm:

1. Map closing → opening

2. Push opens; on close → if stack empty or top mismatch → false

3. Return empty stack

Step 5 — Edge cases: Only closings; interleaved types ({[]}).

function isValid(string $s): bool {
    $stack = [];
    $map   = [')' => '(', ']' => '[', '}' => '{'];
    foreach (str_split($s) as $ch) {
        if (in_array($ch, ['(', '[', '{'])) {
            $stack[] = $ch;
        } else {
            if (empty($stack) || end($stack) !== $map[$ch]) return false;
            array_pop($stack);
        }
    }
    return empty($stack);
}

Time: O(n) | Space: O(n)

---

Q2 — Min Stack

🧠 How to Approach This

Step 1 — Recognize the pattern: Track running minimum alongside each pushed value.

Step 2 — Brute force (what NOT to do): Scan stack on getMin — O(n).

Step 3 — Optimal insight: Store [value, min_so_far] pairs — O(1) for all operations.

Step 4 — Algorithm:

1. Push: append [val, min(val, current_min)]

2. Pop/top/getMin: index into top pair

Step 5 — Edge cases: Empty stack at first push; repeated min values.

class MinStack {
    private array $stack = [];
    public function push(int $val): void {
        $min = empty($this->stack) ? $val : min($val, end($this->stack)[1]);
        $this->stack[] = [$val, $min];
    }
    public function pop(): void   { array_pop($this->stack); }
    public function top(): int    { return end($this->stack)[0]; }
    public function getMin(): int { return end($this->stack)[1]; }
}

Time: O(1) all ops | Space: O(n)

---

Q3 — Evaluate Reverse Polish Notation

🧠 How to Approach This

Step 1 — Recognize the pattern: Operand → push; operator → pop two, compute, push result.

Step 2 — Brute force (what NOT to do): Parse into expression tree — overkill.

Step 3 — Optimal insight: Stack evaluates RPN directly left to right.

Step 4 — Algorithm:

1. For each token: if number → push; if operator → pop b, pop a, compute a OP b, push

2. Return stack top

Step 5 — Edge cases: Division truncates toward zero (use intdiv, adjust for negatives).

function evalRPN(array $tokens): int {
    $stack = [];
    foreach ($tokens as $t) {
        if (in_array($t, ['+', '-', '*', '/'])) {
            $b = array_pop($stack);
            $a = array_pop($stack);
            $stack[] = match($t) {
                '+'  => $a + $b,
                '-'  => $a - $b,
                '*'  => $a * $b,
                '/'  => intdiv($a, $b), // truncate toward zero
            };
        } else {
            $stack[] = (int)$t;
        }
    }
    return end($stack);
}

Time: O(n) | Space: O(n)

---

Q4 — Daily Temperatures

🧠 How to Approach This

Step 1 — Recognize the pattern: "How many days until warmer" → monotonic decreasing stack.

Step 2 — Brute force (what NOT to do): Nested loops — O(n²).

Step 3 — Optimal insight: Stack of indices. When warmer found, answer = current_i - stored_i.

Step 4 — Algorithm:

1. Stack of indices, maintaining decreasing temps

2. Each element: pop while top's temp < current → result[pop] = i - pop

3. Push current index

Step 5 — Edge cases: No warmer day → result stays 0.

function dailyTemperatures(array $temps): array {
    $n = count($temps);
    $result = array_fill(0, $n, 0);
    $stack  = [];
    for ($i = 0; $i < $n; $i++) {
        while (!empty($stack) && $temps[end($stack)] < $temps[$i]) {
            $idx = array_pop($stack);
            $result[$idx] = $i - $idx;
        }
        $stack[] = $i;
    }
    return $result;
}

Time: O(n) | Space: O(n)

---

Q5 — Next Greater Element I

🧠 How to Approach This

Step 1 — Recognize the pattern: Precompute next-greater for nums2, then answer queries for nums1.

Step 2 — Brute force (what NOT to do): For each element in nums1, scan nums2 forward — O(m·n).

Step 3 — Optimal insight: Monotonic stack on nums2 → map[val] = next_greater. Then lookup.

Step 4 — Algorithm:

1. Build monotonic stack on nums2, fill map

2. For each num in nums1: answer = map[num] ?? -1

Step 5 — Edge cases: No greater element in nums2 → -1.

function nextGreaterElement(array $nums1, array $nums2): array {
    $map   = [];
    $stack = [];
    foreach ($nums2 as $num) {
        while (!empty($stack) && end($stack) < $num) {
            $map[array_pop($stack)] = $num;
        }
        $stack[] = $num;
    }
    return array_map(fn($n) => $map[$n] ?? -1, $nums1);
}

Time: O(n + m) | Space: O(n)

---

Q6 — Next Greater Element II (Circular Array)

🧠 How to Approach This

Step 1 — Recognize the pattern: Circular array — process array twice to simulate wrapping.

Step 2 — Brute force (what NOT to do): Nested loop with modulo — O(n²).

Step 3 — Optimal insight: Iterate 0..2n-1 with index % n. Second pass resolves remaining stack elements.

Step 4 — Algorithm:

1. Monotonic decreasing stack of indices

2. Loop 0..2n-1; index = i % n; resolve stack when nums[stack.top] < nums[i%n]

3. Only push on first pass (i < n)

Step 5 — Edge cases: All same values → all -1.

function nextGreaterElements(array $nums): array {
    $n      = count($nums);
    $result = array_fill(0, $n, -1);
    $stack  = [];
    for ($i = 0; $i < 2 * $n; $i++) {
        $idx = $i % $n;
        while (!empty($stack) && $nums[end($stack)] < $nums[$idx]) {
            $result[array_pop($stack)] = $nums[$idx];
        }
        if ($i < $n) $stack[] = $idx;
    }
    return $result;
}

Time: O(n) | Space: O(n)

---

Q7 — Largest Rectangle in Histogram

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic increasing stack — pop when shorter bar arrives.

Step 2 — Brute force (what NOT to do): All pairs of bars — O(n²).

Step 3 — Optimal insight: Each popped bar's height defines a rectangle; width = i - new_top - 1.

Step 4 — Algorithm:

1. Append sentinel 0 to heights

2. Stack starts with -1 (sentinel index)

3. On pop: area = heights[pop] × (i - stack_top - 1)

Step 5 — Edge cases: Sentinel forces all bars to be processed at end.

function largestRectangleArea(array $heights): int {
    $heights[] = 0;
    $stack     = [-1];
    $maxArea   = 0;
    foreach ($heights as $i => $h) {
        while (count($stack) > 1 && $heights[end($stack)] > $h) {
            $height  = $heights[array_pop($stack)];
            $width   = $i - end($stack) - 1;
            $maxArea = max($maxArea, $height * $width);
        }
        $stack[] = $i;
    }
    return $maxArea;
}

Time: O(n) | Space: O(n)

---

Q8 — Trapping Rain Water (Stack Approach)

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack-based horizontal layer calculation.

Step 2 — Brute force (what NOT to do): For each bar find max left/right — O(n²) or O(n) with arrays.

Step 3 — Optimal insight: Stack holds decreasing heights. When a taller bar arrives, pop and compute water in the "valley".

Step 4 — Algorithm:

1. Monotonic decreasing stack of indices

2. When heights[i] > heights[top]: pop, compute bounded water above valley

3. Water = (min(heights[left], heights[i]) - heights[bottom]) × width

Step 5 — Edge cases: No valley (sorted ascending/descending → 0).

function trap(array $height): int {
    $stack = [];
    $water = 0;
    for ($i = 0; $i < count($height); $i++) {
        while (!empty($stack) && $height[end($stack)] < $height[$i]) {
            $bottom = array_pop($stack);
            if (empty($stack)) break;
            $left   = end($stack);
            $h      = min($height[$left], $height[$i]) - $height[$bottom];
            $w      = $i - $left - 1;
            $water += $h * $w;
        }
        $stack[] = $i;
    }
    return $water;
}

Time: O(n) | Space: O(n)

---

Q9 — Implement Queue Using Two Stacks

🧠 How to Approach This

Step 1 — Recognize the pattern: LIFO + LIFO → FIFO via lazy reversal.

Step 2 — Brute force (what NOT to do): Reverse on every push or pop — O(n) each time.

Step 3 — Optimal insight: Only transfer when outStack is empty — amortized O(1).

Step 4 — Algorithm:

1. push → inStack

2. pop/peek → if outStack empty, drain inStack into outStack

Step 5 — Edge cases: Multiple pops in a row without pushes.

class MyQueue {
    private array $in = [], $out = [];
    public function push(int $x): void { $this->in[] = $x; }
    public function pop(): int  { $this->transfer(); return array_pop($this->out); }
    public function peek(): int { $this->transfer(); return end($this->out); }
    public function empty(): bool { return empty($this->in) && empty($this->out); }
    private function transfer(): void {
        if (empty($this->out))
            while (!empty($this->in)) $this->out[] = array_pop($this->in);
    }
}

Time: O(1) amortized | Space: O(n)

---

Q10 — Implement Stack Using Two Queues

🧠 How to Approach This

Step 1 — Recognize the pattern: FIFO + FIFO → LIFO by rotating elements.

Step 2 — Brute force (what NOT to do): Always copy — O(n) per push or pop.

Step 3 — Optimal insight: On push, enqueue to q2 then drain q1 into q2, swap names.

Step 4 — Algorithm:

1. Push: enqueue to q2, drain q1→q2, swap q1↔q2

2. Pop: dequeue from q1 (front is the top/newest)

Step 5 — Edge cases: Single element; multiple pops.

class MyStack {
    private SplQueue $q1, $q2;
    public function __construct() { $this->q1 = new SplQueue(); $this->q2 = new SplQueue(); }
    public function push(int $x): void {
        $this->q2->enqueue($x);
        while (!$this->q1->isEmpty()) $this->q2->enqueue($this->q1->dequeue());
        [$this->q1, $this->q2] = [$this->q2, $this->q1];
    }
    public function pop(): int   { return $this->q1->dequeue(); }
    public function top(): int   { return $this->q1->bottom(); }
    public function empty(): bool { return $this->q1->isEmpty(); }
}

Time: O(n) push, O(1) pop | Space: O(n)

---

Q11 — Sliding Window Maximum (Deque)

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic decreasing deque of indices.

Step 2 — Brute force (what NOT to do): Scan k elements per window — O(n·k).

Step 3 — Optimal insight: Front of deque = current max index. Remove out-of-window from front; remove smaller from back.

Step 4 — Algorithm:

1. Remove expired indices from front

2. Remove smaller elements from back

3. Append result when i ≥ k-1

Step 5 — Edge cases: k = 1 (max = each element); k > n.

function maxSlidingWindow(array $nums, int $k): array {
    $deque = []; $result = [];
    for ($i = 0; $i < count($nums); $i++) {
        while (!empty($deque) && $deque[0] < $i - $k + 1) array_shift($deque);
        while (!empty($deque) && $nums[end($deque)] < $nums[$i]) array_pop($deque);
        $deque[] = $i;
        if ($i >= $k - 1) $result[] = $nums[$deque[0]];
    }
    return $result;
}

Time: O(n) | Space: O(k)

---

Q12 — Basic Calculator (+ - and Parentheses)

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack to save (result, sign) on open paren; restore on close.

Step 2 — Brute force (what NOT to do): Build expression tree — complex.

Step 3 — Optimal insight: Track current result and sign; on ( push state, on ) pop and combine.

Step 4 — Algorithm:

1. result = 0, sign = 1

2. On (: push [result, sign]; reset result = 0, sign = 1

3. On ): result = result + sign * pop_sign + pop_result

Step 5 — Edge cases: Multiple digit numbers; spaces.

function calculate(string $s): int {
    $stack = []; $result = 0; $sign = 1; $num = 0;
    foreach (str_split($s) as $ch) {
        if (ctype_digit($ch)) {
            $num = $num * 10 + (int)$ch;
        } elseif ($ch === '+' || $ch === '-') {
            $result += $sign * $num; $num = 0;
            $sign = ($ch === '+') ? 1 : -1;
        } elseif ($ch === '(') {
            array_push($stack, $result); array_push($stack, $sign);
            $result = 0; $sign = 1;
        } elseif ($ch === ')') {
            $result += $sign * $num; $num = 0;
            $result *= array_pop($stack);  // sign before paren
            $result += array_pop($stack);  // result before paren
        }
    }
    return $result + $sign * $num;
}

Time: O(n) | Space: O(n)

---

Q13 — Basic Calculator II (+ - * /)

🧠 How to Approach This

Step 1 — Recognize the pattern: Handle precedence: push + - operands; apply * / immediately.

Step 2 — Brute force (what NOT to do): Two passes for precedence levels — complex.

Step 3 — Optimal insight: Stack for addition operands; multiply/divide modifies the top of stack.

Step 4 — Algorithm:

1. Track num and last sign

2. On new operator/end: if + push num, if - push -num, if pop and push popnum, if / pop and push pop/num

Step 5 — Edge cases: Multi-digit numbers; trailing digit.

function calculateII(string $s): int {
    $stack = []; $num = 0; $sign = '+';
    $s = trim($s);
    for ($i = 0; $i < strlen($s); $i++) {
        $ch = $s[$i];
        if (ctype_digit($ch)) $num = $num * 10 + (int)$ch;
        if ((!ctype_digit($ch) && $ch !== ' ') || $i === strlen($s) - 1) {
            if ($sign === '+')      $stack[] = $num;
            elseif ($sign === '-')  $stack[] = -$num;
            elseif ($sign === '*')  $stack[] = array_pop($stack) * $num;
            elseif ($sign === '/')  $stack[] = intdiv(array_pop($stack), $num);
            $sign = $ch; $num = 0;
        }
    }
    return array_sum($stack);
}

Time: O(n) | Space: O(n)

---

Q14 — Decode String

🧠 How to Approach This

Step 1 — Recognize the pattern: Nested encoding → stack to save (string, repeat_count) state on [.

Step 2 — Brute force (what NOT to do): Recursion without memoization — deep nesting expensive.

Step 3 — Optimal insight: Stack stores (partial_str, k) on [; on ] pop and expand.

Step 4 — Algorithm:

1. Build current string and number

2. On [: push [current_str, k]; reset

3. On ]: pop, prepend saved_str + (current_str × k)

Step 5 — Edge cases: Multi-digit numbers; nested 3[a2[c]].

function decodeString(string $s): string {
    $stack = []; $cur = ''; $k = 0;
    foreach (str_split($s) as $ch) {
        if (ctype_digit($ch)) {
            $k = $k * 10 + (int)$ch;
        } elseif ($ch === '[') {
            array_push($stack, [$cur, $k]); $cur = ''; $k = 0;
        } elseif ($ch === ']') {
            [$prev, $times] = array_pop($stack);
            $cur = $prev . str_repeat($cur, $times);
        } else {
            $cur .= $ch;
        }
    }
    return $cur;
}

Time: O(output length) | Space: O(n)

---

Q15 — Remove Duplicate Letters (Lexicographically Smallest)

🧠 How to Approach This

Step 1 — Recognize the pattern: Greedy + monotonic stack. Remove larger chars if they appear later.

Step 2 — Brute force (what NOT to do): All permutations of distinct characters — factorial.

Step 3 — Optimal insight: Use last-occurrence index. Pop stack top if top > current char AND top appears again later.

Step 4 — Algorithm:

1. Count last occurrence of each char

2. Monotonic increasing stack with "in stack" set

3. Pop when larger char has future occurrence

Step 5 — Edge cases: Duplicate chars in middle; single occurrences.

function removeDuplicateLetters(string $s): string {
    $last  = [];
    for ($i = 0; $i < strlen($s); $i++) $last[$s[$i]] = $i;
    $stack = []; $inStack = [];
    for ($i = 0; $i < strlen($s); $i++) {
        $ch = $s[$i];
        if (isset($inStack[$ch])) continue;
        while (!empty($stack) && end($stack) > $ch && isset($last[end($stack)]) && $last[end($stack)] > $i) {
            $removed = array_pop($stack);
            unset($inStack[$removed]);
        }
        $stack[] = $ch;
        $inStack[$ch] = true;
    }
    return implode('', $stack);
}

Time: O(n) | Space: O(1) (26 letters)

---

Q16 — Remove K Digits (Smallest Number)

🧠 How to Approach This

Step 1 — Recognize the pattern: Greedy — remove a digit when a smaller one follows (k times).

Step 2 — Brute force (what NOT to do): Try all combinations of removed digits — O(n choose k).

Step 3 — Optimal insight: Monotonic increasing stack. Pop when stack top > current digit and k > 0.

Step 4 — Algorithm:

1. Increasing stack, pop when top > curr and k > 0 (k--)

2. After loop, if k > 0: remove from end

3. Trim leading zeros

Step 5 — Edge cases: k = n (return "0"); leading zeros after removal.

function removeKdigits(string $num, int $k): string {
    $stack = [];
    foreach (str_split($num) as $d) {
        while ($k > 0 && !empty($stack) && end($stack) > $d) {
            array_pop($stack); $k--;
        }
        $stack[] = $d;
    }
    while ($k-- > 0) array_pop($stack);
    $result = ltrim(implode('', $stack), '0');
    return $result === '' ? '0' : $result;
}

Time: O(n) | Space: O(n)

---

Q17 — Score of Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack-based scoring: () = 1, nested = 2 × inner.

Step 2 — Brute force (what NOT to do): Recursive counting — harder to track nesting.

Step 3 — Optimal insight: Stack with 0 as layer marker. On ), pop and either score 1 or 2×inner.

Step 4 — Algorithm:

1. On (: push 0 (start layer)

2. On ): pop v; if v == 0 push 1 (leaf), else push 2*v; add to top

Step 5 — Edge cases: Adjacent ()() — summed at same level.

function scoreOfParentheses(string $s): int {
    $stack = [0];
    foreach (str_split($s) as $ch) {
        if ($ch === '(') {
            $stack[] = 0;
        } else {
            $v = array_pop($stack);
            $stack[count($stack)-1] += max(2 * $v, 1);
        }
    }
    return end($stack);
}

Time: O(n) | Space: O(n)

---

Q18 — Asteroid Collision

🧠 How to Approach This

Step 1 — Recognize the pattern: Collision only when positive (moving right) meets negative (moving left).

Step 2 — Brute force (what NOT to do): Simulate all pairs — O(n²).

Step 3 — Optimal insight: Stack. Positive → push. Negative → collide with positive tops, apply size comparison.

Step 4 — Algorithm:

1. If positive or stack top is negative → push

2. If negative: while top > 0 and |neg| > top: pop (top explodes)

3. Equal: pop both. If negative wins: push it.

Step 5 — Edge cases: All same direction; equal size collision (both destroyed).

function asteroidCollision(array $asteroids): array {
    $stack = [];
    foreach ($asteroids as $a) {
        $alive = true;
        while ($alive && $a < 0 && !empty($stack) && end($stack) > 0) {
            if (end($stack) < -$a)        array_pop($stack);
            elseif (end($stack) === -$a) { array_pop($stack); $alive = false; }
            else                          $alive = false;
        }
        if ($alive) $stack[] = $a;
    }
    return $stack;
}

Time: O(n) | Space: O(n)

---

Q19 — Car Fleet

🧠 How to Approach This

Step 1 — Recognize the pattern: Sort by position descending. Cars that don't catch up form separate fleets.

Step 2 — Brute force (what NOT to do): Simulate time steps — imprecise with floats.

Step 3 — Optimal insight: Time to reach target = (target - pos) / speed. If next car's time ≤ current fleet time, it joins the fleet.

Step 4 — Algorithm:

1. Sort by position descending

2. Compute arrival time for each car

3. Stack: if time > top of stack → new fleet (push); else merge into current fleet

Step 5 — Edge cases: Single car; cars with same position.

function carFleet(int $target, array $position, array $speed): int {
    $n    = count($position);
    $cars = array_map(null, $position, $speed);
    usort($cars, fn($a, $b) => $b[0] <=> $a[0]); // sort descending by position
    $stack = [];
    foreach ($cars as [$pos, $spd]) {
        $time = ($target - $pos) / $spd;
        if (empty($stack) || $time > end($stack)) {
            $stack[] = $time;
        }
    }
    return count($stack);
}

Time: O(n log n) | Space: O(n)

---

Q20 — Exclusive Time of Functions

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack tracks currently running functions. On resume/pause, compute elapsed time.

Step 2 — Brute force (what NOT to do): Parse and simulate per time unit — O(max_time).

Step 3 — Optimal insight: Track previous timestamp. On each log entry compute delta and attribute to current top.

Step 4 — Algorithm:

1. Stack of function IDs

2. On start: add delta to top (if any), push id, update prev

3. On end: add delta+1 to top, pop, update prev to timestamp+1

Step 5 — Edge cases: Nested calls; single function.

function exclusiveTime(int $n, array $logs): array {
    $result = array_fill(0, $n, 0);
    $stack  = [];
    $prev   = 0;
    foreach ($logs as $log) {
        [$id, $type, $time] = explode(':', $log);
        $id = (int)$id; $time = (int)$time;
        if ($type === 'start') {
            if (!empty($stack)) $result[end($stack)] += $time - $prev;
            $stack[] = $id; $prev = $time;
        } else {
            $result[array_pop($stack)] += $time - $prev + 1;
            $prev = $time + 1;
        }
    }
    return $result;
}

Time: O(n) | Space: O(n)

---

Q21 — Number of Visible People in Queue

🧠 How to Approach This

Step 1 — Recognize the pattern: Monotonic decreasing stack — each taller person ends visibility runs.

Step 2 — Brute force (what NOT to do): For each person scan right until blocked — O(n²).

Step 3 — Optimal insight: Process right-to-left. Stack holds heights in decreasing order. Count how many the current person can see.

Step 4 — Algorithm:

1. Traverse right to left

2. Count people shorter than current (they are visible, then blocked)

3. If stack not empty after, add 1 (the taller blocker is also visible)

Step 5 — Edge cases: Strictly decreasing heights — each person sees only next.

function canSeePersonsCount(array $heights): array {
    $n = count($heights);
    $result = array_fill(0, $n, 0);
    $stack  = [];
    for ($i = $n - 1; $i >= 0; $i--) {
        $count = 0;
        while (!empty($stack) && end($stack) < $heights[$i]) {
            array_pop($stack); $count++;
        }
        if (!empty($stack)) $count++; // taller person is also visible
        $result[$i] = $count;
        $stack[] = $heights[$i];
    }
    return $result;
}

Time: O(n) | Space: O(n)

---

Q22 — Design Circular Queue

🧠 How to Approach This

Step 1 — Recognize the pattern: Fixed-size ring buffer with head/tail pointers.

Step 2 — Brute force (what NOT to do): Array with shift/unshift — O(n) per op.

Step 3 — Optimal insight: Circular index arithmetic: (head + size) % capacity.

Step 4 — Algorithm:

1. Array of size k, head = 0, size = 0

2. Enqueue: write at (head+size)%k; dequeue: read at head, advance head

Step 5 — Edge cases: Full on enqueue, empty on dequeue.

class MyCircularQueue {
    private array $data;
    private int $head = 0, $size = 0, $cap;
    public function __construct(int $k) { $this->cap = $k; $this->data = array_fill(0, $k, 0); }
    public function enQueue(int $value): bool {
        if ($this->isFull()) return false;
        $this->data[($this->head + $this->size) % $this->cap] = $value;
        $this->size++; return true;
    }
    public function deQueue(): bool {
        if ($this->isEmpty()) return false;
        $this->head = ($this->head + 1) % $this->cap; $this->size--; return true;
    }
    public function Front(): int { return $this->isEmpty() ? -1 : $this->data[$this->head]; }
    public function Rear(): int  { return $this->isEmpty() ? -1 : $this->data[($this->head + $this->size - 1) % $this->cap]; }
    public function isEmpty(): bool { return $this->size === 0; }
    public function isFull(): bool  { return $this->size === $this->cap; }
}

Time: O(1) all ops | Space: O(k)

---

Q23 — Design Circular Deque

🧠 How to Approach This

Step 1 — Recognize the pattern: Ring buffer with both-end insert/delete.

Step 2 — Brute force (what NOT to do): PHP array with unshift — O(n) front ops.

Step 3 — Optimal insight: Circular array; insert front = move head back: (head - 1 + cap) % cap.

Step 4 — Algorithm:

1. insertFront: head = (head-1+cap)%cap, write there

2. insertLast: write at (head+size)%cap

3. deleteFront/Last: adjust head or size

Step 5 — Edge cases: Full/empty checks before every operation.

class MyCircularDeque {
    private array $data;
    private int $head = 0, $size = 0, $cap;
    public function __construct(int $k) { $this->cap = $k; $this->data = array_fill(0, $k, 0); }
    public function insertFront(int $v): bool {
        if ($this->isFull()) return false;
        $this->head = ($this->head - 1 + $this->cap) % $this->cap;
        $this->data[$this->head] = $v; $this->size++; return true;
    }
    public function insertLast(int $v): bool {
        if ($this->isFull()) return false;
        $this->data[($this->head + $this->size) % $this->cap] = $v; $this->size++; return true;
    }
    public function deleteFront(): bool {
        if ($this->isEmpty()) return false;
        $this->head = ($this->head + 1) % $this->cap; $this->size--; return true;
    }
    public function deleteLast(): bool {
        if ($this->isEmpty()) return false;
        $this->size--; return true;
    }
    public function getFront(): int { return $this->isEmpty() ? -1 : $this->data[$this->head]; }
    public function getRear(): int  { return $this->isEmpty() ? -1 : $this->data[($this->head + $this->size - 1) % $this->cap]; }
    public function isEmpty(): bool { return $this->size === 0; }
    public function isFull(): bool  { return $this->size === $this->cap; }
}

Time: O(1) all ops | Space: O(k)

---

Q24 — Design Hit Counter

🧠 How to Approach This

Step 1 — Recognize the pattern: Sliding window of 300 seconds — queue-based or circular array.

Step 2 — Brute force (what NOT to do): Store all hits, filter on getHits — O(n) per call.

Step 3 — Optimal insight: Queue of timestamps. On getHits, remove expired entries (older than 300s).

Step 4 — Algorithm:

1. hit: append timestamp to queue

2. getHits(t): while front < t-299: dequeue; return count

Step 5 — Edge cases: Multiple hits at same timestamp; no hits in window.

class HitCounter {
    private SplQueue $queue;
    public function __construct() { $this->queue = new SplQueue(); }
    public function hit(int $timestamp): void { $this->queue->enqueue($timestamp); }
    public function getHits(int $timestamp): int {
        while (!$this->queue->isEmpty() && $this->queue->bottom() <= $timestamp - 300) {
            $this->queue->dequeue();
        }
        return $this->queue->count();
    }
}

Time: O(n) worst per getHits, O(1) amortized | Space: O(n)

---

Q25 — Longest Valid Parentheses

🧠 How to Approach This

Step 1 — Recognize the pattern: Stack tracks indices of unmatched brackets to compute lengths.

Step 2 — Brute force (what NOT to do): Check every substring — O(n²) or O(n³).

Step 3 — Optimal insight: Stack stores index of last unmatched (. When ) found and stack empty → push as new base; else pop and compute length = i - stack_top.

Step 4 — Algorithm:

1. Stack initialized with [-1] as base

2. ( → push index; ) → pop; if stack empty push i as new base; else length = i - stack_top

Step 5 — Edge cases: All opening; all closing; alternating.

function longestValidParentheses(string $s): int {
    $stack = [-1];
    $max   = 0;
    for ($i = 0; $i < strlen($s); $i++) {
        if ($s[$i] === '(') {
            $stack[] = $i;
        } else {
            array_pop($stack);
            if (empty($stack)) {
                $stack[] = $i; // new base
            } else {
                $max = max($max, $i - end($stack));
            }
        }
    }
    return $max;
}

Time: O(n) | Space: O(n)