🎯 Top 40 PHP Array Interview Questions

Index: Questions Index | Parent: Array Index

---

How to Use This Guide

For every question, follow this 3-step process before looking at the code:

1. Read the problem — understand what input/output is expected
2. Read the "How to Approach" — understand the thinking pattern
3. Try to code it yourself — then compare with the solution

The goal is to build pattern recognition, not memorise code.

---

Pattern Recognition Quick Guide

Ask these 3 questions before coding:

---

Easy Level

---

Q1. Find All Duplicates in Array [E][FB]

Problem: Array has n numbers, each in range 1–n. Some appear twice, some once. Find all duplicates. No extra memory.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values are in range 1 to n. This is a signal for the index negation trick — use the array itself as a visited marker.

Step 2 — Brute force (what NOT to do):

Use a hash set — O(n) time but O(n) space. The question says no extra memory.

Step 3 — Optimal insight:

For value v, the index v-1 is its "home position". Negate arr[v-1] to mark that value v was seen. If arr[v-1] is already negative, v is a duplicate.

Step 4 — Algorithm:

1. For each element v (use abs(v) since we negate):

2. Compute idx = abs(v) - 1

3. If arr[idx] < 0 → duplicate found, add abs(v) to result

4. Else negate arr[idx] to mark visited

Step 5 — Edge cases:

- Always use abs(v) because earlier elements may have already been negated

- Input array is modified in-place (acceptable if not specified otherwise)

function findDuplicates(array $nums): array {
    $result = [];

    foreach ($nums as $num) {
        $idx = abs($num) - 1;
        if ($nums[$idx] < 0) {
            $result[] = abs($num); // already marked = duplicate
        } else {
            $nums[$idx] = -$nums[$idx]; // mark as visited
        }
    }

    return $result;
}

print_r(findDuplicates([4,3,2,7,8,2,3,1])); // [2,3]

Time: O(n) | Space: O(1) — the result array doesn't count as extra space

---

Q2. Missing Number [E][FB]

Problem: Array has n distinct numbers from 0 to n with exactly one missing. Find it.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

We know exactly what numbers SHOULD be there (0 to n). We need to find which one is absent.

Step 2 — Brute force:

Sort the array, scan for gap. O(n log n) — too slow.

Step 3 — Two optimal approaches:

Approach A — Sum formula:

Expected sum = n*(n+1)/2. Missing = expected - actual sum.

Approach B — XOR (safer for large n, no overflow):

XOR all numbers 0..n with all array values. Pairs cancel (a XOR a = 0). Only missing number remains.

Step 4 — Steps (sum method):

1. Compute expected = n*(n+1)/2

2. Compute actual = array_sum(nums)

3. Return expected - actual

Step 5 — Edge cases:

- n can be large → use XOR to avoid integer overflow

- If all present except n, answer is n

// Method 1: Sum formula — simple and clear
function missingNumber(array $nums): int {
    $n = count($nums);
    $expected = $n * ($n + 1) / 2;
    return $expected - array_sum($nums);
}

// Method 2: XOR — no overflow risk
function missingNumberXOR(array $nums): int {
    $xor = 0;
    $n = count($nums);
    for ($i = 0; $i <= $n; $i++) $xor ^= $i;
    foreach ($nums as $num) $xor ^= $num;
    return $xor;
}

echo missingNumber([3,0,1]);             // 2
echo missingNumber([9,6,4,2,3,5,7,0,1]); // 8

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

---

Q3. Single Number — Find the Non-Duplicate [E][FB]

Problem: Every element appears exactly twice except one. Find the non-duplicate. O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Every element appears twice except one" → XOR trick. Each duplicate pair will cancel itself out.

Step 2 — Brute force:

Use a hash map to count. O(n) time but O(n) space — violates the space constraint.

Step 3 — Optimal insight (XOR properties):

- a XOR a = 0 (same numbers cancel)

- a XOR 0 = a (XOR with zero keeps number)

- XOR is commutative and associative

So XOR of entire array → all pairs cancel → only the single number remains.

Step 4 — Algorithm:

1. Start with result = 0

2. XOR every element into result

3. Return result (only the single number survived)

Step 5 — Edge cases:

- Single element array → return that element

- This works regardless of order

function singleNumber(array $nums): int {
    return array_reduce($nums, fn($carry, $n) => $carry ^ $n, 0);
}

echo singleNumber([2,2,1]);       // 1
echo singleNumber([4,1,2,1,2]);   // 4

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

---

Q4. Plus One [E]

Problem: Array represents a non-negative integer digit-by-digit: [1,2,9] = 129. Add 1.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Simulating addition with carry. Process from the least significant digit (rightmost).

Step 2 — Key insight:

- Digits 0–8: just increment, no carry → done immediately

- Digit 9: becomes 0, carry to next position

- If ALL digits were 9 (e.g. [9,9,9]): result has one extra digit → prepend 1

Step 3 — Algorithm:

1. Loop from right to left

2. If digit < 9: increment and return immediately

3. If digit = 9: set to 0, continue loop (carry)

4. If loop finishes: all were 9 → prepend 1

Step 4 — Edge cases:

- [9,9,9] → [1,0,0,0] (array grows by 1)

- [1,0,0] → [1,0,1]

function plusOne(array $digits): array {
    for ($i = count($digits) - 1; $i >= 0; $i--) {
        if ($digits[$i] < 9) {
            $digits[$i]++;
            return $digits;    // no carry, done
        }
        $digits[$i] = 0;       // was 9, becomes 0, carry continues
    }
    array_unshift($digits, 1); // all 9s case: [9,9,9] → [1,0,0,0]
    return $digits;
}

print_r(plusOne([1,2,9])); // [1,3,0]
print_r(plusOne([9,9,9])); // [1,0,0,0]

Time: O(n) worst case | Space: O(1)

---

Q5. Intersection of Two Arrays [E]

Problem: Find elements that appear in both arrays (with multiplicity).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Frequency counting. Count elements of first array, then consume counts while scanning second array.

Step 2 — Algorithm:

1. Count frequency of each element in nums1 using a hash map

2. For each element in nums2: if it exists in count map with count > 0, add to result and decrement count

Step 3 — Edge cases:

- Duplicate elements: count handles this correctly

- Empty arrays: return empty array

function intersect(array $nums1, array $nums2): array {
    $count = array_count_values($nums1);
    $result = [];

    foreach ($nums2 as $num) {
        if (isset($count[$num]) && $count[$num] > 0) {
            $result[] = $num;
            $count[$num]--;
        }
    }

    return $result;
}

print_r(intersect([1,2,2,1], [2,2])); // [2,2]
print_r(intersect([4,9,5], [9,4,9,8,4])); // [9,4]

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

---

Medium Level

---

Q6. Best Time to Buy and Sell Stock [M][FB]

Problem: Array of prices on each day. Find max profit from one buy and one sell (buy before sell).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Single-pass with minimum tracking. No sorting needed.

Step 2 — Brute force:

Check every buy/sell pair → O(n²). For n=10,000 that's 100M operations — too slow.

Step 3 — Optimal insight:

Profit = sell_price - buy_price. To maximize profit, you want to buy at the LOWEST price seen so far and sell at the HIGHEST price AFTER that point.

As you scan left to right: track the minimum price seen so far. At each day, calculate what profit WOULD be if you sold today. Track the maximum of these.

Step 4 — Algorithm:

1. Set minPrice = +infinity, maxProfit = 0

2. For each price: update minPrice = min(minPrice, price)

3. Update maxProfit = max(maxProfit, price - minPrice)

4. Return maxProfit

Step 5 — Edge cases:

- Prices always decreasing → profit = 0 (never buy)

- Single element → profit = 0

```

[7, 1, 5, 3, 6, 4]

↑ buy here (min=1)

↑ sell here (profit=5) ← maximum

```

function maxProfit(array $prices): int {
    $minPrice  = PHP_INT_MAX;
    $maxProfit = 0;

    foreach ($prices as $price) {
        $minPrice  = min($minPrice, $price);
        $maxProfit = max($maxProfit, $price - $minPrice);
    }

    return $maxProfit;
}

echo maxProfit([7,1,5,3,6,4]); // 5 (buy at 1, sell at 6)
echo maxProfit([7,6,4,3,1]);   // 0 (prices only fall, don't buy)

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

---

Q7. Find All Numbers Disappeared in Array [M]

