Press "Enter" to skip to content

JS Tech Road

LeetCode 141. Linked List Cycle (javascript)

By stone on March 27, 2021

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, 104].
  • -105 <= Node.val <= 105
  • pos is -1 or a valid index in the linked-list.

Can you solve it using O(1) (i.e. constant) memory?

Idea:

Use fast and slow pointers traversal, you they can meet each other then there is a circle

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head;
    let slow = head;
    
    while (fast) {
        if (!fast.next) return false;
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

LeetCode 209. Minimum Size Subarray Sum (javascript)

By stone on March 27, 2021

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.

Example 2:

Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:

Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Constraints:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Idea:

Two pointers + tracking min size

Solution:

/**
 * @param {number} target
 * @param {number[]} nums
 * @return {number}
 */
var minSubArrayLen = function(target, nums) {
    let l = 0;
    let r = 0;
    let ans = Infinity;
    const n = nums.length;
    let total = 0;
    while (l < n) {
        while(r < n && total < target) {
            total += nums[r];
            r++;
        }
        if (total < target) break;
        ans = Math.min(ans, r - l);
        total -= nums[l];
        l++;
    }
    return ans === Infinity ? 0 : ans;
};

LeetCode 121. Best Time to Buy and Sell Stock (javascript)

By stone on March 27, 2021

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Idea:

Tracking two variables – minStock(min price of the stock) and maxGain(max profit)

Solution:

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    let maxGain = 0;
    let minStock = prices[0];
    
    for (let i = 0; i < prices.length; i++) {
        minStock = Math.min(minStock, prices[i]);
        maxGain = Math.max(maxGain, prices[i] - minStock);
    }
    return maxGain;
};

LeetCode 42. Trapping Rain Water (javascript)

By stone on March 27, 2021

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

Idea:

Two pointers traversal

Solution:

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res = 0;
    const n = height.length;
    let l = 0;
    let r = n - 1;
    
    while (l < r) {
        let min = Math.min(height[l], height[r]);
        
        // if left side is smaller
        if (min === height[l]) {
            l++;
            while (l < r && height[l] < min) {
                res += min - height[l++];
            }
        } else { // right side is smaller
            r--;
            while (l < r && height[r] < min) {
                res += min - height[r--];
            }
        }
    }
    return res;
};

LeetCode 26. Remove Duplicates from Sorted Array (javascript)

By stone on March 26, 2021

Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4]
Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Constraints:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • nums is sorted in ascending order.

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    if(nums === null || nums.length === 0) return 0;
    if(nums.length == 1) return 1;
    var count = 0;
    for(var i = 0; i < nums.length; i++) {
        if(nums[i] !== nums[i+1]){
            count++;
            nums[count] = nums[i+1];
        }
    }
    return count;
};

LeetCode 16. 3Sum Closest (javascript)

By stone on March 26, 2021

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

Idea:

Sorting the array + two pointers traversal

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    if (nums === null || nums.length <= 2) return null;
    if (nums.length === 3) return nums[0] + nums[1] + nums[2];
    // sort array first
    nums.sort((a, b) => a - b);
    let n = nums.length;
    let res = null;
    let closest = Infinity;
    // two pointers traverse
    for (let i = 0; i < n; i++) {
        let j = i + 1;
        let k = n - 1;
        while (j < k) {
            let sum = nums[i] + nums[j] + nums[k];
            let diff = sum - target;
            if (diff === 0) {
                return sum;
            } else if (diff > 0) {
                // too large, make it smaller by moving k to the left
                k--;
            } else {
                // get the postive diff
                diff = target - sum;
                // too small, make it larger by moving j to the right;
                j++;
            }
            // keep tracking the current closest and update the current sum
            if (diff < closest) {
                closest = diff;
                res = sum;
            }
        }
    }
    return res;
}

LeetCode 15. 3Sum (javascript)

By stone on March 24, 2021

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

Idea:

  • Sort nums + two pointers
  • Enumerate nums[i]
  • Use two pointers to find all possible sets of (i,  l,  r) such that
    • i < l < r
    • nums[i] + nums[l] + nums[r] === 0
  • How to move pointers?
    • nums[i] + nums[l] + nums[r] > 0, too large, decrease r
    • nums[i] + nums[l] + nums[r] > 0, too small, increase l

Optimize:

  • skip: if nums[i] > 0, then nums[i] + nums[l] + nums[r] never = 0 
  • skip same number: nums[i] === nums[i – 1]

Solution:

Time complexity: O(nlogn + n^2)

Space complexity: O(1)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const n = nums.length;
    let res = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < n - 2; i++) {
        // skip: if nums[i] > 0,
        // then nums[i] + nums[l] + nums[r] never = 0
        if (nums[i] > 0) break; 
        // skip same number
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let l = i + 1;
        let r = n - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] === 0) {
                res.push([nums[i], nums[l++], nums[r--]]);
                // skip same number
                while (l < r && nums[l] === nums[l - 1]) l++;
                while (l < r && nums[r] === nums[r + 1]) r--;
            } else if (nums[i] + nums[l] + nums[r] > 0) {
                r--;
            } else {          
                l++;
            }  
        }
    }
    return res;
};

