Given an array A of non-negative integers, the array is squareful if for every pair of adjacent elements, their sum is a perfect square.

Return the number of permutations of A that are squareful. Two permutations A1 and A2 differ if and only if there is some index i such that A1[i] != A2[i].

Example 1:

Output: 2
Explanation: 
[1,8,17] and [17,8,1] are the valid permutations.

Example 2:

Input: [2,2,2]
Output: 1

Note:

1 <= A.length <= 12
0 <= A[i] <= 1e9

Solved this with PHP.

1. Go through the input and construct array ‘peers’
   1. peers holds an array of pointers pointing to all possible ‘partners’ in the input.
   2. For example, [1 => [8=>ref(8)], 8 => [1=>ref(1), 17=>ref(17)], 17 => [8=>ref(8)]]
2. Meanwhile, another array stat collect all numbers and its occurrence.
3. Then peers is recursive. so it’s like a tree, with infinite depth.
4. Starting from the root of peers, if found any number in ‘stat’, update (-1) stat, and move on to peers’ children
   1. if cannot find any match at some points, break;
   2. since stat is finite, the recursive func will run forever
5. Calculate the sum.

Works well with even larger input length.

16ms runtime w/ 14.7M RAM

Class Solution {

    /**
     * @param Integer[] $ls
     * @return Integer
     */
    function numSquarefulPerms($ls) {
        
        if(count($ls) <= 1){
            return 0;
        }
        
        $peers = [];
        $stat = [];
        
        for($i = 0; $i < count($ls); $i++){
            // Insert/Update stat
            if(!isset($stat[$ls[$i]])){
                $stat[$ls[$i]] = 1;
            } else {
                $stat[$ls[$i]] ++;
            }
            
            for($j = $i + 1; $j < count($ls); $j++){

                $value_i = $ls[$i];
                $value_j = $ls[$j];
                
                if(!isset($peers[$value_i])){
                    $peers[$value_i] = [];
                }
                if(!isset($peers[$value_j])){
                    $peers[$value_j] = [];
                }
                if($this -> isPerfectSquare($ls[$i] + $ls[$j])){
                    $peers[$value_i][$value_j] = &$peers[$value_j];
                    if($ls[$j] !== $ls[$i]){
                        $peers[$value_j][$value_i] = &$peers[$value_i];
                    }
                }
            }
        }
        // If any number has no partner
        foreach($peers as $p){
            if($p === []){
                return 0;
            }
        }
        return $this->traversal($stat, $peers, count($ls));
    }
    
    // Check if number is perfect square w/ small optimization
    function isPerfectSquare($num){
        $last_digit = $num % 10;
        if($last_digit == 2 ||
            $last_digit == 3 ||
            $last_digit == 7 ||
            $last_digit == 8 
          ) 
            return false;
        
        $sqrt = sqrt($num);
        return $sqrt == floor($sqrt);
    }
    
    function traversal($nums, &$tree, $max){
        $count = 0;
        var_dump($nums);
        if(empty($nums)){
            echo "Add\r\n";
            return 1;
        }
        foreach($tree as $k => $v){
            // Make a copy
            $nums_copy = $nums;
            if(isset($nums_copy[$k])){
                // If exist decrease, if last remove
                if($nums[$k] > 1){
                    $nums_copy[$k] --;
                } else {
                    unset($nums_copy[$k]);
                }
                // move on to children
                $count += $this -> traversal($nums_copy, $v, $max - 1); 
            }     
        }
        return $count;
    }
}

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    // remove elements from both ends

    
    while ((nums1.length + nums2.length)/2 > 1){
        // If any of the arrays is empty, rm the other one
        if(nums1.length == 0){
            nums2.shift();
            nums2.pop();
        } else if(nums2.length == 0){
            nums1.shift();
            nums1.pop();
        } else {
            if(nums1[0] < nums2[0]){
                nums1.shift();
            } else {
                nums2.shift();
            }
            // if nums1 is empty 
            //   OR nums1's tail is less than nums2's, remove nums2
            if(nums1.length == 0 || 
               nums1[nums1.length -1] < nums2[nums2.length -1]){
                nums2.pop();
            } else {
                nums1.pop();
            }
        }
    }
    // only 1 or 2 elements remain now
    var r = nums1.concat(nums2);
    // send average for two
    if(r.length > 1){
        return (r[0]+r[1])/2;
    } else {
    // or just the last element
        return r[0];
    }
};