Problem: Array 1–n, some appear twice, find which numbers are missing. O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values are 1 to n → index negation trick (same as Q1 but finding what's MISSING).

Step 2 — Key insight:

Mark visited numbers by negating the value at index num-1. After marking, indices that still have positive values correspond to numbers that never appeared.

Step 3 — Algorithm:

1. Pass 1: For each num, negate arr[abs(num)-1] to mark "seen"

2. Pass 2: Collect all indices i where arr[i] > 0 → (i+1) is missing

Step 4 — Edge cases:

- Use abs() because some elements were already negated in pass 1

- Don't need to restore — question only asks for result

function findDisappearedNumbers(array $nums): array {
    // Pass 1: Mark visited positions
    foreach ($nums as $num) {
        $idx = abs($num) - 1;
        if ($nums[$idx] > 0) $nums[$idx] = -$nums[$idx];
    }

    // Pass 2: Positive index → that number never appeared
    $result = [];
    foreach ($nums as $i => $num) {
        if ($num > 0) $result[] = $i + 1;
    }

    return $result;
}

print_r(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]
print_r(findDisappearedNumbers([1,1]));               // [2]

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

---

Q8. Majority Element [M][FB]

Problem: Find element that appears more than n/2 times. O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

O(1) space with majority condition → Boyer-Moore Voting Algorithm.

Step 2 — Brute force:

Count with hash map → O(n) space. Sort → O(n log n). Both violate constraints.

Step 3 — Boyer-Moore insight:

Imagine the majority element as a "candidate". Every time it faces a different element, they "cancel" each other. Since majority appears > n/2 times, it will always survive cancellations.

```

[2, 2, 1, 1, 1, 2, 2]

candidate=2 count=1

candidate=2 count=2

count=1 (1 cancels with 2)

count=0 (1 cancels with 2)

candidate=1 count=1 (reset)

count=0 (2 cancels 1)

candidate=2 count=1 (reset)

Result: 2 ✅

```

Step 4 — Algorithm:

1. Set candidate = first element, count = 0

2. For each element: if count=0 → new candidate; same as candidate → count++; different → count--

3. Return candidate

Step 5 — Edge cases:

- Problem guarantees majority exists; if it didn't, we'd need a verification pass

function majorityElement(array $nums): int {
    $candidate = 0;
    $count     = 0;

    foreach ($nums as $num) {
        if ($count === 0) $candidate = $num;
        $count += ($num === $candidate) ? 1 : -1;
    }

    return $candidate;
}

echo majorityElement([3,2,3]);         // 3
echo majorityElement([2,2,1,1,1,2,2]); // 2

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

---

Q9. Jump Game [M][FB]

Problem: Each element is max jump length from that position. Can you reach the last index?

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Greedy — track the furthest reachable position as you scan.

Step 2 — Brute force:

Recursion/DFS exploring all jump paths → exponential time.

Step 3 — Greedy insight:

You don't need to track every path. Just track maxReach = the furthest index you can reach from any previously visited position. If you encounter an index beyond maxReach, you're stuck.

Step 4 — Algorithm:

1. maxReach = 0

2. For each index i: if i > maxReach → return false (can't reach here)

3. Update maxReach = max(maxReach, i + nums[i])

4. If loop completes → return true

Step 5 — Edge cases:

- Single element → always reachable

- Zero at some position: only a problem if maxReach can't surpass it

function canJump(array $nums): bool {
    $maxReach = 0;

    foreach ($nums as $i => $jump) {
        if ($i > $maxReach) return false; // stuck!
        $maxReach = max($maxReach, $i + $jump);
    }

    return true;
}

var_dump(canJump([2,3,1,1,4])); // true
var_dump(canJump([3,2,1,0,4])); // false (stuck at index 3)

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

---

Q10. Next Permutation [M][FB]

Problem: Rearrange array to next lexicographically greater permutation. In-place.

---

🧠 How to Approach This

Step 1 — Understand the goal:

Like incrementing a number — find the rightmost "digit" that can be increased, increase it minimally, then make everything after it as small as possible.

Step 2 — Three-step algorithm:

Step A — Find the pivot:

Scan from right. Find first position i where arr[i] < arr[i+1]. This is the element that needs to increase.

Step B — Find the swap target:

Find the rightmost element to the right of i that is greater than arr[i]. This is the smallest possible increase.

Step C — Swap and reverse:

Swap pivot with swap target. Then reverse everything after position i (to get smallest possible suffix).

```

[1, 2, 3] → find i=1 (arr[1]=2 < arr[2]=3) → swap 2 and 3 → [1,3,2]

↑ pivot → no suffix to reverse

[1, 3, 2] → find i=0 (arr[0]=1 < arr[1]=3) → swap 1 and 2 → [2,3,1]

↑ pivot → reverse [3,1] → [2,1,3]

```

Step 5 — Edge cases:

- Descending array (e.g. [3,2,1]): no pivot found → reverse entire array → [1,2,3]

function nextPermutation(array &$nums): void {
    $n = count($nums);
    $i = $n - 2;

    // Step A: Find pivot (first descent from right)
    while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;

    if ($i >= 0) {
        // Step B: Find smallest element > pivot on its right
        $j = $n - 1;
        while ($nums[$j] <= $nums[$i]) $j--;
        [$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]]; // swap
    }

    // Step C: Reverse suffix (i+1 to end)
    $left = $i + 1; $right = $n - 1;
    while ($left < $right) {
        [$nums[$left], $nums[$right]] = [$nums[$right], $nums[$left]];
        $left++; $right--;
    }
}

$a = [1,2,3]; nextPermutation($a); print_r($a); // [1,3,2]
$a = [3,2,1]; nextPermutation($a); print_r($a); // [1,2,3]
$a = [1,1,5]; nextPermutation($a); print_r($a); // [1,5,1]

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

---

Q11. Spiral Matrix [M]

Problem: Return elements of an m×n matrix in spiral order (clockwise).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Simulation with shrinking boundaries. Peel off the outer "ring" of the matrix, then move to the next ring.

Step 2 — Key insight:

Maintain four boundary pointers: top, bottom, left, right. Move in order: right → down → left → up. After each direction, shrink that boundary inward.

Step 3 — Algorithm:

1. top=0, bottom=rows-1, left=0, right=cols-1

2. While top <= bottom AND left <= right:

- Traverse top row left→right, then top++

- Traverse right column top→bottom, then right--

- If top <= bottom: traverse bottom row right→left, then bottom--

- If left <= right: traverse left column bottom→top, then left++

Step 4 — Edge cases:

- Single row or single column: check boundaries before traversing inward

- 1×1 matrix: just return the single element

function spiralOrder(array $matrix): array {
    $result = [];
    if (empty($matrix)) return $result;

    $top = 0; $bottom = count($matrix) - 1;
    $left = 0; $right  = count($matrix[0]) - 1;

    while ($top <= $bottom && $left <= $right) {
        for ($i = $left;   $i <= $right;  $i++) $result[] = $matrix[$top][$i];  $top++;
        for ($i = $top;    $i <= $bottom; $i++) $result[] = $matrix[$i][$right]; $right--;
        if ($top <= $bottom) {
            for ($i = $right; $i >= $left;   $i--) $result[] = $matrix[$bottom][$i]; $bottom--;
        }
        if ($left <= $right) {
            for ($i = $bottom; $i >= $top; $i--) $result[] = $matrix[$i][$left]; $left++;
        }
    }

    return $result;
}

print_r(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]));
// [1,2,3,6,9,8,7,4,5]

Time: O(m×n) | Space: O(1) extra

---

Q12. Rotate Matrix 90 Degrees [M][FB]

Problem: Rotate an n×n matrix clockwise by 90° in-place.

---

🧠 How to Approach This

Step 1 — Observation:

Extra space: copy to new matrix is O(n²) space — interviewer wants O(1).

Step 2 — Mathematical trick:

Rotating 90° clockwise = Transpose + Reverse each row.

Proof: element at [row][col] goes to [col][n-1-row] after 90° clockwise rotation.

Transpose puts it at [col][row], then reversing rows puts it at [col][n-1-row]. ✓

```

Original: Transpose: Reversed rows:

1 2 3 1 4 7 7 4 1

4 5 6 → 2 5 8 → 8 5 2 (rotated 90° CW)

7 8 9 3 6 9 9 6 3

```

Step 3 — Algorithm:

1. Transpose: swap matrix[i][j] with matrix[j][i] for all i < j

2. Reverse each row: array_reverse()

Step 4 — Edge cases:

- Non-square matrix cannot be done in-place this way (use extra space)

- 1×1 matrix: no-op

function rotateMatrix(array &$matrix): void {
    $n = count($matrix);

    // Step 1: Transpose (only upper triangle)
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            [$matrix[$i][$j], $matrix[$j][$i]] = [$matrix[$j][$i], $matrix[$i][$j]];
        }
    }

    // Step 2: Reverse each row
    foreach ($matrix as &$row) {
        $row = array_reverse($row);
    }
}

$m = [[1,2,3],[4,5,6],[7,8,9]];
rotateMatrix($m);
// [[7,4,1],[8,5,2],[9,6,3]]

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

---

Q13. Longest Consecutive Sequence [M][FB]

Problem: Unsorted array. Find length of longest consecutive sequence. O(n) time.

---

🧠 How to Approach This

Step 1 — Brute force:

Sort the array, then scan for consecutive elements. O(n log n) — question asks for O(n).

Step 2 — Hash Set insight:

Put all numbers in a Set for O(1) lookup. For each number n, only START counting a sequence if (n-1) is NOT in the set — meaning n is the beginning of a new sequence. Then count how far n, n+1, n+2... continues.

Why this is O(n): Each number is visited at most twice — once when checking if it's a start, once when counting from a start.

Step 3 — Algorithm:

1. Add all numbers to a hash set

2. For each num: if (num-1) NOT in set → it's a sequence start

3. Count: while (num + len) in set → len++

4. Update maxLen

Step 4 — Edge cases:

- Duplicates: set handles them (only unique values)

- Negative numbers: works fine, just check n-1

function longestConsecutive(array $nums): int {
    $numSet = array_flip($nums); // flip for O(1) isset() lookup
    $longest = 0;

    foreach ($numSet as $num => $_) {
        if (!isset($numSet[$num - 1])) { // num is a sequence START
            $length = 1;
            while (isset($numSet[$num + $length])) $length++;
            $longest = max($longest, $length);
        }
    }

    return $longest;
}

echo longestConsecutive([100,4,200,1,3,2]); // 4  [1,2,3,4]
echo longestConsecutive([0,3,7,2,5,8,4,6,0,1]); // 9

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

---

Q14. Merge Intervals [M][FB][L]

Problem: Array of [start,end] intervals. Merge all overlapping intervals.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Sorting + greedy merge. Once sorted by start time, overlapping intervals are adjacent.

Step 2 — Key insight:

Two intervals [a,b] and [c,d] overlap if c <= b (next starts before current ends). Merged interval = [a, max(b,d)].

