Problem Solving

<?php
// Restated: best profit from one buy then one later sell; 0 if prices only fall.
// Input: list of ints (may be empty). Output: int >= 0.
function maxProfit(array $prices): int
{
    $lowest = PHP_INT_MAX;
    $best = 0;
    foreach ($prices as $price) {
        $lowest = min($lowest, $price);       // cheapest buy so far
        $best = max($best, $price - $lowest); // what if I sell today?
    }
    return $best;
}

echo maxProfit([7, 1, 5, 3, 6, 4]), "\n"; // normal: buy at 1, sell at 6
echo maxProfit([7, 6, 4, 3, 1]), "\n";    // prices only fall
echo maxProfit([]), "\n";                 // empty
echo maxProfit([5]), "\n";                // one day

<?php
function isPalindrome(string $s): bool
{
    $i = 0;
    $j = strlen($s) - 1;
    while ($i < $j) {
        if (!ctype_alnum($s[$i])) { $i++; continue; }
        if (!ctype_alnum($s[$j])) { $j--; continue; }
        if (strtolower($s[$i]) !== strtolower($s[$j])) return false;
        $i++;
        $j--;
    }
    return true;
}

$passed = $failed = 0;
$check = function (string $input, bool $expected) use (&$passed, &$failed): void {
    $got = isPalindrome($input);
    if ($got === $expected) { $passed++; return; }
    $failed++;
    echo "FAIL '$input': expected ", var_export($expected, true), ', got ', var_export($got, true), "\n";
};

$check('', true);                          // empty
$check('a', true);                         // one character
$check('ab', false);                       // smallest false case
$check('Aba', true);                       // mixed case
$check('A man, a plan, a canal: Panama', true);
$check('race a car', false);
$check('.,', true);                        // only punctuation
echo "$passed passed, $failed failed\n";

<?php
// O(n^2): compare every pair
function nestedOps(array $a): int
{
    $ops = 0;
    $n = count($a);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            $ops++;
            if ($a[$i] === $a[$j]) return $ops;
        }
    }
    return $ops;
}

// O(n): remember what we have seen, as array KEYS
function setOps(array $a): int
{
    $ops = 0;
    $seen = [];
    foreach ($a as $x) {
        $ops++;
        if (isset($seen[$x])) return $ops;
        $seen[$x] = true;
    }
    return $ops;
}

foreach ([1_000, 10_000] as $n) {
    $a = range(0, $n - 1); // no duplicates: the worst case
    echo "n=$n  nested=", nestedOps($a), '  set=', setOps($a), "\n";
}

<?php
// sorted input: indices of two numbers that add up to $target, or null
function pairSum(array $a, int $target): ?array
{
    $i = 0;
    $j = count($a) - 1;
    while ($i < $j) {
        $sum = $a[$i] + $a[$j];
        if ($sum === $target) return [$i, $j];
        if ($sum < $target) $i++; // need bigger: move the left pointer up
        else $j--;                // need smaller: move the right pointer down
    }
    return null;
}

$a = [1, 3, 4, 6, 8, 11];
echo json_encode(pairSum($a, 10)), "\n";
echo json_encode(pairSum($a, 2)), "\n";

<?php
// length of the longest substring with no repeated character
function longestUnique(string $s): int
{
    $lastSeen = [];
    $best = $left = 0;
    for ($right = 0; $right < strlen($s); $right++) {
        $c = $s[$right];
        if (isset($lastSeen[$c]) && $lastSeen[$c] >= $left) {
            $left = $lastSeen[$c] + 1; // jump the left edge past the repeat
        }
        $lastSeen[$c] = $right;
        $best = max($best, $right - $left + 1);
    }
    return $best;
}

// fixed-size window: biggest sum of any $k consecutive numbers
function maxSumK(array $a, int $k): int
{
    $sum = array_sum(array_slice($a, 0, $k));
    $best = $sum;
    for ($i = $k; $i < count($a); $i++) {
        $sum += $a[$i] - $a[$i - $k]; // slide: add the new, drop the old
        $best = max($best, $sum);
    }
    return $best;
}

echo longestUnique('abcabcbb'), ' ', longestUnique('bbbb'), ' ', longestUnique('pwwkew'), "\n";
echo maxSumK([2, 1, 5, 1, 3, 2], 3), "\n";

<?php
// unsorted input: indices of two numbers that add up to $target
function twoSum(array $nums, int $target): ?array
{
    $indexOf = [];
    foreach ($nums as $i => $x) {
        $need = $target - $x;
        if (isset($indexOf[$need])) return [$indexOf[$need], $i];
        $indexOf[$x] = $i;
    }
    return null;
}

// group words that are anagrams of each other
function groupAnagrams(array $words): array
{
    $groups = [];
    foreach ($words as $w) {
        $letters = str_split($w);
        sort($letters);
        $groups[implode('', $letters)][] = $w;
    }
    return array_values($groups);
}

echo json_encode(twoSum([2, 7, 11, 15], 9)), "\n";
echo json_encode(twoSum([3, 2, 4], 6)), "\n";
foreach (groupAnagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']) as $g) {
    echo implode(',', $g), "\n";
}

