Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

class Solution {
    function kWeakestRows($mat, $k) {
        $m = count($mat);
        $n = count($mat[0]);

        $pairs = [];
        for ($i = 0; $i < $m; $i++) {
            $strength = 0;
            for ($j = 0; $j < $n; $j++) {
                if ($mat[$i][$j] == 0) break;
                $strength++;
            }
            $pairs[] = [$strength, $i];
        }

        usort($pairs, function($a, $b) {
            if ($a[0] == $b[0]) return $a[1] - $b[1];
            return $a[0] - $b[0];
        });

        $indexes = [];
        for ($i = 0; $i < $k; $i++) {
            $indexes[] = $pairs[$i][1];
        }
        return $indexes;
    }
}

Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.

class Solution {
    private $directions = [0, 1, 0, -1, 0];

    function getMaximumGold($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        $maxGold = 0;

        for ($row = 0; $row < $rows; $row++) {
            for ($col = 0; $col < $cols; $col++) {
                $maxGold = max($maxGold, $this->dfsBacktrack($grid, $rows, $cols, $row, $col));
            }
        }
        return $maxGold;
    }

    private function dfsBacktrack(&$grid, $rows, $cols, $row, $col) {
        if ($row < 0 || $col < 0 || $row >= $rows || $col >= $cols || $grid[$row][$col] == 0) {
            return 0;
        }
        $originalVal = $grid[$row][$col];
        $grid[$row][$col] = 0;
        $maxGold = 0;

        for ($i = 0; $i < 4; $i++) {
            $maxGold = max($maxGold, $this->dfsBacktrack($grid, $rows, $cols, $row + $this->directions[$i], $col + $this->directions[$i + 1]));
        }

        $grid[$row][$col] = $originalVal;
        return $maxGold + $originalVal;
    }
}

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output: 4
Explanation: The longest arithmetic subsequence is [7,5,3,1].

class Solution {
    function longestSubsequence($arr, $difference) {
        $dp = [];
        $answer = 1;
        
        foreach ($arr as $a) {
            $beforeA = isset($dp[$a - $difference]) ? $dp[$a - $difference] : 0;
            $dp[$a] = $beforeA + 1;
            $answer = max($answer, $dp[$a]);
        }
        
        return $answer;
    }
}

Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

class Solution {
    function countElements($arr) {
        $count = 0;
        foreach ($arr as $x) {
            if ($this->integerInArray($arr, $x + 1)) {
                $count++;
            }
        }
        return $count;
    }

    function integerInArray($arr, $target) {
        foreach ($arr as $x) {
            if ($x == $target) {
                return true;
            }
        }
        return false;
    }
}

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

class Solution {
    private $smallestDistanceSum = PHP_INT_MAX;
    private $visited = array_fill(0, 10, false);
    
    private function findDistance($worker, $bike) {
        return abs($worker[0] - $bike[0]) + abs($worker[1] - $bike[1]);
    }
    
    private function minimumDistanceSum($workers, $workerIndex, $bikes, $currDistanceSum) {
        if ($workerIndex >= count($workers)) {
            $this->smallestDistanceSum = min($this->smallestDistanceSum, $currDistanceSum);
            return;
        }
        
        if ($currDistanceSum >= $this->smallestDistanceSum) {
            return;
        }
        
        foreach ($bikes as $bikeIndex => $bike) {
            if (!$this->visited[$bikeIndex]) {
                $this->visited[$bikeIndex] = true;
                $this->minimumDistanceSum($workers, $workerIndex + 1, $bikes, 
                    $currDistanceSum + $this->findDistance($workers[$workerIndex], $bike));
                $this->visited[$bikeIndex] = false;
            }
        }
    }
    
    public function assignBikes($workers, $bikes) {
        $this->minimumDistanceSum($workers, 0, $bikes, 0);
        return $this->smallestDistanceSum;
    }
}

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

class Solution {
    function carPooling($trips, $capacity) {
        $timestamp = [];
        foreach ($trips as $trip) {
            $timestamp[$trip[1]] = ($timestamp[$trip[1]] ?? 0) + $trip[0];
            $timestamp[$trip[2]] = ($timestamp[$trip[2]] ?? 0) - $trip[0];
        }
        ksort($timestamp);
        $usedCapacity = 0;
        foreach ($timestamp as $change) {
            $usedCapacity += $change;
            if ($usedCapacity > $capacity) {
                return false;
            }
        }
        return true;
    }
}

Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
Output: 2
Explanation: One potential sequence of moves is shown.
The first move swaps the first and second column.
The second move swaps the second and third row.