Step 3 — Algorithm:

1. Sort intervals by start time

2. Initialize result with first interval

3. For each subsequent interval:

- If it overlaps with last result interval → extend the end

- Otherwise → add as new interval

Step 4 — Edge cases:

- Adjacent intervals [1,2] and [2,3] → overlap? Depends on definition (usually yes, merge to [1,3])

- Single interval → return as-is

- Already sorted → sort is still needed (don't assume)

Laravel use case: Merging date ranges for booking/calendar systems

function mergeIntervals(array $intervals): array {
    if (empty($intervals)) return [];

    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]); // sort by start

    $merged = [$intervals[0]];

    for ($i = 1; $i < count($intervals); $i++) {
        $last    = &$merged[count($merged) - 1];
        $current = $intervals[$i];

        if ($current[0] <= $last[1]) {
            $last[1] = max($last[1], $current[1]); // MERGE: extend end
        } else {
            $merged[] = $current;                   // NO overlap: add new
        }
    }

    return $merged;
}

print_r(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

print_r(mergeIntervals([[1,4],[4,5]]));
// [[1,5]]

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

---

Q15. Group Anagrams [M][FB]

Problem: Group strings that are anagrams of each other.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Grouping by a canonical key. All anagrams produce the same key.

Step 2 — Key insight:

If you sort the characters of a word, all anagrams produce the same sorted string. Use this sorted string as the hash map key.

Example: "eat" → sorted → "aet", "tea" → sorted → "aet", "ate" → sorted → "aet" → same group!

Step 3 — Algorithm:

1. For each string: sort its characters to get the key

2. Group strings by their key in a hash map

3. Return all groups

Step 4 — Edge cases:

- Empty string: "" → still valid, key = ""

- Single character strings: each is its own anagram group

- Unicode characters: sort by code point (str_split + sort works)

function groupAnagrams(array $strs): array {
    $groups = [];

    foreach ($strs as $str) {
        $chars = str_split($str);
        sort($chars);
        $key = implode('', $chars);
        $groups[$key][] = $str;
    }

    return array_values($groups);
}

print_r(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

Time: O(n · k · log k) where k = max string length | Space: O(n·k)

---

Hard Level

---

Q16. First Missing Positive [H][FB]

Problem: Find the smallest missing positive integer. O(n) time, O(1) space.

---

🧠 How to Approach This

Step 1 — Key observation:

The answer must be in range [1, n+1] (where n = array length). Why? Because we have n numbers; if they're 1..n, answer is n+1; otherwise some value in 1..n is missing.

Step 2 — Cyclic Sort approach:

Since answer ∈ [1, n+1], we can use the array itself as storage. Place each number v at index v-1 (if v is in range 1..n).

After placement, scan: first index where arr[i] ≠ i+1 → answer is i+1.

Step 3 — Algorithm:

1. For each index i: while arr[i] is in [1,n] AND arr[arr[i]-1] ≠ arr[i]: swap arr[i] to its correct position

2. After all swaps: scan for first i where arr[i] ≠ i+1 → return i+1

3. If all correct → return n+1

Step 4 — Edge cases:

- Negatives and zeros: skip them (only care about positives in range)

- Duplicates: the while condition arr[arr[i]-1] ≠ arr[i] prevents infinite swap loops

```

[3,4,-1,1]

Place 1 at index 0: [1,4,-1,3]

Place 4 at index 3: [1,3,-1,4] (swap 4 to pos 3, 3 comes to pos 1)

Place 3 at index 2: [1,-1,3,4] (wait, let me redo)

→ Scan: arr[1]=-1 ≠ 2 → answer is 2 ✅

```

function firstMissingPositive(array $nums): int {
    $n = count($nums);

    // Cyclic sort: place each number at its correct index
    for ($i = 0; $i < $n; $i++) {
        while ($nums[$i] > 0 && $nums[$i] <= $n && $nums[$nums[$i] - 1] !== $nums[$i]) {
            $idx = $nums[$i] - 1;
            [$nums[$i], $nums[$idx]] = [$nums[$idx], $nums[$i]];
        }
    }

    // Find first mismatch
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] !== $i + 1) return $i + 1;
    }

    return $n + 1; // all [1..n] present
}

echo firstMissingPositive([3,4,-1,1]);  // 2
echo firstMissingPositive([1,2,0]);     // 3
echo firstMissingPositive([7,8,9,11]);  // 1

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

---

Q17. Median of Two Sorted Arrays [H][FB]

Problem: Find median of two sorted arrays in O(log(m+n)) time.

---

🧠 How to Approach This

Step 1 — Understand the goal:

Median splits the combined array into two equal halves: everything in the left half ≤ everything in the right half.

Step 2 — Brute force:

Merge both arrays, find middle. O(m+n) time — question asks O(log(m+n)).

Step 3 — Binary search on partitions:

Use binary search to find the right partition point in the smaller array. Once we know how many elements from nums1 are in the "left half", we know how many from nums2 must be there too.

The partition is valid when:

- maxLeft1 <= minRight2 (left side of nums1 ≤ right side of nums2)

- maxLeft2 <= minRight1 (left side of nums2 ≤ right side of nums1)

Step 4 — Algorithm:

1. Ensure nums1 is the shorter array (binary search on shorter)

2. Binary search on partition point in nums1 (0 to m)

3. For each partition: compute nums2 partition as half - partX

4. Check boundary values → adjust binary search

5. Once found: median = max(left halves) for odd total, average of max-left and min-right for even

Step 5 — Edge cases:

- Partition at edge (px=0 or px=m) → use -∞ or +∞ as boundary

- Odd vs even total elements → different median formula

function findMedianSortedArrays(array $nums1, array $nums2): float {
    if (count($nums1) > count($nums2)) {
        return findMedianSortedArrays($nums2, $nums1); // ensure nums1 is shorter
    }

    $m = count($nums1);
    $n = count($nums2);
    $half = intdiv($m + $n, 2);

    $left = 0; $right = $m;

    while ($left <= $right) {
        $px = intdiv($left + $right, 2); // partition nums1
        $py = $half - $px;               // partition nums2

        $maxL1 = $px > 0 ? $nums1[$px-1] : PHP_INT_MIN;
        $minR1 = $px < $m ? $nums1[$px]  : PHP_INT_MAX;
        $maxL2 = $py > 0 ? $nums2[$py-1] : PHP_INT_MIN;
        $minR2 = $py < $n ? $nums2[$py]  : PHP_INT_MAX;

        if ($maxL1 <= $minR2 && $maxL2 <= $minR1) {
            if (($m + $n) % 2 === 1) return (float) min($minR1, $minR2);
            return (max($maxL1, $maxL2) + min($minR1, $minR2)) / 2.0;
        } elseif ($maxL1 > $minR2) {
            $right = $px - 1; // too many from nums1 in left half
        } else {
            $left = $px + 1;  // too few from nums1 in left half
        }
    }

    return 0.0;
}

echo findMedianSortedArrays([1,3], [2]);   // 2.0
echo findMedianSortedArrays([1,2], [3,4]); // 2.5

Time: O(log(min(m,n))) | Space: O(1)

---

Q18. Find Longest Subarray with Equal 0s and 1s [M]

Problem: Binary array. Find longest subarray with equal number of 0s and 1s.

---

🧠 How to Approach This

Step 1 — Transformation trick:

Replace 0 with -1. Now "equal 0s and 1s" becomes "subarray sum = 0".

Step 2 — Prefix sum insight:

If prefix sum at index i equals prefix sum at index j (j > i), then the subarray [i+1..j] has sum 0 (equal 0s and 1s in original).

Step 3 — Algorithm:

1. Replace all 0s with -1

2. Use prefix sum + hash map: map[prefix_sum] = first_index_seen

3. If current prefix sum was seen before: subarray length = i - map[prefix_sum]

4. Initialize map with {0: -1} (empty prefix)

Step 4 — Edge cases:

- Initialize map[0] = -1 (handles subarrays starting from index 0)

- Don't overwrite an existing prefix sum in map (keep first occurrence for max length)

function findMaxLengthEqualZeroOne(array $nums): int {
    $nums = array_map(fn($n) => $n === 0 ? -1 : 1, $nums); // 0→-1

    $seen = [0 => -1]; // prefixSum → first index it appeared
    $sum  = 0;
    $max  = 0;

    foreach ($nums as $i => $num) {
        $sum += $num;
        if (isset($seen[$sum])) {
            $max = max($max, $i - $seen[$sum]);
        } else {
            $seen[$sum] = $i; // store only first occurrence
        }
    }

    return $max;
}

echo findMaxLengthEqualZeroOne([0,1]);         // 2
echo findMaxLengthEqualZeroOne([0,1,0,0,1,1,0]); // 6

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

---

Additional Medium Questions

---

Q19. Maximum Product Subarray [M][FB]

Problem: Find the contiguous subarray with the largest product.

---

🧠 How to Approach This

Step 1 — Why this is tricky:

Negative × negative = positive! A very negative subarray can become the maximum if multiplied by another negative. So we need to track BOTH max and min at each step.

Step 2 — Modified Kadane's for products:

- Track both maxProduct and minProduct ending at current position

- At each step: new max = max(num, maxPrev×num, minPrev×num)

- At each step: new min = min(num, maxPrev×num, minPrev×num)

Step 3 — Edge cases:

- Zero resets both max and min (no carry-over across zeros)

- Single negative number: max product = that number

function maxProduct(array $nums): int {
    $maxProd = $nums[0];
    $minProd = $nums[0];
    $result  = $nums[0];

    for ($i = 1; $i < count($nums); $i++) {
        $n = $nums[$i];
        $tempMax = max($n, $maxProd * $n, $minProd * $n);
        $minProd = min($n, $maxProd * $n, $minProd * $n);
        $maxProd = $tempMax;
        $result  = max($result, $maxProd);
    }

    return $result;
}

