HackerRank: New Year Chaos

Here is my solution to New Years Chaos problem from HackerRank. The first solution had a bug:

function minimumBribes(q) {
    let bribes = 0;
    
    for (let i=0; i<q.length-2; i++) {
        if (q[i] - (i+1) > 2) {
            console.log('Too chaotic');
            return;
        }
        // compare index to element, works great except when a smaller element is pushed way back
        if (q[i] - (i+1) > 0) {
          bribes += q[i] - (i+1);
        } 
    }
    console.log(bribes);
}

Second solution had O(n^2) complexity:

function minimumBribes(q) {
    let bribes = 0;
    
    for (let i=0; i<q.length; i++) {
        if (q[i] - (i+1) > 2) {
            console.log('Too chaotic');
            return;
        }
        // if there is a bigger  element before this element
        // then that element must have bribed this element
        for (let j=0; j<i; j++) {
            if (q[i]<q[j]) {
                bribes++;
            }
        }
    }
    console.log(bribes);
}

At this point, I looked up in comments and found an optimal solution:

function minimumBribes(q) {
    let bribes = 0;
    let expectedFirst = 1;
    let expectedSecond = 2;
    let expectedThird = 3;
    
    for (let i=0; i<q.length-0; i++) {
        if (q[i] == expectedFirst) {
            expectedFirst = expectedSecond;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedSecond) {
            ++bribes;
            expectedSecond = expectedThird;
            ++expectedThird;
        } else if (q[i] == expectedThird) {
            bribes += 2;
            ++expectedThird;
        } else {
            console.log("Too chaotic");
            return;
        }
    }
    console.log(bribes);
}

LeetCode 200: Number of Islands

I had to watch some YouTube videos for the solution to [this problem][1]. I am not sure if this is the best solution though, one day I will revisit it.


    /**
     * @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);
    }
}```

 [1]: https://leetcode.com/problems/number-of-islands/

Cigarette

Feeling so empty, and hollow inside,
Cannot believe I am writing a poem to a cigarette,
but I feel so unsatisfied, unfulfilled,
like this poem, half-finished.


LeetCode 42. Trapping Rain Water

My solution to LeetCode 42. Trapping Rain Water in JavaScript.

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let maxLeft = 0, maxRight = 0;
    
    let left = 0;
    let right = height.length -1;
    let total = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left]>maxLeft) {
                maxLeft = height[left];
            } else {
               total += maxLeft-height[left]
            }
            left++;
        } else {
            if (height[right]>maxRight) {
                maxRight = height[right];
            } else {
               total += maxRight-height[right]
            }
            right--;
        }    
    }
    return total;
};

Oneness of Humanity

O my friend, a heart does not need hate.
All love good but do not even hate bad.
Who does not want the softness of flowers?
But do not be afraid of sharpness of thorns.
There is same blood in the veins of the thorn.
It is brought up by same evening breeze of the spring.

Do not throw away dying flowers.
Yesterday, they were the glamor of the garden.
Once they were also part of the world of perfumes.
O passerby! Do not kick dust on their leaves.
Though they are no longer in the feast.
They were raised in the laps of same morning breeze.

Living or not living, all are basically one.
Earth and heavens, both were made from one.
There are millions of idol, but God is one.
All hearts are different, but feeling is one.
Clothes are same, but shops are different.
Meanings are same, but languages are different.

The lightkeeper is also human.
And the one who is lost in the dark sea is also human.
The best friend is also human.
And the worst enemy is also human.
It doesn’t matter if you run away from death or life.
But, O Human! Never run away from humans.

by Josh Malihabadi

I translated this poem in 1999 for a school project.


LeetCode 1089: Duplicate Zeros

LeetCode 1089: Duplicate Zeros solution in PHP.

class Solution {

    /**
     * @param Integer[] $arr
     * @return NULL
     */
    function duplicateZeros(&$arr) {
        $len = count($arr);
        for ($i=0; $i < $len; $i++) {
            if (0 === $arr[$i]) {
                array_splice($arr, $i++, 0, 0);
            }
        } 
        array_splice($arr, $len);
    }
}

Broken Dreams/Bheegi Yadein by Junoon

By Junoon

Not sure if I translated this this or found this translation on the web, Google search shows only this post though.


LeetCode 11. Container With Most Water

Here is my solution to Container with Most Water in JavaScript.

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0;
    let right = height.length-1;
    let maxWater = 0;
    
    while (left < right) {
        const water = (right-left) * Math.min(height[left], height[right]);

        if (water > maxWater) {
            maxWater = water;
        }
        
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
};

LeetCode 1: Two Sum

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const numsToFind = {};
    
    for (let i=0; i<nums.length; i++) {
        const numToFind = nums[i];
        if (numsToFind[numToFind] >= 0) {
            return [i, numsToFind[numToFind]];
        }
        numsToFind[target - numToFind] = i;    
    }
};

My solution for Two Sum problem in PHP.


Yellow Bus and Red Car

Once upon a time there was a Yellow bus. Yellow bus was very fast, but there was a Red car which was faster. One day, Red car challenged yellow bus for a race.

They decided to race from Dallas to Houston. It was the longest race ever. All the cars gathered around the highway.

Referee said “1, 2, 3, Go!”

Yellow bus goes zoom zoom. But red car goes zoom zoom zooooom. And Red car was faster and it was winning.

After a while Red car looked in its rearview mirror and didn’t see Yellow bus at all. Red car’s engine was overheating, and it was running low on gas. Up ahead was a gas station.

Red car decided to pull into gas station to refill gas and and cool down the engine in a shade.

While resting in the shade, it fell asleep.

Yellow bus, however, didn’t stop. It kept going and going until it crossed the finish line.

Red car woke up and realized, it slept for too long. It raced to finish line but Yellow bus had already won the race.

Red car was surprised and asked how did you not take a break, Yellow bus said by going fast but not too fast. They laughed and then went to eat ice cream.

Moral of story, go fast but not too fast.