class Solution {
    function movesToChessboard($board) {
        $N = count($board);
        $ans = 0;
        
        foreach ([$this->getCount($board), $this->getCount($this->transpose($board))] as $count) {
            $values = array_values($count);
            sort($values);
            if (count($values) !== 2 || $values[0] !== intdiv($N, 2) || $values[1] !== intdiv($N + 1, 2)) {
                return -1;
            }

            $keys = array_keys($count);
            $line1 = $keys[0];
            $line2 = $keys[1];
            if (!$this->allOpposite($line1, $line2)) {
                return -1;
            }

            $starts = $N % 2 === 0 ? [0, 1] : [substr_count($line1, '1') * 2 > $N ? 1 : 0];

            $minSwaps = PHP_INT_MAX;
            foreach ($starts as $start) {
                $swaps = 0;
                for ($i = 0; $i < $N; $i++) {
                    if ((int)$line1[$i] !== ($i % 2 === $start ? 1 : 0)) {
                        $swaps++;
                    }
                }
                $minSwaps = min($minSwaps, intdiv($swaps, 2));
            }
            $ans += $minSwaps;
        }
        
        return $ans;
    }

    private function getCount($board) {
        $count = [];
        foreach ($board as $row) {
            $key = implode('', $row);
            if (!isset($count[$key])) {
                $count[$key] = 0;
            }
            $count[$key]++;
        }
        return $count;
    }

    private function transpose($board) {
        $N = count($board);
        $transposed = array_fill(0, $N, array_fill(0, $N, 0));
        for ($i = 0; $i < $N; $i++) {
            for ($j = 0; $j < $N; $j++) {
                $transposed[$j][$i] = $board[$i][$j];
            }
        }
        return $transposed;
    }

    private function allOpposite($line1, $line2) {
        for ($i = 0; $i < strlen($line1); $i++) {
            if ((int)$line1[$i] ^ (int)$line2[$i] === 0) {
                return false;
            }
        }
        return true;
    }
}

Input: nums = [4,2,5,7]
Output: [4,5,2,7]

function sortArrayByParityII($nums) {
    $result = array_fill(0, count($nums), 0);
    $evenIdx = 0;
    $oddIdx = 1;
    
    foreach ($nums as $num) {
        if ($num % 2 == 0) {
            $result[$evenIdx] = $num;
            $evenIdx += 2;
        } else {
            $result[$oddIdx] = $num;
            $oddIdx += 2;
        }
    }
    
    return $result;
}

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off]. 
So you should return 1 because there is only one bulb is on.
Explanation: The two words can be "abcw", "xtfn".

class Solution {
    function bulbSwitch($n) {
        return floor(sqrt($n));
    }
}

Input: list1 = [1,2,4], list2 = [1,3,4]  
Output: [1,1,2,3,4,4]

class Solution { 

    function mergeTwoLists($list1, $list2) { 
        $newList = new ListNode(); 
        $current = $newList; 

        while($list1 || $list2) { 
            if ($list1 && !$list2) { 
                $current->next = new ListNode($list1->val); 
                $list1 = $list1->next; 
            } elseif (!$list1 && $list2) { 
                $current->next = new ListNode($list2->val); 
                $list2 = $list2->next; 
            } else { 
                if ($list1->val <= $list2->val) { 
                    $current->next = new ListNode($list1->val); 
                    $list1 = $list1->next; 
                } else { 
                    $current->next = new ListNode($list2->val); 
                    $list2 = $list2->next; 
                } 
            } 
            $current = $current->next; 
        } 

        return $newList->next; 
    } 
}

Input: s = "aabcbc"
Output: true

class Solution {
    function isValid($s) {
        if (strlen($s) % 3 != 0) return false;

        $stack = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $char = $s[$i];
            if ($char == 'c') {
                if (count($stack) < 2 || array_pop($stack) != 'b' || array_pop($stack) != 'a') {
                    return false;
                }
            } else {
                $stack[] = $char;
            }
        }

        return empty($stack);
    }
}

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: 
[null,2,null,2,null,3,null,-1]
Explanation: 
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

class FirstUnique {
    private $queue;
    private $isUnique;

    function __construct($nums) {
        $this->queue = new SplDoublyLinkedList();
        $this->isUnique = [];
        foreach ($nums as $num) {
            $this->add($num);
        }
    }