echo maxProduct([2,3,-2,4]);   // 6  (subarray [2,3])
echo maxProduct([-2,0,-1]);    // 0
echo maxProduct([-2,3,-4]);    // 24 (entire array)

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

---

Q20. Trapping Rain Water [H][FB]

Problem: Array of wall heights. How much water can be trapped after rain?

---

🧠 How to Approach This

Step 1 — Understand what traps water:

Water above position i is: min(max_height_left_of_i, max_height_right_of_i) - height[i].

If this is negative, no water (wall is taller than bounds).

Step 2 — Brute force:

For each position, scan left for max height and scan right for max height. O(n²).

Step 3 — Pre-compute arrays:

Pre-compute leftMax[] and rightMax[] arrays. O(n) time, O(n) space.

Step 4 — Two Pointers (O(1) space):

Use two pointers, process from the side with the smaller maximum (that side's bound is certain).

Algorithm:

1. L=0, R=n-1, leftMax=0, rightMax=0, water=0

2. While L < R:

- If height[L] < height[R]: process left side (bound = leftMax)

- Else: process right side (bound = rightMax)

Step 5 — Edge cases:

- Heights of 0: valid wall

- Monotonically increasing/decreasing: no water trapped

function trapRainwater(array $height): int {
    $left = 0; $right = count($height) - 1;
    $leftMax = 0; $rightMax = 0;
    $water = 0;

    while ($left < $right) {
        if ($height[$left] < $height[$right]) {
            if ($height[$left] >= $leftMax) {
                $leftMax = $height[$left]; // new left max, no water yet
            } else {
                $water += $leftMax - $height[$left]; // water fills in
            }
            $left++;
        } else {
            if ($height[$right] >= $rightMax) {
                $rightMax = $height[$right];
            } else {
                $water += $rightMax - $height[$right];
            }
            $right--;
        }
    }

    return $water;
}

echo trapRainwater([0,1,0,2,1,0,1,3,2,1,2,1]); // 6
echo trapRainwater([4,2,0,3,2,5]);               // 9

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

---

Q21. 3Sum — All Triplets Summing to Zero [M][FB]

Problem: Find all unique triplets in the array that sum to zero.

---

🧠 How to Approach This

Step 1 — Brute force:

O(n³) — three nested loops. Too slow.

Step 2 — Sort + Two Pointers:

Sort the array. For each element nums[i], use two pointers on the rest to find pairs summing to -nums[i].

Step 3 — Avoiding duplicates:

Skip duplicate values for i (if same as i-1, skip). After finding a triplet, skip duplicates for left and right pointers too.

Step 4 — Algorithm:

1. Sort array

2. For each i from 0 to n-3:

- Skip if nums[i] == nums[i-1] (duplicate)

- Two pointers: L=i+1, R=n-1

- If sum==0: add triplet, skip duplicates, move both pointers

- If sum<0: L++ (need bigger)

- If sum>0: R-- (need smaller)

Step 5 — Edge cases:

- Less than 3 elements: return empty

- All zeros [0,0,0]: valid triplet

function threeSum(array $nums): array {
    sort($nums);
    $result = [];
    $n = count($nums);

    for ($i = 0; $i < $n - 2; $i++) {
        if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue; // skip duplicate i

        $left = $i + 1;
        $right = $n - 1;

        while ($left < $right) {
            $sum = $nums[$i] + $nums[$left] + $nums[$right];

            if ($sum === 0) {
                $result[] = [$nums[$i], $nums[$left], $nums[$right]];
                while ($left < $right && $nums[$left] === $nums[$left + 1]) $left++;
                while ($left < $right && $nums[$right] === $nums[$right - 1]) $right--;
                $left++; $right--;
            } elseif ($sum < 0) {
                $left++;
            } else {
                $right--;
            }
        }
    }

    return $result;
}

print_r(threeSum([-1,0,1,2,-1,-4])); // [[-1,-1,2],[-1,0,1]]

Time: O(n²) | Space: O(1) extra

---

Q22. Subarray Sum Equals K [M][FB]

Problem: Count the number of contiguous subarrays that sum to k.

---

🧠 How to Approach This

Step 1 — Brute force:

O(n²) — compute sum for every subarray. Interviewer wants better.

Step 2 — Prefix sum insight:

If prefix[j] - prefix[i] = k, then subarray [i+1..j] sums to k.

Equivalently: look for how many previous prefix sums equal (current_prefix - k).

Step 3 — Algorithm:

1. Use hash map: count of each prefix sum seen so far

2. Initialize map with {0: 1} (empty prefix)

3. For each element: add to running sum; check if (sum - k) exists in map

4. Add map[sum - k] to count; update map[sum]++

Step 4 — Edge cases:

- k can be 0 or negative

- Multiple subarrays can end at same position

- Initialize map[0]=1 handles subarrays starting from index 0

function subarraySum(array $nums, int $k): int {
    $prefixCounts = [0 => 1]; // sum => frequency
    $sum = 0;
    $count = 0;

    foreach ($nums as $num) {
        $sum += $num;
        $count += $prefixCounts[$sum - $k] ?? 0;
        $prefixCounts[$sum] = ($prefixCounts[$sum] ?? 0) + 1;
    }

    return $count;
}

echo subarraySum([1,1,1], 2);   // 2  ([1,1] twice)
echo subarraySum([1,2,3], 3);   // 2  ([1,2] and [3])

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

---

Q23. Product of Array Except Self [M][FB]

Problem: For each index, compute product of all OTHER elements. No division, O(n).

---

🧠 How to Approach This

Step 1 — Why no division:

Division fails with zeros (division by zero). Interviewer tests if you know the left×right pass trick.

Step 2 — Left×Right pass:

For each index i:

- Left product = product of all elements to the LEFT of i

- Right product = product of all elements to the RIGHT of i

- Answer[i] = left × right

Step 3 — Algorithm (O(1) extra space):

1. Pass 1 (left to right): result[i] = product of all elements before i

2. Pass 2 (right to left): multiply result[i] by running right product

Step 4 — Edge cases:

- Array with one zero: all positions except zero-position get 0

- Two zeros: all positions get 0

function productExceptSelf(array $nums): array {
    $n = count($nums);
    $result = array_fill(0, $n, 1);

    // Left pass: result[i] = product of all elements before i
    $leftProd = 1;
    for ($i = 0; $i < $n; $i++) {
        $result[$i] = $leftProd;
        $leftProd *= $nums[$i];
    }

    // Right pass: multiply result[i] by product of all elements after i
    $rightProd = 1;
    for ($i = $n - 1; $i >= 0; $i--) {
        $result[$i] *= $rightProd;
        $rightProd *= $nums[$i];
    }

    return $result;
}

print_r(productExceptSelf([1,2,3,4])); // [24,12,8,6]
print_r(productExceptSelf([-1,1,0,-3,3])); // [0,0,9,0,0]

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

---

Q24. Container With Most Water [M][FB]

Problem: Array of wall heights. Find two lines that form a container holding the most water.

---

🧠 How to Approach This

Step 1 — Brute force:

Check every pair of walls. O(n²). Too slow.

Step 2 — Two pointers insight:

Water = min(height[L], height[R]) × (R - L). To maximize this:

- Width decreases as we move pointers inward

- So we should move the pointer with the SHORTER height (keeping the taller one is our only chance of getting more water with smaller width)

Step 3 — Algorithm:

1. L=0, R=n-1, maxWater=0

2. While L < R:

- Compute water = min(height[L], height[R]) × (R-L)

- Update maxWater

- Move the SHORTER pointer inward

Step 4 — Edge cases:

- Equal heights: move either pointer (move both is also fine)

- All same heights: move from outside in, shrink width

function maxWaterContainer(array $height): int {
    $left = 0; $right = count($height) - 1;
    $maxWater = 0;

    while ($left < $right) {
        $water = min($height[$left], $height[$right]) * ($right - $left);
        $maxWater = max($maxWater, $water);

        if ($height[$left] < $height[$right]) {
            $left++;  // shorter left wall can never do better — move it
        } else {
            $right--;
        }
    }

    return $maxWater;
}

echo maxWaterContainer([1,8,6,2,5,4,8,3,7]); // 49
echo maxWaterContainer([1,1]);               // 1

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

---

Q25. Word Count from String Array [E][L]

Real Laravel/PHP scenario: Count word frequencies from a collection of strings.

---

🧠 How to Approach This

Pattern: Hash map frequency counter. Very common in Laravel data processing.

// Basic PHP
function wordCount(array $words): array {
    return array_count_values($words);
}

// Case-insensitive
function wordCountInsensitive(array $words): array {
    $words = array_map('strtolower', $words);
    return array_count_values($words);
}

// Top N most frequent words
function topNWords(array $words, int $n): array {
    $counts = array_count_values(array_map('strtolower', $words));
    arsort($counts); // sort by value descending
    return array_slice($counts, 0, $n, true);
}

// Laravel Collection equivalent
$words = collect(['PHP', 'php', 'JS', 'PHP', 'Laravel', 'js']);
$topWords = $words
    ->map(fn($w) => strtolower($w))
    ->countBy()
    ->sortByDesc(fn($count) => $count)
    ->take(3);

---

Q26. Sliding Window Maximum [H][FB]

Problem: Given array nums and window size k, return the max of each sliding window.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Maximum in every window of size k = Monotonic Deque. Key signals: "max/min in sliding window".

Step 2 — Brute force:

For each of n-k+1 windows, find max → O(n×k). Too slow for large k.

Step 3 — Monotonic Deque insight:

Maintain a deque of indices in decreasing order of their values. Front = current window max. When a new element arrives, remove all back elements smaller than it (they will never be max while this element is in the window).

Step 4 — Algorithm:

1. For each right: remove front if index < right-k+1 (out of window)

2. Remove back while nums[back] <= nums[right]

3. Push right to back; if right >= k-1: result[] = nums[front]

Step 5 — Edge cases:

- k=1: each element is its own max

- k=n: single window, max of entire array

function maxSlidingWindow(array $nums, int $k): array {
    $result = [];
    $deque  = []; // stores indices

    for ($i = 0; $i < count($nums); $i++) {
        // Remove indices outside current window
        if (!empty($deque) && $deque[0] < $i - $k + 1) {
            array_shift($deque);
        }
        // Remove back elements smaller than current (they're useless)
        while (!empty($deque) && $nums[end($deque)] <= $nums[$i]) {
            array_pop($deque);
        }
        $deque[] = $i;
        // Record max once first full window is complete
        if ($i >= $k - 1) {
            $result[] = $nums[$deque[0]];
        }
    }
    return $result;
}

print_r(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3)); // [3,3,5,5,6,7]

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

