Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.

class TreeNode {
    public $val;
    public $left;
    public $right;

    public function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    private $previous = null;
    private $inorderSuccessorNode = null;

    public function inorderSuccessor($root, $p) {
        if ($p->right !== null) {
            $leftmost = $p->right;
            while ($leftmost->left !== null) {
                $leftmost = $leftmost->left;
            }
            $this->inorderSuccessorNode = $leftmost;
        } else {
            $this->inorderCase2($root, $p);
        }
        return $this->inorderSuccessorNode;
    }

    private function inorderCase2($node, $p) {
        if ($node === null) {
            return;
        }

        $this->inorderCase2($node->left, $p);

        if ($this->previous === $p && $this->inorderSuccessorNode === null) {
            $this->inorderSuccessorNode = $node;
            return;
        }

        $this->previous = $node;

        $this->inorderCase2($node->right, $p);
    }
}

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

function shortestSuperstring($words) {
    while (count($words) > 1) {
        $maxOverlap = -1;
        $l = 0;
        $r = 0;
        $merged = '';
        for ($i = 0; $i < count($words); $i++) {
            for ($j = 0; $j < count($words); $j++) {
                if ($i != $j) {
                    $ovlp = overlap($words[$i], $words[$j]);
                    if ($ovlp > $maxOverlap) {
                        $maxOverlap = $ovlp;
                        $l = $i;
                        $r = $j;
                        $merged = merge($words[$i], $words[$j], $ovlp);
                    }
                }
            }
        }
        $words[$l] = $merged;
        array_splice($words, $r, 1);
    }
    return $words[0];
}

function overlap($a, $b) {
    $maxOverlap = 0;
    for ($i = 1; $i <= min(strlen($a), strlen($b)); $i++) {
        if (substr($a, -$i) === substr($b, 0, $i)) {
            $maxOverlap = $i;
        }
    }
    return $maxOverlap;
}

function merge($a, $b, $overlapLen) {
    return $a . substr($b, $overlapLen);
}

Input: traversal = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

class Solution {
    function twoCitySchedCost($costs) {
        usort($costs, function($a, $b) {
            return ($a[0] - $a[1]) - ($b[0] - $b[1]);
        });
        $totalCost = 0;
        $n = count($costs) / 2;
        for ($i = 0; $i < $n; $i++) {
            $totalCost += $costs[$i][0];
            $totalCost += $costs[$i + $n][1];
        }
        return $totalCost;
    }
}

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Codec {
    function rserialize($root, &$str) {
        if ($root === null) {
            $str .= "null,";
        } else {
            $str .= $root->val . ",";
            $this->rserialize($root->left, $str);
            $this->rserialize($root->right, $str);
        }
    }

    function serialize($root) {
        $str = "";
        $this->rserialize($root, $str);
        return $str;
    }

    function rdeserialize(&$data) {
        if ($data[0] === "null") {
            array_shift($data);
            return null;
        }

        $root = new TreeNode(intval(array_shift($data)));
        $root->left = $this->rdeserialize($data);
        $root->right = $this->rdeserialize($data);
        return $root;
    }

    function deserialize($data) {
        $dataArray = explode(",", $data);
        return $this->rdeserialize($dataArray);
    }
}
?>

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

class Solution {
    function minimumSemesters($N, $relations) {
        $graph = array_fill(0, $N + 1, []);
        foreach ($relations as $relation) {
            $graph[$relation[0]][] = $relation[1];
        }

        $visited = array_fill(0, $N + 1, 0);
        for ($node = 1; $node <= $N; $node++) {
            if ($this->dfsCheckCycle($node, $graph, $visited) === -1) {
                return -1;
            }
        }

        $visitedLength = array_fill(0, $N + 1, 0);
        $maxLength = 1;
        for ($node = 1; $node <= $N; $node++) {
            $length = $this->dfsMaxPath($node, $graph, $visitedLength);
            $maxLength = max($length, $maxLength);
        }
        return $maxLength;
    }

    private function dfsCheckCycle($node, $graph, &$visited) {
        if ($visited[$node] !== 0) {
            return $visited[$node];
        } else {
            $visited[$node] = -1;
        }
        foreach ($graph[$node] as $endNode) {
            if ($this->dfsCheckCycle($endNode, $graph, $visited) === -1) {
                return -1;
            }
        }
        $visited[$node] = 1;
        return 1;
    }

    private function dfsMaxPath($node, $graph, &$visitedLength) {
        if ($visitedLength[$node] !== 0) {
            return $visitedLength[$node];
        }
        $maxLength = 1;
        foreach ($graph[$node] as $endNode) {
            $length = $this->dfsMaxPath($endNode, $graph, $visitedLength);
            $maxLength = max($length + 1, $maxLength);
        }
        $visitedLength[$node] = $maxLength;
        return $maxLength;
    }
}

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));
    }
}