<?php
// for each day, how many days until a warmer temperature (0 if never)
function daysUntilWarmer(array $temps): array
{
    $answer = array_fill(0, count($temps), 0);
    $waiting = []; // indexes, temperatures decreasing from bottom to top
    foreach ($temps as $i => $t) {
        while ($waiting && $temps[end($waiting)] < $t) {
            $j = array_pop($waiting);
            $answer[$j] = $i - $j;
        }
        $waiting[] = $i;
    }
    return $answer;
}

// simplify a Unix path: /a/./b/../../c/ -> /c
function simplifyPath(string $path): string
{
    $stack = [];
    foreach (explode('/', $path) as $part) {
        if ($part === '' || $part === '.') continue;
        if ($part === '..') array_pop($stack);
        else $stack[] = $part;
    }
    return '/' . implode('/', $stack);
}

echo implode(' ', daysUntilWarmer([73, 74, 75, 71, 69, 72, 76, 73])), "\n";
echo simplifyPath('/a/./b/../../c/'), "\n";
echo simplifyPath('/../'), "\n";

<?php
function subsets(array $items): array
{
    $out = [];
    $current = [];
    $walk = function (int $start) use (&$walk, &$out, &$current, $items): void {
        $out[] = $current;                     // every node is a subset
        for ($i = $start; $i < count($items); $i++) {
            $current[] = $items[$i];           // choose
            $walk($i + 1);                     // explore
            array_pop($current);               // un-choose
        }
    };
    $walk(0);
    return $out;
}

function permutations(array $items): array
{
    if (count($items) <= 1) return [$items];
    $out = [];
    foreach ($items as $i => $x) {
        $rest = $items;
        unset($rest[$i]);
        foreach (permutations(array_values($rest)) as $p) {
            $out[] = [$x, ...$p];
        }
    }
    return $out;
}

echo implode(' ', array_map(fn($s) => '[' . implode(',', $s) . ']', subsets(['a', 'b', 'c']))), "\n";
echo implode(' ', array_map(fn($p) => implode('', $p), permutations([1, 2, 3]))), "\n";

<?php
function mergeIntervals(array $intervals): array
{
    usort($intervals, fn($a, $b) => $a[0] <=> $b[0]);
    $merged = [];
    foreach ($intervals as [$start, $end]) {
        $last = array_key_last($merged);
        if ($last !== null && $start <= $merged[$last][1]) {
            $merged[$last][1] = max($merged[$last][1], $end); // overlap: extend
        } else {
            $merged[] = [$start, $end];                       // gap: new interval
        }
    }
    return $merged;
}

echo json_encode(mergeIntervals([[8, 10], [1, 3], [2, 6], [15, 18], [17, 20]])), "\n";
echo json_encode(mergeIntervals([[1, 4], [4, 5]])), "\n";

<?php
function countIslands(array $grid): int
{
    $rows = count($grid);
    $cols = strlen($grid[0]);
    $seen = [];
    $sink = function (int $r, int $c) use (&$sink, &$seen, $grid, $rows, $cols): void {
        if ($r < 0 || $c < 0 || $r >= $rows || $c >= $cols) return;
        if ($grid[$r][$c] !== '#' || isset($seen["$r,$c"])) return;
        $seen["$r,$c"] = true;
        $sink($r + 1, $c); $sink($r - 1, $c); $sink($r, $c + 1); $sink($r, $c - 1);
    };
    $islands = 0;
    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($grid[$r][$c] === '#' && !isset($seen["$r,$c"])) {
                $islands++;
                $sink($r, $c);
            }
        }
    }
    return $islands;
}

function shortestSteps(array $maze): int
{
    $rows = count($maze);
    $cols = strlen($maze[0]);
    $queue = new SplQueue();
    $queue->enqueue([0, 0, 0]);
    $seen = ['0,0' => true];
    while (!$queue->isEmpty()) {
        [$r, $c, $d] = $queue->dequeue();
        if ($r === $rows - 1 && $c === $cols - 1) return $d;
        foreach ([[1, 0], [-1, 0], [0, 1], [0, -1]] as [$dr, $dc]) {
            $nr = $r + $dr;
            $nc = $c + $dc;
            if ($nr < 0 || $nc < 0 || $nr >= $rows || $nc >= $cols) continue;
            if ($maze[$nr][$nc] === '#' || isset($seen["$nr,$nc"])) continue;
            $seen["$nr,$nc"] = true;
            $queue->enqueue([$nr, $nc, $d + 1]);
        }
    }
    return -1;
}

echo countIslands(['##..#', '#...#', '..#..', '.....', '##.##']), "\n";
echo shortestSteps(['..#.', '#...', '..#.', '.#..']), "\n";

<?php
// ways to climb n stairs taking 1 or 2 steps: ways(n) = ways(n-1) + ways(n-2)
function climbStairs(int $n): int
{
    [$a, $b] = [1, 1];
    for ($i = 2; $i <= $n; $i++) [$a, $b] = [$b, $a + $b];
    return $b;
}

// house robber: max sum with no two adjacent houses
function rob(array $houses): int
{
    $take = $skip = 0; // best total if we take / skip the previous house
    foreach ($houses as $h) {
        [$take, $skip] = [$skip + $h, max($take, $skip)];
    }
    return max($take, $skip);
}

echo climbStairs(5), ' ', climbStairs(10), "\n";
echo rob([2, 7, 9, 3, 1]), ' ', rob([2, 1, 1, 2]), "\n";