---

Q27. Next Greater Element [M][FB]

Problem: For each element, find the next element to its right that is greater. Return -1 if none.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"Next greater/smaller" = Monotonic Stack (decreasing). Elements wait in the stack for their answer.

Step 2 — Brute force:

For each element scan right → O(n²). Too slow.

Step 3 — Monotonic Stack insight:

Keep a stack of indices whose "next greater" is unknown. When you reach element X, pop all stack elements smaller than X — X is their answer. Remaining stack at the end → answer is -1.

Step 4 — Algorithm:

1. Fill result with -1

2. Stack stores indices waiting for next greater

3. For each i: while stack not empty AND nums[top] < nums[i] → result[pop] = nums[i]

4. Push i to stack

Step 5 — Edge cases:

- Decreasing [5,4,3,2,1]: all -1

- Increasing [1,2,3,4,5]: each gets next, last gets -1

function nextGreaterElement(array $nums): array {
    $result = array_fill(0, count($nums), -1);
    $stack  = []; // indices waiting for their next greater

    for ($i = 0; $i < count($nums); $i++) {
        while (!empty($stack) && $nums[end($stack)] < $nums[$i]) {
            $idx = array_pop($stack);
            $result[$idx] = $nums[$i];
        }
        $stack[] = $i;
    }
    return $result;
}

print_r(nextGreaterElement([2,1,2,4,3])); // [4,2,4,-1,-1]

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

---

Q28. Daily Temperatures [M][FB]

Problem: Return an array where each element is the number of days until a warmer temperature. 0 if never.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

"How many days until warmer" = Next Greater Element variant, but record the distance instead of the value.

Step 2 — Monotonic Stack:

Stack stores indices. When today is warmer than what's on top, pop and record i - popped_index as the wait.

Step 3 — Edge cases:

- Last day: always 0 (nothing after it — stays in stack, result defaults to 0)

function dailyTemperatures(array $temps): array {
    $result = array_fill(0, count($temps), 0);
    $stack  = [];

    for ($i = 0; $i < count($temps); $i++) {
        while (!empty($stack) && $temps[end($stack)] < $temps[$i]) {
            $idx          = array_pop($stack);
            $result[$idx] = $i - $idx; // days to wait
        }
        $stack[] = $i;
    }
    return $result;
}

print_r(dailyTemperatures([73,74,75,71,69,72,76,73])); // [1,1,4,2,1,1,0,0]

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

---

Q29. Find the Duplicate Number [M][FB]

Problem: Array of n+1 integers with values 1–n. Exactly one value appears twice. Find it. No array modification, O(1) space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Values 1..n in an array of n+1 elements = treat indices as "next pointers" in a linked list → Floyd's Cycle Detection.

Step 2 — Brute force:

Hash set O(n) space, or sort O(n log n). Neither satisfies O(1) space + no modification.

Step 3 — Floyd's insight:

If value v is duplicated, two indices point to nums[v], creating a cycle. Find the cycle entry = duplicate.

Step 4 — Algorithm:

- Phase 1: slow moves 1 step, fast moves 2 steps. They meet inside the cycle.

- Phase 2: reset fast to start. Both move 1 step. They meet at the cycle entrance = duplicate.

Step 5 — Edge cases:

- Guaranteed exactly one duplicate per problem constraints

function findDuplicate(array $nums): int {
    $slow = $nums[0];
    $fast = $nums[0];

    // Phase 1: detect cycle
    do {
        $slow = $nums[$slow];
        $fast = $nums[$nums[$fast]];
    } while ($slow !== $fast);

    // Phase 2: find cycle entrance
    $fast = $nums[0];
    while ($slow !== $fast) {
        $slow = $nums[$slow];
        $fast = $nums[$fast];
    }
    return $slow;
}

echo findDuplicate([1,3,4,2,2]); // 2
echo findDuplicate([3,1,3,4,2]); // 3

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

---

Q30. Longest Increasing Subsequence (LIS) [M][FB]

Problem: Find the length of the longest strictly increasing subsequence.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Longest subsequence = DP. For O(n log n): patience sorting (binary search on tails array).

Step 2 — DP O(n²):

dp[i] = LIS ending at index i. For each j < i where nums[j] < nums[i]: dp[i] = max(dp[i], dp[j]+1).

Step 3 — Patience sort O(n log n):

Maintain tails[] where tails[i] = smallest ending element of all increasing subsequences of length i+1. Binary search to find where each new number fits in tails.

Step 4 — Edge cases:

- All decreasing: LIS = 1

- All same: LIS = 1 (strictly increasing)

function lengthOfLIS(array $nums): int {
    $tails = [];

    foreach ($nums as $num) {
        // Binary search: find first tail >= num
        $lo = 0;
        $hi = count($tails);
        while ($lo < $hi) {
            $mid = intdiv($lo + $hi, 2);
            if ($tails[$mid] < $num) $lo = $mid + 1;
            else $hi = $mid;
        }
        $tails[$lo] = $num; // replace or extend tails
    }
    return count($tails);
}

echo lengthOfLIS([10,9,2,5,3,7,101,18]); // 4  → [2,3,7,101]
echo lengthOfLIS([0,1,0,3,2,3]);           // 4  → [0,1,2,3]

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

---

Q31. Gas Station [M][FB]

Problem: N gas stations in a circle. gas[i] fuel available, cost[i] to travel to next. Find start station to complete the circuit, or -1.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Circular path with net gain/loss at each station = Greedy (one-pass).

Step 2 — Key insight 1:

If total gas >= total cost, a solution is guaranteed to exist (and it's unique).

Step 3 — Key insight 2:

If you run out at station X starting from S, no station between S and X can be a valid start (they have less surplus). Reset start to X+1.

Step 4 — Algorithm:

1. tank=0, total=0, start=0

2. For each i: diff = gas[i]-cost[i]; tank += diff; total += diff

3. If tank < 0: start = i+1, tank = 0

4. Return total >= 0 ? start : -1

Step 5 — Edge cases:

- Total gas < total cost: impossible (return -1)

- Single station: valid only if gas[0] >= cost[0]

function canCompleteCircuit(array $gas, array $cost): int {
    $total = 0;
    $tank  = 0;
    $start = 0;

    for ($i = 0; $i < count($gas); $i++) {
        $diff   = $gas[$i] - $cost[$i];
        $tank  += $diff;
        $total += $diff;

        if ($tank < 0) {         // can't continue from current start
            $start = $i + 1;
            $tank  = 0;
        }
    }
    return $total >= 0 ? $start : -1;
}

echo canCompleteCircuit([1,2,3,4,5], [3,4,5,1,2]); // 3
echo canCompleteCircuit([2,3,4],     [3,4,3]);      // -1

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

---

Q32. Candy Distribution [H][FB]

Problem: N children in a row, each with a rating. Give everyone ≥ 1 candy. Higher-rated child must get MORE than any adjacent lower-rated neighbor. Minimize total candies.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Two constraints (left neighbor, right neighbor) = Two-pass greedy. Each pass enforces one direction.

Step 2 — Why one pass fails:

Left-to-right handles "greater than left neighbor". We also need "greater than right neighbor" — requires a right-to-left pass.

Step 3 — Algorithm:

- Pass 1 (L→R): if ratings[i] > ratings[i-1], candies[i] = candies[i-1] + 1, else candies[i] = 1

- Pass 2 (R→L): if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1]+1)

- Take the max at each step to satisfy BOTH directions simultaneously.

Step 4 — Edge cases:

- All equal ratings: 1 candy each

- Strictly increasing: 1,2,3,...,n

- Strictly decreasing: n,...,2,1

function candy(array $ratings): int {
    $n       = count($ratings);
    $candies = array_fill(0, $n, 1);

    // Pass 1: left to right
    for ($i = 1; $i < $n; $i++) {
        if ($ratings[$i] > $ratings[$i - 1]) {
            $candies[$i] = $candies[$i - 1] + 1;
        }
    }

    // Pass 2: right to left
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($ratings[$i] > $ratings[$i + 1]) {
            $candies[$i] = max($candies[$i], $candies[$i + 1] + 1);
        }
    }

    return array_sum($candies);
}

echo candy([1, 0, 2]); // 5  → [2,1,2]
echo candy([1, 2, 2]); // 4  → [1,2,1]

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

---

Q33. Meeting Rooms II [M][FB]

Problem: Given meeting intervals [start, end], find the minimum number of rooms required.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Minimum rooms = maximum overlapping intervals at any point = Sweep Line.

Step 2 — Key insight:

