1007. Minimum Domino Rotations For Equal Row

In a row of dominoes, A[i] and B[i] represent the top and bottom halves of the i-th domino.  (A domino is a tile with two numbers from 1 to 6 – one on each half of the tile.)

We may rotate the i-th domino, so that A[i] and B[i] swap values.

Return the minimum number of rotations so that all the values in A are the same, or all the values in B are the same.

If it cannot be done, return -1.

 

Example 1:

 

Input:

A = [2,1,2,4,2,2], B = [5,2,6,2,3,2]

Output:

2

Explanation:

The first figure represents the dominoes as given by A and B: before we do any rotations.
If we rotate the second and fourth dominoes, we can make every value in the top row equal to 2, as indicated by the second figure.

Example 2:

Input:

A = [3,5,1,2,3], B = [3,6,3,3,4]

Output:

-1

Explanation:

In this case, it is not possible to rotate the dominoes to make one row of values equal.

 

Note:

  1. 1 <= A[i], B[i] <= 6
  2. 2 <= A.length == B.length <= 20000

Thoughts:

  • Two possible values, A[0] and B[0]
  • For each possible value, and foreach index, if one doesn’t have while the other does add 1 to counter
  • There are two counters for each possible values, {B->A, A->B}
  • Return the best result

The speaking of domino’s top and bottom is misleading, no domino has the same value for top and bottom. Why not just say a single digit number?

 


class Solution {

    /**
     * @param Integer[] $A
     * @param Integer[] $B
     * @return Integer
     */
    function minDominoRotations($A, $B) {
  
        $p = [];      // Possible Values
        $p[] = $A[0]; // Either First elem if A
        $p[] = $B[0]; // Either First elem of B
        $r = [];      // List of mins 

        // Foreach Possible Values
        foreach($p as $s){
            $x = 0;   // Counter, swap B to match A's Value
            $y = 0;   // Counter, swap A to match B's Value
            $nf = false;    // For a possible value, not found both Swap A to B and B to A
            for($i = 0;$i < count($A); $i ++){
                if($s == $A[$i] && $s !== $B[$i]){
                    $y ++;
                } elseif ($s == $B[$i] && $s !== $A[$i]){
                    $x ++;
                } else if($s !== $A[$i] && $s !== $B[$i]) {
                    // If possible value not found in either array, move to next possible value.
                    $nf = true;
                    break;
                }
                
            }

            if(!$nf){
                // If found
                if($x == 0 || $y ==0){
                    // O is the best, no need to continue
                    return 0;
                }
                // Otherwise push the best counter result to array
                $r[] = min($x, $y);
            }

        }
        // When all possible values are no longer possible :(
        if(empty($r)){
            return -1;
        }
        // Otherwise return the best result
        return min($r);
    }
}

 

807. Max Increase to Keep City Skyline

In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the “skyline” when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city’s skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:


Input:

 grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

Output:

 35

Explanation:

 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

  • 1 < grid.length = grid[0].length <= 50.
  • All heights grid[i][j] are in the range [0, 100].
  • All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Thoughts;

  1. Vertical & Horizontal  scan, generate skyline view array
  2. Max increment = min(vertical, horizontal).
  3. Result = Sum (each max increment)

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function maxIncreaseKeepingSkyline($grid) {
        if(empty($grid)){
            return 0;
        }
        $result = 0;
        $h = array_fill(0,count($grid), 0);
        $v = array_fill(0,count($grid[0]), 0);
        
        for($i = 0; $i < count($grid); $i ++){
            $h[$i] = max($grid[$i]);
            for($j = 0; $j < count($grid[0]); $j ++){
                if($grid[$i][$j] > $v[$j]){
                    $v[$j] = $grid[$i][$j];
                }
            }
        }
        
        for($i = 0; $i < count($grid); $i ++){
            for($j = 0; $j < count($grid[0]); $j ++){
                $max = min($h[$i], $v[$j]);
                $result += $max - $grid[$i][$j];
            }
        }
        return $result;
    }
}

 

987. Vertical Order Traversal of a Binary Tree

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation:
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2:

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation:
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report “[1,5,6]”, the node value of 5 comes first since 5 is smaller than 6.

Note:

The tree will have between 1 and 1000 nodes.
Each node’s value will be between 0 and 1000.

My notes.

Mind the case.

[0,8,1,null,null,3,2,null,4,5,null,null,7,6]

          0
     8         1
          3         2
              4,5
          6         7

Rendered by Leetcode, with my lines added

Screen Shot 2019-02-18 at 15.10.02

My Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this-&gt;val = $value; }
 * }
 */
class Solution {

    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function verticalTraversal($root) {
        $result = [];
        $this-&gt;traversalHelper($root,0,0,$result);
        // Sort by col, from left to right
        ksort($result);
        foreach($result as &amp;$rs){
            $new_sub = [];
            // foreach col, sort by depth from top to bottom
            ksort($rs);
            foreach($rs as &amp;$r){
                // Same depth, sort by value asc, according to spec
                asort($r);
                $new_sub = array_merge($new_sub,$r);
            }
            $rs = $new_sub;
        }
        return $result;
    }
    
    // Recursion, go through the tree
    function traversalHelper($root, $pos,$depth, &amp;$result) {
        if($root !== null){
            if(!isset($result[$pos])){
                $result[$pos] = [];
            } 
            if(!isset($result[$pos][$depth])){
                $result[$pos][$depth] = [];
            }
            $result[$pos][$depth][] = $root-&gt;val;
            
            $this-&gt;traversalHelper($root-&gt;left, $pos - 1,$depth+1, $result);
            $this-&gt;traversalHelper($root-&gt;right, $pos + 1,$depth+1, $result);
        }
    }
}

 

991. Broken Calculator

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.
Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2

Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3

Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023

Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 109
1 <= Y <= 109

class Solution {

    /**
     * @param Integer $x
     * @param Integer $y
     * @return Integer
     */
    function brokenCalc($x, $y) {
        $c = 0;
        while($x < $y){
           if($y % 2 == 0){
                $y /= 2;
            } else {
                $y ++;
           } 
            $c ++;
        }
        return $c + $x - $y;
    }
}

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {\
    // palindromic str for single round
    var o = ""; 
    // Longest palindromic str
    var max = "";
    for (var i = 0; i < s.length; i ++){
        var x = i;
        var y = i;
        // Include current char
            o = s[i];
            
            // Collect Same letters on the right
        while(s[y+1] == s[y]){
            y ++; i ++;
            // append same char on the right to p_str
            o += s[i];
        } 
        
        // Then check both sides one by one
        // Make sure x & y in range, then compare both ends
        while(x > 0 
                && y < s.length-1 
                && s[x-1] == s[y+1]){
            o = s[x-1] + o + s[y+1];
            // Separate x & y for one more step
            x--; y++;
        }
        
        // Save, if longer than current max record
        if(o.length > max.length){
            max = o;
        }
        
    }
    
    return max;
};

3. Longest Substring Without Repeating

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    var max = 0;
    var a = [];
    for (var i = 0; i < s.length; i ++){
        // If element exists, remove any other elements before it, 
        // and itself
        if(a.includes(s[i])){
            a.splice(0, a.indexOf(s[i]) + 1);
        }
        // Append new element
        a.push(s[i]);
        // Update result
        if(max < a.length){
            max = a.length;
        }
    }
    return max;
};