    function showFirstUnique() {
        while (!$this->queue->isEmpty() && !$this->isUnique[$this->queue->bottom()]) {
            $this->queue->shift();
        }
        if ($this->queue->isEmpty()) {
            return -1;
        }
        return $this->queue->bottom();
    }

    function add($value) {
        if (!isset($this->isUnique[$value])) {
            $this->isUnique[$value] = true;
            $this->queue->push($value);
        } elseif ($this->isUnique[$value]) {
            $this->isUnique[$value] = false;
        }
    }
}

Input: nums = [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation: 1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant since they do not influence the operation priority.
So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

class Solution {
    private function addStrings($num1, $num2) {
        $ans = [];
        $carry = 0;
        $n1 = count($num1);
        $n2 = count($num2);

        for ($i = 0; $i < max($n1, $n2) || $carry; $i++) {
            $digit1 = $i < $n1 ? $num1[$i] : 0;
            $digit2 = $i < $n2 ? $num2[$i] : 0;
            $sum = $digit1 + $digit2 + $carry;
            $carry = intdiv($sum, 10);
            $ans[] = $sum % 10;
        }
        return $ans;
    }

    private function multiplyOneDigit($firstNumber, $secondNumberDigit, $numZeros) {
        $currentResult = array_fill(0, $numZeros, 0);
        $carry = 0;

        for ($i = 0; $i < strlen($firstNumber); $i++) {
            $multiplication = (intval($secondNumberDigit) * intval($firstNumber[$i])) + $carry;
            $carry = intdiv($multiplication, 10);
            $currentResult[] = $multiplication % 10;
        }
        if ($carry != 0) {
            $currentResult[] = $carry;
        }
        return $currentResult;
    }

    public function multiply($firstNumber, $secondNumber) {
        if ($firstNumber === "0" || $secondNumber === "0") {
            return "0";
        }

        $firstNumber = strrev($firstNumber);
        $secondNumber = strrev($secondNumber);

        $ans = array_fill(0, strlen($firstNumber) + strlen($secondNumber), 0);

        for ($i = 0; $i < strlen($secondNumber); $i++) {
            $ans = $this->addStrings($this->multiplyOneDigit($firstNumber, $secondNumber[$i], $i), $ans);
        }

        while (end($ans) === 0) {
            array_pop($ans);
        }

        return implode('', array_reverse($ans));
    }
}

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

function minMutation($start, $end, $bank) {
    $queue = [$start];
    $seen = [$start => true];
    $steps = 0;

    while (count($queue) > 0) {
        $nodesInQueue = count($queue);

        for ($j = 0; $j < $nodesInQueue; $j++) {
            $node = array_shift($queue);

            if ($node === $end) {
                return $steps;
            }

            foreach (str_split("ACGT") as $c) {
                for ($i = 0; $i < strlen($node); $i++) {
                    $neighbor = substr($node, 0, $i) . $c . substr($node, $i + 1);
                    if (!isset($seen[$neighbor]) && in_array($neighbor, $bank)) {
                        $queue[] = $neighbor;
                        $seen[$neighbor] = true;
                    }
                }
            }
        }

        $steps++;
    }

    return -1;
}

echo minMutation("AACCGGTT", "AACCGGTA", ["AACCGGTA"]) . "\n"; // Output: 1
echo minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]) . "\n"; // Output: 2
echo minMutation("AAAAACCC", "AACCCCCC", ["AAAACCCC", "AAACCCCC", "AACCCCCC"]) . "\n"; // Output: 3

Input: bills = [5,5,5,10,20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

class Solution {
    function lemonadeChange($bills) {
        $five = 0;
        $ten = 0;
        foreach ($bills as $bill) {
            if ($bill == 5) {
                $five++;
            } elseif ($bill == 10) {
                if ($five == 0) return false;
                $five--;
                $ten++;
            } else {
                if ($five > 0 && $ten > 0) {
                    $five--;
                    $ten--;
                } elseif ($five >= 3) {
                    $five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

class Solution {
    function minStartValue($nums) {
        $startValue = 1;
        while (true) {
            $total = $startValue;
            $isValid = true;
            foreach ($nums as $num) {
                $total += $num;
                if ($total < 1) {
                    $isValid = false;
                    break;
                }
            }
            if ($isValid) {
                return $startValue;
            }
            $startValue++;
        }
    }
}