Separate start and end times. Sort both independently. Use two pointers: rooms++ when a new meeting starts, rooms-- when one ends.

Step 3 — Algorithm:

1. Sort starts[], sort ends[] separately

2. s=0, e=0, rooms=0, maxRooms=0

3. While s < n: if starts[s] < ends[e] → rooms++, s++; else → rooms--, e++

4. maxRooms = max(maxRooms, rooms) each step

Step 4 — Edge cases:

- No intervals: 0 rooms

- All non-overlapping: 1 room

- All at same time: n rooms

function minMeetingRooms(array $intervals): int {
    if (empty($intervals)) return 0;

    $starts = array_column($intervals, 0);
    $ends   = array_column($intervals, 1);
    sort($starts);
    sort($ends);

    $rooms = 0;
    $maxRooms = 0;
    $s = 0;
    $e = 0;

    while ($s < count($intervals)) {
        if ($starts[$s] < $ends[$e]) {
            $rooms++;
            $s++;
        } else {
            $rooms--;
            $e++;
        }
        $maxRooms = max($maxRooms, $rooms);
    }
    return $maxRooms;
}

echo minMeetingRooms([[0,30],[5,10],[15,20]]); // 2
echo minMeetingRooms([[7,10],[2,4]]);           // 1

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

---

Q34. K Closest Points to Origin [M][FB]

Problem: Given 2D points, find the K closest to the origin (0,0).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

K smallest/closest from N items = Max-Heap of size K (discard farther points as you go).

Step 2 — Simple approach:

Sort all by distance², take first k → O(n log n).

Step 3 — Optimal heap O(n log k):

Maintain a max-heap of size k. For each point: if heap size < k OR current distance < heap max → insert (remove max if heap overflows).

Step 4 — Distance formula:

dist² = x² + y² (no sqrt needed, comparisons are valid without it)

Step 5 — Edge cases:

- k=n: return all points

function kClosest(array $points, int $k): array {
    // O(n log n) sort approach
    usort($points, fn($a, $b) => ($a[0]**2 + $a[1]**2) <=> ($b[0]**2 + $b[1]**2));
    return array_slice($points, 0, $k);
}

// O(n log k) max-heap approach
function kClosestHeap(array $points, int $k): array {
    $heap = new SplMaxHeap();

    foreach ($points as $point) {
        $dist = $point[0]**2 + $point[1]**2;
        $heap->insert([$dist, $point]);
        if ($heap->count() > $k) {
            $heap->extract(); // remove farthest
        }
    }

    $result = [];
    while (!$heap->isEmpty()) {
        $result[] = $heap->extract()[1];
    }
    return $result;
}

print_r(kClosest([[1,3],[-2,2]], 1));         // [[-2,2]]
print_r(kClosest([[3,3],[5,-1],[-2,4]], 2));  // [[3,3],[-2,4]]

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

---

Q35. Set Matrix Zeroes [M][FB]

Problem: If any cell in an m×n matrix is 0, set its entire row and column to 0. Do it in-place with O(1) extra space.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

In-place matrix modification — use first row/column as flags to avoid extra space.

Step 2 — Naive:

Collect all zero positions, then zero rows/cols → O(m+n) extra space.

Step 3 — O(1) space insight:

Use row 0 and col 0 as flag arrays. matrix[i][0]=0 means "zero row i". matrix[0][j]=0 means "zero col j". First row/col need separate booleans since they are the flags themselves.

Step 4 — Algorithm:

1. Check if first row/col originally have zeros (save as booleans)

2. For i,j > 0: if matrix[i][j]=0, set matrix[i][0]=0 and matrix[0][j]=0

3. For i,j > 0: if flag is 0 → zero the cell

4. Apply first row/col booleans to actually zero row 0 / col 0

Step 5 — Edge cases:

- 1×1 matrix: trivial

function setZeroes(array &$matrix): void {
    $rows = count($matrix);
    $cols = count($matrix[0]);
    $zeroFirstRow = false;
    $zeroFirstCol = false;

    // Check first row and col for original zeros
    for ($j = 0; $j < $cols; $j++) if ($matrix[0][$j] === 0) $zeroFirstRow = true;
    for ($i = 0; $i < $rows; $i++) if ($matrix[$i][0] === 0) $zeroFirstCol = true;

    // Mark zeros using first row/col as flags
    for ($i = 1; $i < $rows; $i++) {
        for ($j = 1; $j < $cols; $j++) {
            if ($matrix[$i][$j] === 0) {
                $matrix[$i][0] = 0;
                $matrix[0][$j] = 0;
            }
        }
    }

    // Zero cells based on flags
    for ($i = 1; $i < $rows; $i++)
        for ($j = 1; $j < $cols; $j++)
            if ($matrix[$i][0] === 0 || $matrix[0][$j] === 0)
                $matrix[$i][$j] = 0;

    if ($zeroFirstRow) for ($j = 0; $j < $cols; $j++) $matrix[0][$j] = 0;
    if ($zeroFirstCol) for ($i = 0; $i < $rows; $i++) $matrix[$i][0] = 0;
}

Time: O(m×n) | Space: O(1)

---

Q36. Maximum Sum Circular Subarray [M][FB]

Problem: Find the maximum sum subarray in a circular array (subarray may wrap around).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

A circular max subarray is either:

- A normal (non-wrapping) subarray → Kadane's max

- A wrapping subarray = total sum − (some middle portion) → minimize that middle with Kadane's min

Step 2 — Algorithm:

1. maxSum = Kadane's max subarray

2. minSum = Kadane's min subarray

3. circularMax = total − minSum

4. If all values negative: return maxSum (circularMax would be empty = 0, which is wrong)

5. Return max(maxSum, circularMax)

Step 3 — Edge cases:

- All negative: skip circularMax (it becomes 0 which is invalid)

function maxSubarraySumCircular(array $nums): int {
    $total  = array_sum($nums);
    $maxSum = $minSum = $nums[0];
    $curMax = $curMin = $nums[0];

    for ($i = 1; $i < count($nums); $i++) {
        $curMax = max($nums[$i], $curMax + $nums[$i]);
        $maxSum = max($maxSum, $curMax);
        $curMin = min($nums[$i], $curMin + $nums[$i]);
        $minSum = min($minSum, $curMin);
    }

    // If maxSum < 0, all elements are negative — circular answer is invalid
    return $maxSum > 0 ? max($maxSum, $total - $minSum) : $maxSum;
}

echo maxSubarraySumCircular([1,-2,3,-2]);  // 3
echo maxSubarraySumCircular([5,-3,5]);     // 10  (wraps: 5+5)
echo maxSubarraySumCircular([-3,-2,-3]);   // -2

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

---

Q37. Minimum Arrows to Burst Balloons [M]

Problem: Balloons have horizontal extents [start, end]. A vertical arrow at x bursts all balloons whose range includes x. Return minimum arrows needed.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Minimum arrows = greedy interval scheduling. Sort by end coordinate.

Step 2 — Key insight:

