Category Archives: LeetCode

LeetCode #1664: Ways to Make a Fair Array

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function waysToMakeFair($nums) {
        $len = count($nums);
        $ans = 0;
        
        $leftOdd = 0;
        $rightOdd = 0;
        $leftEven = 0;
        $rightEven = 0;
        
        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0) 
                $rightEven += $nums[$i];
            else
                $rightOdd += $nums[$i];              
        }
        
        for ($i=0; $i<$len; $i++) {
            if ($i%2 === 0) 
                $rightEven -= $nums[$i];
            else
                $rightOdd -= $nums[$i];
            
            if ($leftEven + $rightOdd === $rightEven + $leftOdd) $ans++;
            
            if ($i%2 === 0)
                $leftEven += $nums[$i];
            else
                $leftOdd += $nums[$i];
        }
        
        return $ans;     
    }
}

This seems simple but initially I went down wrong path, trying to use way too many arrays. I gave up and looked at https://leetcode.com/problems/ways-to-make-a-fair-array/discuss/944567/Java-O(N)-and-constant-space-beats-100-easy-solution. My solution is basically transpilation of it in PHP.

Ref: https://leetcode.com/problems/ways-to-make-a-fair-array/

LeetCode 200: Number of Islands

class Solution {

    /**
     * @param String[][] $grid
     * @return Integer
     */
    function numIslands($grid) {
        $count = 0;
        
        for ($i=0; $i<count($grid); $i++) {
            for ($j=0; $j<count($grid[$i]); $j++) {
                if ($grid[$i][$j] == "1") {
                    $count++;
                    // zero out rest of 1s
                    $this->zeroOut($grid, $i, $j);
                }
            }
        }
        
        return $count;
    }
    
    function zeroOut(&$grid, $i, $j) {
        if ($i<0 || $i>=count($grid) || $j<0 || $j>=count($grid[$i]) || $grid[$i][$j] == "0")
            return;
        
        $grid[$i][$j] = "0";
        
        $this->zeroOut($grid, $i-1, $j);
        $this->zeroOut($grid, $i+1, $j);
        $this->zeroOut($grid, $i, $j-1);
        $this->zeroOut($grid, $i, $j+1);
    }
}

I had to watch some YouTube videos for solution. Initially, I was creating over-complicated solutions to track islands.

Ref: https://leetcode.com/problems/number-of-islands/

LeetCode 88: Merge Sorted Array solution

class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    function merge(&$nums1, $m, $nums2, $n) {
        if ($n == 0) {
            return;
        }
        
        if ($m == 0) {
            for ($i=0; $i<$n; $i++) {
                $nums1[$i] = $nums2[$i];
            }
        }
        
        $i = 0;
        $j = 0;
        
        while ($i<$m && $j<$n) {
            if ($nums1[$i]<=$nums2[$j]) {
                $i++;
            } else {
                $this->array_insert($nums1, $i++, $nums2[$j]);
                $m++;
                $j++;
            }   
        }
        
        while ($j < $n) {
            $nums1[$i++] = $nums2[$j++];
        }
        
    }
    
    function array_insert(&$arr, $i, $num) {
        $endArr = array_slice($arr, $i);
        $arr[$i] = $num;
        
        for ($x=$i+1; $x<count($arr); $x++) {
            $arr[$x] = array_shift($endArr);
        }
    }
}

Not very clean but this will do for now. Ref: https://leetcode.com/problems/merge-sorted-array/

LeetCode #73: Set Matrix Zeroes

class Solution {

    /**
     * @param Integer[][] $matrix
     * @return NULL
     */
    function setZeroes(&$matrix) {
        $rowsToZeroOut = [];
        $colsToZeroOut = [];
        for ($i=0; $i<count($matrix); $i++) {
            for ($j=0; $j<count($matrix[$i]); $j++) {
                if ($matrix[$i][$j] === 0) {
                    $rowsToZeroOut[] = $i;
                    $colsToZeroOut[] = $j;
                }
            }
        }
        
        foreach($rowsToZeroOut as $r) {
            for($i=0; $i<count($matrix[$r]); $i++) {
               $matrix[$r][$i] = 0; 
            }
        }
                
        foreach($colsToZeroOut as $c) {
            for($i=0; $i<count($matrix); $i++) {
               $matrix[$i][$c] = 0; 
            }
        }
    }
}

Results:

Runtime: 52 ms, faster than 13.33% of PHP online submissions for Set Matrix Zeroes. Memory Usage: 19.8 MB, less than 80.00% of PHP online submissions for Set Matrix Zeroes.