Observer Design Pattern (PHP)

By stone on March 23, 2021

Observer is a behavioral design pattern that allows some objects to notify other objects about changes in their state.

PHP has several built-in interfaces (SplSubject, SplObserver) that can be used to make your implementations of the Observer pattern compatible with the rest of the PHP code.

Sample Code:

(Source from https://refactoring.guru/design-patterns/observer/php/example)

<?php

namespace RefactoringGuru\Observer\Conceptual;

/**
 * PHP has a couple of built-in interfaces related to the Observer pattern.
 *
 * Here's what the Subject interface looks like:
 *
 * @link http://php.net/manual/en/class.splsubject.php
 *
 *     interface SplSubject
 *     {
 *         // Attach an observer to the subject.
 *         public function attach(SplObserver $observer);
 *
 *         // Detach an observer from the subject.
 *         public function detach(SplObserver $observer);
 *
 *         // Notify all observers about an event.
 *         public function notify();
 *     }
 *
 * There's also a built-in interface for Observers:
 *
 * @link http://php.net/manual/en/class.splobserver.php
 *
 *     interface SplObserver
 *     {
 *         public function update(SplSubject $subject);
 *     }
 */

/**
 * The Subject owns some important state and notifies observers when the state
 * changes.
 */
class Subject implements \SplSubject
{
    /**
     * @var int For the sake of simplicity, the Subject's state, essential to
     * all subscribers, is stored in this variable.
     */
    public $state;

    /**
     * @var \SplObjectStorage List of subscribers. In real life, the list of
     * subscribers can be stored more comprehensively (categorized by event
     * type, etc.).
     */
    private $observers;

    public function __construct()
    {
        $this->observers = new \SplObjectStorage();
    }

    /**
     * The subscription management methods.
     */
    public function attach(\SplObserver $observer): void
    {
        echo "Subject: Attached an observer.\n";
        $this->observers->attach($observer);
    }

    public function detach(\SplObserver $observer): void
    {
        $this->observers->detach($observer);
        echo "Subject: Detached an observer.\n";
    }

    /**
     * Trigger an update in each subscriber.
     */
    public function notify(): void
    {
        echo "Subject: Notifying observers...\n";
        foreach ($this->observers as $observer) {
            $observer->update($this);
        }
    }

    /**
     * Usually, the subscription logic is only a fraction of what a Subject can
     * really do. Subjects commonly hold some important business logic, that
     * triggers a notification method whenever something important is about to
     * happen (or after it).
     */
    public function someBusinessLogic(): void
    {
        echo "\nSubject: I'm doing something important.\n";
        $this->state = rand(0, 10);

        echo "Subject: My state has just changed to: {$this->state}\n";
        $this->notify();
    }
}

/**
 * Concrete Observers react to the updates issued by the Subject they had been
 * attached to.
 */
class ConcreteObserverA implements \SplObserver
{
    public function update(\SplSubject $subject): void
    {
        if ($subject->state < 3) {
            echo "ConcreteObserverA: Reacted to the event.\n";
        }
    }
}

class ConcreteObserverB implements \SplObserver
{
    public function update(\SplSubject $subject): void
    {
        if ($subject->state == 0 || $subject->state >= 2) {
            echo "ConcreteObserverB: Reacted to the event.\n";
        }
    }
}

/**
 * The client code.
 */

$subject = new Subject();

$o1 = new ConcreteObserverA();
$subject->attach($o1);

$o2 = new ConcreteObserverB();
$subject->attach($o2);

$subject->someBusinessLogic();
$subject->someBusinessLogic();

$subject->detach($o2);

$subject->someBusinessLogic();

Output:

Subject: Attached an observer.
Subject: Attached an observer.

Subject: I'm doing something important.
Subject: My state has just changed to: 2
Subject: Notifying observers...
ConcreteObserverA: Reacted to the event.
ConcreteObserverB: Reacted to the event.

Subject: I'm doing something important.
Subject: My state has just changed to: 4
Subject: Notifying observers...
ConcreteObserverB: Reacted to the event.
Subject: Detached an observer.

Subject: I'm doing something important.
Subject: My state has just changed to: 1
Subject: Notifying observers...
ConcreteObserverA: Reacted to the event.

Adapter (PHP)

By stone on March 23, 2021

Adapter is a structural design pattern, which allows incompatible objects to collaborate. The Adapter acts as a wrapper between two objects. It catches calls for one object and transforms them to format and interface recognizable by the second object. It is often used to make existing classes work with others without modifying their source code

Use case: It’s very often used in systems based on some legacy code. In such cases, Adapters make legacy code work with modern classes.

Sample Code: (Source from https://refactoring.guru/design-patterns/adapter/php/example#example-1)

<?php

namespace RefactoringGuru\Adapter\RealWorld;

/**
 * The Target interface represents the interface that your application's classes
 * already follow.
 */
interface Notification
{
    public function send(string $title, string $message);
}

/**
 * Here's an example of the existing class that follows the Target interface.
 *
 * The truth is that many real apps may not have this interface clearly defined.
 * If you're in that boat, your best bet would be to extend the Adapter from one
 * of your application's existing classes. If that's awkward (for instance,
 * SlackNotification doesn't feel like a subclass of EmailNotification), then
 * extracting an interface should be your first step.
 */
class EmailNotification implements Notification
{
    private $adminEmail;

    public function __construct(string $adminEmail)
    {
        $this->adminEmail = $adminEmail;
    }

    public function send(string $title, string $message): void
    {
        mail($this->adminEmail, $title, $message);
        echo "Sent email with title '$title' to '{$this->adminEmail}' that says '$message'.";
    }
}

/**
 * The Adaptee is some useful class, incompatible with the Target interface. You
 * can't just go in and change the code of the class to follow the Target
 * interface, since the code might be provided by a 3rd-party library.
 */
class SlackApi
{
    private $login;
    private $apiKey;

    public function __construct(string $login, string $apiKey)
    {
        $this->login = $login;
        $this->apiKey = $apiKey;
    }

    public function logIn(): void
    {
        // Send authentication request to Slack web service.
        echo "Logged in to a slack account '{$this->login}'.\n";
    }

    public function sendMessage(string $chatId, string $message): void
    {
        // Send message post request to Slack web service.
        echo "Posted following message into the '$chatId' chat: '$message'.\n";
    }
}

/**
 * The Adapter is a class that links the Target interface and the Adaptee class.
 * In this case, it allows the application to send notifications using Slack
 * API.
 */
class SlackNotification implements Notification
{
    private $slack;
    private $chatId;

    public function __construct(SlackApi $slack, string $chatId)
    {
        $this->slack = $slack;
        $this->chatId = $chatId;
    }

    /**
     * An Adapter is not only capable of adapting interfaces, but it can also
     * convert incoming data to the format required by the Adaptee.
     */
    public function send(string $title, string $message): void
    {
        $slackMessage = "#" . $title . "# " . strip_tags($message);
        $this->slack->logIn();
        $this->slack->sendMessage($this->chatId, $slackMessage);
    }
}

/**
 * The client code can work with any class that follows the Target interface.
 */
function clientCode(Notification $notification)
{
    // ...

    echo $notification->send("Website is down!",
        "<strong style='color:red;font-size: 50px;'>Alert!</strong> " .
        "Our website is not responding. Call admins and bring it up!");

    // ...
}

echo "Client code is designed correctly and works with email notifications:\n";
$notification = new EmailNotification("developers@example.com");
clientCode($notification);
echo "\n\n";


echo "The same client code can work with other classes via adapter:\n";
$slackApi = new SlackApi("example.com", "XXXXXXXX");
$notification = new SlackNotification($slackApi, "Example.com Developers");
clientCode($notification);

Output:

Client code is designed correctly and works with email notifications:
Sent email with title 'Website is down!' to 'developers@example.com' that says '<strong style='color:red;font-size: 50px;'>Alert!</strong> Our website is not responding. Call admins and bring it up!'.

The same client code can work with other classes via adapter:
Logged in to a slack account 'example.com'.
Posted following message into the 'Example.com Developers' chat: '#Website is down!# Alert! Our website is not responding. Call admins and bring it up!'.

Singleton (PHP)

By stone on March 23, 2021

Singleton is a creational design pattern, which ensures that only that object exists in the memory and provides a single point of access to it for any other code.

<?php

namespace JSTechRoad\Singleton;

// The Singleton class defines the `GetInstance` method 
// that serves as an alternative to constructor and lets 
// clients access the same instance of this class forever.
class Singleton
{
    // The Singleton's instance is stored in a static field
    private static $instances = [];

    // The Singleton's constructor should always be private
    // to prevent direct construction calls with the `new` operator.
    protected function __construct() { }

    // Singletons should not be cloneable.
    protected function __clone() { }

    // Singletons should not be restorable from strings.
    public function __wakeup()
    {
        throw new \Exception("Cannot unserialize a singleton.");
    }

    // static method that controls the access to the singleton
    // instance. 
    public static function getInstance(): Singleton
    {
        $cls = static::class;
        if (!isset(self::$instances[$cls])) {
            self::$instances[$cls] = new static();
        }

        return self::$instances[$cls];
    }

    // any singleton should define some business logic, which can be
    // executed on its instance.
    public function someFunction()
    {
        // ...
    }
}

// testing function
function clientCode()
{
    $s1 = Singleton::getInstance();
    $s2 = Singleton::getInstance();
    if ($s1 === $s2) {
        echo "Singleton works!";
    } else {
        echo "Singleton failed!";
    }
}

clientCode();