Shoot as far right as possible (at the first balloon's right edge). This bursts the most overlapping balloons with one shot. Any balloon that starts AFTER that shot position needs a new arrow.

Step 3 — Algorithm:

1. Sort by end coordinate

2. arrows=1, arrowPos=balloons[0][1]

3. For each balloon: if start > arrowPos → new arrow, arrowPos = balloon[1]

Step 4 — Edge cases:

- Empty: 0 arrows

- Non-overlapping balloons: arrows = count of balloons

function findMinArrowShots(array $points): int {
    if (empty($points)) return 0;

    usort($points, fn($a, $b) => $a[1] <=> $b[1]); // sort by end

    $arrows   = 1;
    $arrowPos = $points[0][1];

    for ($i = 1; $i < count($points); $i++) {
        if ($points[$i][0] > $arrowPos) {  // balloon starts after current arrow
            $arrows++;
            $arrowPos = $points[$i][1];
        }
    }
    return $arrows;
}

echo findMinArrowShots([[10,16],[2,8],[1,6],[7,12]]); // 2
echo findMinArrowShots([[1,2],[3,4],[5,6],[7,8]]);     // 4

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

---

Q38. Subarray Sum Divisible by K [M][FB]

Problem: Count the number of subarrays whose sum is divisible by K.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count subarrays with sum % k = 0 = Prefix Sum + Modular Arithmetic + Hash Map.

Step 2 — Key insight:

If prefixSum[i] % k = prefixSum[j] % k, then sum of subarray [j+1..i] is divisible by k. Count pairs with same remainder.

Step 3 — Algorithm:

1. remainderCount = [0 => 1] (prefix sum 0 seen once before start)

2. For each num: sum += num; rem = ((sum % k) + k) % k (handle negatives)

3. count += remainderCount[rem]; remainderCount[rem]++

Step 4 — Edge cases:

- Negative numbers: ((sum % k) + k) % k normalizes to positive remainder

- k=1: all subarrays are divisible (count = n*(n+1)/2)

function subarraysDivByK(array $nums, int $k): int {
    $count          = 0;
    $sum            = 0;
    $remainderCount = [0 => 1];

    foreach ($nums as $num) {
        $sum += $num;
        $rem  = (($sum % $k) + $k) % $k; // normalize to positive
        $count += $remainderCount[$rem] ?? 0;
        $remainderCount[$rem] = ($remainderCount[$rem] ?? 0) + 1;
    }
    return $count;
}

echo subarraysDivByK([4,5,0,-2,-3,1], 5); // 7
echo subarraysDivByK([5], 9);              // 0

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

---

Q39. Find Minimum in Rotated Sorted Array [M][FB]

Problem: Find the minimum element in a rotated sorted array (no duplicates) in O(log n).

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Find rotation pivot in sorted-then-rotated array = Binary Search.

Step 2 — Key insight:

If nums[mid] > nums[right], the minimum is in the RIGHT half (rotation point is there). Otherwise the minimum is in the LEFT half (including mid).

Step 3 — Algorithm:

1. left=0, right=n-1

2. While left < right: mid = (left+right)/2

3. If nums[mid] > nums[right]: left = mid+1 (min is right of mid)

4. Else: right = mid (min is mid or left of mid)

5. Return nums[left]

Step 4 — Edge cases:

- Not rotated: right stays on left, returns nums[0]

- Single element: returns it directly

function findMin(array $nums): int {
    $left  = 0;
    $right = count($nums) - 1;

    while ($left < $right) {
        $mid = intdiv($left + $right, 2);
        if ($nums[$mid] > $nums[$right]) {
            $left = $mid + 1;  // min is in right half
        } else {
            $right = $mid;     // min is here or in left half
        }
    }
    return $nums[$left];
}

echo findMin([3,4,5,1,2]);    // 1
echo findMin([4,5,6,7,0,1,2]); // 0
echo findMin([11,13,15,17]);   // 11

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

---

Q40. Wiggle Subsequence [M]

Problem: A wiggle sequence alternates between increasing and decreasing. Return the length of the longest wiggle subsequence.

---

🧠 How to Approach This

Step 1 — Recognize the pattern:

Count peaks and valleys = Greedy. Each time the direction changes, we add 1 to our subsequence.

Step 2 — Key insight:

We only care when the direction flips: from going up to going down (or vice versa). Count the total number of direction changes + 1.

Step 3 — Algorithm:

1. up = down = 1 (single element is a valid wiggle of length 1)

2. For each i from 1 to n: if nums[i] > nums[i-1]: up = down + 1

3. If nums[i] < nums[i-1]: down = up + 1

4. Return max(up, down)

Step 4 — Edge cases:

- All equal: length 1

- Strictly alternating: length = n

function wiggleMaxLength(array $nums): int {
    if (count($nums) < 2) return count($nums);

    $up   = 1; // length of longest ending with an upward wiggle
    $down = 1; // length of longest ending with a downward wiggle

    for ($i = 1; $i < count($nums); $i++) {
        if ($nums[$i] > $nums[$i - 1]) {
            $up = $down + 1;
        } elseif ($nums[$i] < $nums[$i - 1]) {
            $down = $up + 1;
        }
    }
    return max($up, $down);
}

echo wiggleMaxLength([1,7,4,9,2,5]);   // 6  (all elements)
echo wiggleMaxLength([1,2,3,4,5,6]);   // 2  (one direction only)
echo wiggleMaxLength([1,17,5,10,13,15,10,5,16,8]); // 7

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

---

Summary: Problem → Technique Mapping

---

Q1. Find All Duplicates in Array [E][FB]

Question: Array [4,3,2,7,8,2,3,1] has values 1–n. Find all duplicates.

Way of Thinking:

Use index as a marker. For each value v, negate arr[abs(v)-1]. If it's already negative, abs(v) is a duplicate.

function findDuplicates(array $nums): array {
    $result = [];

    foreach ($nums as $num) {
        $idx = abs($num) - 1;
        if ($nums[$idx] < 0) {
            $result[] = abs($num); // already marked = duplicate
        } else {
            $nums[$idx] = -$nums[$idx]; // mark as visited
        }
    }

    return $result;
}

print_r(findDuplicates([4,3,2,7,8,2,3,1])); // [2,3]

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

---

Q2. Missing Number [E][FB]

Question: Array has n numbers from 0 to n with one missing. Find it.

Way of Thinking:

Expected sum = n*(n+1)/2. Actual sum = array_sum. Missing = expected - actual.

function missingNumber(array $nums): int {
    $n = count($nums);
    $expected = $n * ($n + 1) / 2;
    return $expected - array_sum($nums);
}

echo missingNumber([3,0,1]); // 2
echo missingNumber([9,6,4,2,3,5,7,0,1]); // 8

XOR Method (no overflow risk):

function missingNumberXOR(array $nums): int {
    $xor = 0;
    $n = count($nums);
    for ($i = 0; $i <= $n; $i++) $xor ^= $i;
    foreach ($nums as $num) $xor ^= $num;
    return $xor;
}

---

Q3. Single Number [E][FB]

Question: Every element appears twice except one. Find it. No extra memory.

Way of Thinking:

XOR: a ^ a = 0, a ^ 0 = a. XOR all elements → pairs cancel → only single remains.

function singleNumber(array $nums): int {
    return array_reduce($nums, fn($carry, $n) => $carry ^ $n, 0);
}

echo singleNumber([2,2,1]);         // 1
echo singleNumber([4,1,2,1,2]);     // 4

JavaScript:

const singleNumber = nums => nums.reduce((xor, n) => xor ^ n, 0);

---

Q4. Plus One [E]

Question: Array represents a number [1,2,9] = 129. Add 1 → [1,3,0].

Way of Thinking:

Process from right. Add 1. If result < 10, done. If 10, set 0, carry to next. If all carry, prepend 1.

function plusOne(array $digits): array {
    for ($i = count($digits) - 1; $i >= 0; $i--) {
        if ($digits[$i] < 9) {
            $digits[$i]++;
            return $digits;
        }
        $digits[$i] = 0; // carry
    }
    array_unshift($digits, 1); // [9,9,9] → [1,0,0,0]
    return $digits;
}

print_r(plusOne([1,2,9]));    // [1,3,0]
print_r(plusOne([9,9,9]));    // [1,0,0,0]

---

Q5. Intersection of Two Arrays [E]

function intersect(array $nums1, array $nums2): array {
    $count = array_count_values($nums1);
    $result = [];

    foreach ($nums2 as $num) {
        if (isset($count[$num]) && $count[$num] > 0) {
            $result[] = $num;
            $count[$num]--;
        }
    }

    return $result;
}

print_r(intersect([1,2,2,1], [2,2])); // [2,2]

---

Medium Level

---

Q6. Best Time to Buy and Sell Stock [M][FB]

Question: [7,1,5,3,6,4] — max profit from one buy/sell.

Way of Thinking:

Track minimum price seen so far. At each day, profit = price - minPrice. Track maxProfit.

[7, 1, 5, 3, 6, 4]
    ↑ buy here (min=1)
          ↑ sell here (profit=5)

function maxProfit(array $prices): int {
    $minPrice  = PHP_INT_MAX;
    $maxProfit = 0;

    foreach ($prices as $price) {
        $minPrice  = min($minPrice, $price);
        $maxProfit = max($maxProfit, $price - $minPrice);
    }

    return $maxProfit;
}

echo maxProfit([7,1,5,3,6,4]); // 5 (buy at 1, sell at 6)
echo maxProfit([7,6,4,3,1]);   // 0 (no profit possible)

JavaScript:

const maxProfit = prices => {
    let minPrice = Infinity, maxProfit = 0;
    for (const p of prices) {
        minPrice  = Math.min(minPrice, p);
        maxProfit = Math.max(maxProfit, p - minPrice);
    }
    return maxProfit;
};

---

Q7. Find All Numbers Disappeared in Array [M]

Question: Array 1–n with duplicates. Find all missing numbers. O(1) space.

Way of Thinking:

Mark visited using negative index trick (same as Q1). Numbers with positive value at index i mean (i+1) is missing.

function findDisappearedNumbers(array $nums): array {
    // Mark visited
    foreach ($nums as $num) {
        $idx = abs($num) - 1;
        if ($nums[$idx] > 0) $nums[$idx] = -$nums[$idx];
    }

    // Positive index means value (i+1) never appeared
    $result = [];
    foreach ($nums as $i => $num) {
        if ($num > 0) $result[] = $i + 1;
    }

    return $result;
}

print_r(findDisappearedNumbers([4,3,2,7,8,2,3,1])); // [5,6]

---

Q8. Majority Element [M][FB]

Question: Find element appearing > n/2 times. Must be O(n) time, O(1) space.

Way of Thinking (Boyer-Moore Voting):

If majority exists, it will "survive" cancellations against all others.

Count up for candidate, count down for others. When count=0, pick new candidate.

function majorityElement(array $nums): int {
    $candidate = 0;
    $count     = 0;

    foreach ($nums as $num) {
        if ($count === 0) {
            $candidate = $num;
        }
        $count += ($num === $candidate) ? 1 : -1;
    }

    return $candidate;
}

echo majorityElement([3,2,3]);               // 3
echo majorityElement([2,2,1,1,1,2,2]);       // 2

---

Q9. Next Permutation [M][FB]

Question: Rearrange [1,2,3] to next permutation [1,3,2]. In-place.

Way of Thinking:

1. Find rightmost element smaller than its right neighbor (pivot)
2. Find rightmost element greater than pivot
3. Swap them
4. Reverse everything to the right of pivot position

function nextPermutation(array &$nums): void {
    $n = count($nums);
    $i = $n - 2;

    // Step 1: Find pivot (first descending from right)
    while ($i >= 0 && $nums[$i] >= $nums[$i + 1]) $i--;

    if ($i >= 0) {
        // Step 2: Find rightmost element > pivot
        $j = $n - 1;
        while ($nums[$j] <= $nums[$i]) $j--;

        // Step 3: Swap
        [$nums[$i], $nums[$j]] = [$nums[$j], $nums[$i]];
    }

    // Step 4: Reverse suffix
    $left = $i + 1;
    $right = $n - 1;
    while ($left < $right) {
        [$nums[$left], $nums[$right]] = [$nums[$right], $nums[$left]];
        $left++; $right--;
    }
}

$arr = [1,2,3]; nextPermutation($arr); print_r($arr); // [1,3,2]
$arr = [3,2,1]; nextPermutation($arr); print_r($arr); // [1,2,3]

---

Q10. Jump Game [M][FB]

Question: [2,3,1,1,4] — each value is max jump length. Can you reach last index?

Way of Thinking:

Track maximum reachable index. At each position, update max reach. If current position > max reach, we're stuck.

function canJump(array $nums): bool {
    $maxReach = 0;

    foreach ($nums as $i => $jump) {
        if ($i > $maxReach) return false; // can't reach this position
        $maxReach = max($maxReach, $i + $jump);
    }

    return true;
}

var_dump(canJump([2,3,1,1,4])); // true
var_dump(canJump([3,2,1,0,4])); // false

---

Q11. Spiral Matrix [M]

Question: Return all elements of matrix in spiral order.

Way of Thinking:

Define four boundaries (top, bottom, left, right). Move right→down→left→up. Shrink boundary after each direction.

function spiralOrder(array $matrix): array {
    $result = [];
    if (empty($matrix)) return $result;

    $top = 0; $bottom = count($matrix) - 1;
    $left = 0; $right = count($matrix[0]) - 1;

    while ($top <= $bottom && $left <= $right) {
        // Move right
        for ($i = $left; $i <= $right; $i++)   $result[] = $matrix[$top][$i];
        $top++;

        // Move down
        for ($i = $top; $i <= $bottom; $i++)   $result[] = $matrix[$i][$right];
        $right--;

        // Move left
        if ($top <= $bottom) {
            for ($i = $right; $i >= $left; $i--) $result[] = $matrix[$bottom][$i];
            $bottom--;
        }

        // Move up
        if ($left <= $right) {
            for ($i = $bottom; $i >= $top; $i--) $result[] = $matrix[$i][$left];
            $left++;
        }
    }

    return $result;
}

print_r(spiralOrder([[1,2,3],[4,5,6],[7,8,9]]));
// [1,2,3,6,9,8,7,4,5]

---

Q12. Rotate Matrix 90 Degrees [M][FB]

Way of Thinking:

Transpose (swap rows and columns), then reverse each row.

function rotateMatrix(array &$matrix): void {
    $n = count($matrix);

    // Step 1: Transpose
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            [$matrix[$i][$j], $matrix[$j][$i]] = [$matrix[$j][$i], $matrix[$i][$j]];
        }
    }

    // Step 2: Reverse each row
    foreach ($matrix as &$row) {
        $row = array_reverse($row);
    }
}

