PHP in Leetcode

Cutting to the chase, binary searching over the solution space is the recommended approach. I wasn't able to come up with a heap solution, but if I did, I would reach for a new SplMaxHeap(). The standard library is thankfully loaded, so no need to fuss with importing.

Below I assume you're familiar with this technique. If not, it's basically 2 things:

1. A validation function to check if the guess is correct
   
2. A binary search that uses the validation function
   

The invariant used for the problem is monotonicity (monotonicicity isn't always the invariant used in binary search, but probably the most common. Just check out the find-peak-element problem as a canonical example of an invariant that isn't monotonicity).

• It's not ergonomic to echo PHP_EOL when you want to debug via printing. People seem really hesitant to add some kind of println utility to the language. Sigh.
  
• PHP provides no built-in binary search :(. I wouldn't have used it anyway for this problem though since we're not binary searching over an array, but an abstract search space.
  
• Leetcode also doesn't add any useful libraries that would help. The only module included is bcmath, which…is not helpful in the slightest for almost all problems on the platform. Sometimes you just want an ordered map¹ (balanced binary trees implement this).
  
• PHP feels more like a templating language still, rather than an application server language, making it not a preferred fit for leetcode.
  
• PHP has a lot of surprises in its own functions
  
  • Like argument order of very related functions
    
    • array_map takes the callback first
      

      function array_map(?callable $callback, array $array, array $arrays = unknown): array
      

      and ugh, ok ok, its variadic to how many arrays you pass in so the callable comes first, but this was totally unexpected.

    • array_reduce takes the array first
      

      function array_reduce(array $array, callable $callback, mixed $initial = null): ?mixed
      

  • the naming of functions themselves: strlen vs str_pad, how do you reason about when underscores happen?.
    
  • You cannot have a callable as a type hint for an instance variable….
    
  • Passing functions around seems like an afterthought of the language. Maybe I'll get used to it? You either pass in a string, which references the name of a function, an anonymous function declared directly, or a formatted array (format varies depending on what you're calling).
    

I wrote a draft of this post days ago. I think I'm beginning to kind of love php in a weird way. The tooling is there in emacs. Maybe I'll post about that later.

Leetcode is a great platform to practice language syntax. I've reviewed quite a few concepts just doing a few problems.

You can try yourself, and reach for these datastructures on leetcode without importing anything:

SplDoublyLinkedList  SplHeap              SplObserver          SplSubject
SplFileInfo          SplMaxHeap           SplPriorityQueue     SplTempFileObject
SplFileObject        SplMinHeap           SplQueue             
SplFixedArray        SplObjectStorage     SplStack

I also learned a lot by packaging a php binary index tree (it's pretty alpha, I'm still learning). One could argue one would not need a library for such a small data structure. But I made it anyway–no one else did for php, might as well. Also on packagist, which is the popular(?) package repository for php.

This section is for a cursory glance a few different uses of the Spl datastructures on leetcode, without explanation of the algorithms. PHP is pretty capable, but I'll stick with python usually.

• 2558. Take Gifts From the Richest Pile
  

  In this problem, you want a container with orderedness as you mutate it. Trees work (no builtin available). But heaps are faster.

  PHP's built in heaps don't have a heapify method like in python to turn an array into a heap in O(n).

  You also don't have something like heappushpop or heapreplace, which are faster than a single heappop.

  class Solution {
  
      /**
       * @param Integer[] $gifts
       * @param Integer $k
       * @return Integer
       */
      function pickGifts($gifts, $k) {
          $heap = new SplMaxHeap();
          foreach($gifts as $gift) {
              $heap->insert($gift);
          }
          while($k > 0 and $heap->top() > 1) {
              $max = $heap->extract();
              $insert = (int)sqrt($max);
              // echo $max, ' ', $insert, PHP_EOL;
              $heap->insert($insert);
              $k--;
          }
          $res = 0;
          foreach($heap as $gift) {
              $res += $gift;
          }
          return $res;
      }
  }
  

• 2577. Minimum Time to Visit a Cell In a Grid
  

  And you can of course do dijkstra with the SplMinHeap. You can also solve this using Dial's algorithm, a dijkstra variant, by using SplQueue or even SplDoublyLinkedList if you want to go that route.

  Here my heap elements are (curr_cost, row, column). This shows you that the heap behaves like heaps in python. Elements will be compared index-wise. That's why I didn't need a custom comparator–just store more data in a heap node.

  class Solution {
      /**
       * @param Integer[][] $grid
       * @return Integer
       */
      function minimumTime($grid) {
          $m = count($grid); $n = count($grid[0]);
          $able_to_visit = 0;
          if ($m != 1) {
              $able_to_visit += $grid[1][0] <= 1 ? 1 : 0;
          }
          if ($n != 1) {
              $able_to_visit += $grid[0][1] <= 1 ? 1 : 0;
          }
          if ($able_to_visit == 0){
              return ($n == 1 and $n == 1) ? 0 : -1;
          }
          $min_costs = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
          $min_costs[0][0] = 0;
          // var_dump($min_costs);
          $q = new \SplMinHeap();
          $q->insert([$grid[0][0], 0, 0]);
          while ($q) {
              [$curr_cost, $r, $c] = $q->extract();
              if ($r == $m - 1 and $c == $n - 1) {
                  return $curr_cost;
              }
              foreach ([[$r, $c + 1], [$r, $c - 1], [$r + 1, $c], [$r - 1, $c]] as [$next_r, $next_c]) {
                  if ($next_r < 0 or $next_r == $m or $next_c < 0 or $next_c == $n) {
                      continue;
                  }
                  $next_cost = $grid[$next_r][$next_c];
                  # take into account back,forward steps
                  if ($curr_cost + 1 >= $next_cost) {
                      $next_cost = $curr_cost + 1;
                  } else {
                      $next_cost += ($next_cost - ($curr_cost + 1)) % 2;
                  }
                  if ($next_cost < $min_costs[$next_r][$next_c]) {
                      $min_costs[$next_r][$next_c] = $next_cost;
                      $q->insert([$next_cost, $next_r, $next_c]);
                  }
              }
          }
  
          return -1;
      }
  }
  

• 862. Shortest Subarray with Sum at Least K
  Finally we can also SplDoublyLinkedList as a queue, stack, or in this case, a deque:

  class Solution {
  
      /**
       * @param Integer[] $nums
       * @param Integer $k
       * @return Integer
       */
      function shortestSubarray($nums, $k) {
          $res = PHP_INT_MAX;
  
          $prefix = new SplDoublyLinkedList();
          $acc = 0;
          foreach($nums as $i => $num) {
              $acc += $num;
              if ($acc >= $k) {
                  $res = min($res, $i + 1);
              }
              // We now check if we have a window where we made a sum >= k
              // if so, try trimming the deque from the left end until we're the window sum
              // is < k. Each step, we can record the window length.
              while ($prefix->count() and $acc - $prefix[0][0] >= $k) {
                  $res = min($res, $i - $prefix[0][1]);
                  // remove from left end
                  $prefix->shift();
              }
  
              // Because of negative numbers, the running sum, acc, can be less than it was
              // We want our prefix window to be monotonically increasing so we pop from right
              while ($prefix->count() and $acc <= $prefix->top()[0]) {
                  // remove from right end
                  $prefix->pop();
              }
              $prefix->push([$acc,$i]);
          }
  
          if ($res != PHP_INT_MAX) {
              return $res;
          }
          return -1;
      }
  }