$matrix = [[1,2,3],[4,5,6],[7,8,9]];
rotateMatrix($matrix);
// [[7,4,1],[8,5,2],[9,6,3]]

---

Q13. Longest Consecutive Sequence [M][FB]

Question: [100,4,200,1,3,2] → longest consecutive sequence length = 4 (1,2,3,4).

Way of Thinking:

Use a hash set. For each number, only start counting if n-1 is NOT in set (it's a sequence start). Count up from there.

function longestConsecutive(array $nums): int {
    $numSet = array_flip($nums); // O(1) lookup
    $longest = 0;

    foreach ($numSet as $num => $_) {
        if (!isset($numSet[$num - 1])) { // start of sequence
            $length = 1;
            while (isset($numSet[$num + $length])) {
                $length++;
            }
            $longest = max($longest, $length);
        }
    }

    return $longest;
}

echo longestConsecutive([100,4,200,1,3,2]); // 4

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

---

Q14. Merge Intervals [M][FB][L]

Question: Merge [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]].

Way of Thinking:

Sort by start. If current interval overlaps with last merged (start <= last end), merge (extend last end). Else add as new interval.

function mergeIntervals(array $intervals): array {
    if (empty($intervals)) return [];

    // Sort by start time
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);

    $merged = [$intervals[0]];

    for ($i = 1; $i < count($intervals); $i++) {
        $current = $intervals[$i];
        $last    = &$merged[count($merged) - 1];

        if ($current[0] <= $last[1]) {
            $last[1] = max($last[1], $current[1]); // merge: extend end
        } else {
            $merged[] = $current; // no overlap: add new
        }
    }

    return $merged;
}

print_r(mergeIntervals([[1,3],[2,6],[8,10],[15,18]]));
// [[1,6],[8,10],[15,18]]

Laravel context: Merging date ranges for scheduling, booking systems.

---

Q15. Group Anagrams [M][FB]

Question: Group ["eat","tea","tan","ate","nat","bat"] by anagram.

Way of Thinking:

Sort each word alphabetically → same sorted key = same anagram group.

function groupAnagrams(array $strs): array {
    $groups = [];

    foreach ($strs as $str) {
        $key = str_split($str);
        sort($key);
        $key = implode('', $key);
        $groups[$key][] = $str;
    }

    return array_values($groups);
}

print_r(groupAnagrams(["eat","tea","tan","ate","nat","bat"]));
// [["eat","tea","ate"],["tan","nat"],["bat"]]

---

Hard Level

---

Q16. First Missing Positive [H][FB]

Question: Find smallest missing positive in [3,4,-1,1] → answer is 2. O(n) time, O(1) space.

Way of Thinking:

Place each number at its correct index: value 1 → index 0, value 2 → index 1, etc.

Then scan for first index where arr[i] ≠ i+1.

function firstMissingPositive(array $nums): int {
    $n = count($nums);

    // Place each number at its correct position
    for ($i = 0; $i < $n; $i++) {
        while ($nums[$i] > 0 && $nums[$i] <= $n && $nums[$nums[$i] - 1] !== $nums[$i]) {
            $idx = $nums[$i] - 1;
            [$nums[$i], $nums[$idx]] = [$nums[$idx], $nums[$i]];
        }
    }

    // Find first wrong position
    for ($i = 0; $i < $n; $i++) {
        if ($nums[$i] !== $i + 1) return $i + 1;
    }

    return $n + 1;
}

echo firstMissingPositive([3,4,-1,1]);  // 2
echo firstMissingPositive([1,2,0]);      // 3
echo firstMissingPositive([7,8,9,11]);   // 1

---

Q17. Median of Two Sorted Arrays [H][FB]

Way of Thinking:

Binary search on the smaller array to find the right partition point where left half of both arrays combined has the correct count.

function findMedianSortedArrays(array $nums1, array $nums2): float {
    // Ensure nums1 is the smaller array
    if (count($nums1) > count($nums2)) {
        return findMedianSortedArrays($nums2, $nums1);
    }

    $m = count($nums1);
    $n = count($nums2);
    $half = intdiv($m + $n, 2);

    $left = 0;
    $right = $m;

    while ($left <= $right) {
        $i = intdiv($left + $right, 2); // partition nums1
        $j = $half - $i;                // partition nums2

        $maxLeft1  = $i > 0 ? $nums1[$i - 1] : PHP_INT_MIN;
        $minRight1 = $i < $m ? $nums1[$i]     : PHP_INT_MAX;
        $maxLeft2  = $j > 0 ? $nums2[$j - 1] : PHP_INT_MIN;
        $minRight2 = $j < $n ? $nums2[$j]     : PHP_INT_MAX;

        if ($maxLeft1 <= $minRight2 && $maxLeft2 <= $minRight1) {
            // Correct partition
            if (($m + $n) % 2 === 1) {
                return min($minRight1, $minRight2);
            }
            return (max($maxLeft1, $maxLeft2) + min($minRight1, $minRight2)) / 2.0;
        } elseif ($maxLeft1 > $minRight2) {
            $right = $i - 1;
        } else {
            $left = $i + 1;
        }
    }

    return 0.0;
}

echo findMedianSortedArrays([1,3], [2]);     // 2.0
echo findMedianSortedArrays([1,2], [3,4]);   // 2.5

---

PHP/Laravel Specific Questions

---

Q18. Chunk Array for Batch Processing [E][L]

Real Laravel scenario: Process 10,000 records in batches of 500.

// PHP built-in
$chunks = array_chunk($largeArray, 500);
foreach ($chunks as $chunk) {
    processChunk($chunk);
}

// Laravel
User::chunk(500, function ($users) {
    foreach ($users as $user) {
        // process
    }
});

// Laravel lazy (memory efficient)
User::lazy()->each(function ($user) {
    // process one at a time
});

---

Q19. Transform Collection with Map/Filter/Reduce [E][L]

Real Laravel scenario: Build an API response from Eloquent models.

$users = User::where('active', true)->get();

$response = $users
    ->filter(fn($u) => $u->age >= 18)
    ->map(fn($u) => [
        'id'    => $u->id,
        'name'  => $u->name,
        'email' => $u->email,
    ])
    ->sortBy('name')
    ->values()
    ->toArray();

---

Q20. Find Longest Subarray with Equal 0s and 1s [M]

Question: [0,1,0,0,1,1,0] — find length of longest subarray with equal 0s and 1s.

Way of Thinking:

Replace 0 with -1. Now problem = "find longest subarray with sum 0".

Use prefix sum + hash map: when same prefix sum seen again, subarray between them has sum 0.

function findMaxLengthEqualZeroOne(array $nums): int {
    // Replace 0 with -1
    $nums = array_map(fn($n) => $n === 0 ? -1 : 1, $nums);

    $seen = [0 => -1]; // prefixSum => first seen index
    $prefixSum = 0;
    $maxLen = 0;

    foreach ($nums as $i => $num) {
        $prefixSum += $num;

        if (isset($seen[$prefixSum])) {
            $maxLen = max($maxLen, $i - $seen[$prefixSum]);
        } else {
            $seen[$prefixSum] = $i;
        }
    }

    return $maxLen;
}

echo findMaxLengthEqualZeroOne([0,1,0,0,1,1,0]); // 6

---

Summary: Problem → Technique Mapping