Forem: Samuel Hinchliffe 🚀

2. Add Two Numbers 🚀

Samuel Hinchliffe 🚀 — Mon, 10 Oct 2022 15:31:13 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '2. Add Two Numbers' question. A medium question that is a little tricky.
Question:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Explaining The Question

This Question is rated Medium. Which would be fair to say if you've just started learning Linked Lists. See this question is a really odd one. It's more of a maths question with Linked Lists thrown in.

We're given 2 linked lists. Which represents two numbers (2->4->3, 5->6->4). We need to add the numbers together and return the result as a list. Which sounds really tough to do.

The way we're going to solve this is by going back to when you first learnt how to add big numbers with that carry system. We're going to implement that exact system.

We're going to go through our lists at the exact same time, with a pointer on each list. That'll be our column. We will add up all those numbers in that column (2 + 5 = 7). If that number is greater than 9, we know we need to carry that number to the next column. So what we do is we {sum} - 10. With a note to carry a 1 to the next col. We then take that now < 10 sum and create it's own ListNode. Moving to all the next list nodes.

We repeat this until we have no more lists left and more carry numbers left.
It's the exact same system that many people are taught at a young age.

Big O Notation:

Time Complexity: O(n + m) | Where n / m is the length of the list we're traversing.
Space Complexity: O(1) | We don't use extra space and we don't count the output as extra space as it's expected.

Leetcode Results:

See Submission Link:

The Solution


var addTwoNumbers = function (l1, l2) {

    const sentinel_node = new ListNode(0);
    let   number_carry  = 0;
    let   head          = sentinel_node;
    let   sum           = 0;

    while (l1 || l2 || sum) {

        // Add the numbers together.
        sum += (l1) ? l1.val : 0;
        sum += (l2) ? l2.val : 0;

        // Do we need a number carry?
        if (sum >= 10) {
            number_carry = 1;         // Add carry
            sum          = sum - 10;  // Update sum to 1 int
        }

        // Add new node (With our new sum)
        head.next = new ListNode(sum, null);
        head      = head.next;

        // Move both lists forward if possible
        l1 = (l1) ? l1.next : null;
        l2 = (l2) ? l2.next : null;


        // Carry the 1 if so.
        sum          = number_carry;
        number_carry = 0;
    }

    return sentinel_node.next;
};

287. Find the Duplicate Number 🚀

Samuel Hinchliffe 🚀 — Thu, 29 Sep 2022 13:49:56 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '287. Find the Duplicate Number' question. An question that you'll never solve in constant space without Google (Or knowing floyd's turtle and hare)

Question:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

Input: nums = [1,3,4,2,2]
Output: 2

Explaining The Question

This Question is rated Medium. Which is I would say is in-accurate, especially if you've never solved 141. Linked List Cycle or 142. Linked List Cycle. I'd almost say this was impossible to solve without knowing how to solve both of these problems, unless you're Robert W. Floyd himself.

So how do we really solve this question? floyd's turtle and hare is the only way to solve this question to my understanding.
Alright, so you know we can solve it with this Turtle & Hare approach. But what the hell is it you ask?

Floyds Turtle & Hare is an algorithm designed to find the node that loops back upon. Meaning, it detects cycles in a list. Normally you would do this in a Linked List, but this time we have a Linked List disguised as an Array. Where nums[i] represents the next node.

How does it work?
Well the math behind that is complicated, see for yourself: Proof;
;

Basically, where we move one pointer 1 node at a time (slow) and another a double the speed (fast), our fast will eventually lap around and land on slow. Which mean's a loop has occurred because they shouldn't be able to meet due to their speed difference. So we move our fast pointer back to the start and go 1 node at a time until the pointer meet again. It just so happens when they meet again, they will always meet on the looping node.

The code to achieve this is painfully simple.

Big O Notation:

Time Complexity: O(n) | Where n is the length of the list we're traversing.
Space Complexity: O(1) | We don't use extra space.

Leetcode Results:

See Submission Link:

The Solution

var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    fast = 0;

    do {
        slow = nums[slow];
        fast = nums[fast];
    } while (slow != fast);

    return slow
};

76. Minimum Window Substring 🚀

Samuel Hinchliffe 🚀 — Sun, 11 Sep 2022 14:34:32 +0000

The Question

For this article we will be covering Leetcode's '76. Minimum Window Substring' question. An Advanced Sliding Window Problem.

Question:

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.
A substring is a contiguous sequence of characters within the string.



Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Explaining The Question

This Question is rated Hard. Which is I would agree with if you haven't solved 424. Longest Repeating Character Replacement as this problem will require a similar solution in structure.

This question requires the use of the Sliding Window technique, where we're attempting to find the shortest window that contains our substring. We then need to return that substring.

Recommended Knowledge

What do we know?

We know that our input will only ever contain uppercase and lowercase english letters.

How we're going to do it:

We're going to go through our list with 2 pointers. Left and Right. Where Left is the start of our current substring and our right is the end of it. Each time we move our right pointer we ask 'Does this window contain our target?' if so we shrink our window by moving our left pointer. We keep doing this until the target is no longer within the window.

We achieve this with the use of Hashmaps and pointers. As well as a little helper function.

We firstly turn our target string into a hashmap so we can easily ask later on if we have all the chars required to fit into the target.
We also do the same for the input string hashmap, but we leave that empty for now as that hashmap will represent whats in our sliding window.
We then create our helper function that let's us know if the current window contains our substring or not. We do this by getting all the chars and their counts from the target hashmap and comparing it with the sliding windows hashmap.
We then go through our string, adding it to our hashmap that represents the sliding window.
If our current window contains the target, we will shorten our window by reducing our left pointer. Each time checking if this is our new smallest window, if so that becomes our output / return value. We also remove the left pointers hashmap value as it's no longer in the sliding window anymore.

Big O Notation:

Time Complexity: O(52 * n) | Where 52 of possible chars and where N represents the length of the input itself. The reason it's 52 * n, is because for each item in our string, we're going to be possibly going over a hashmap of 52 length.
Space Complexity: O(104) | As in the worst case, both of our hashmaps will be totally full. As we have 2 hashmaps that contain up to 52 entries.

Leetcode Results:

See Submission Link:

The Solution



var minWindow = function (s, t) {

    const target_map = new Map();
    const string_map = new Map();
    let shortest = "";

    for (const char of t) {
        target_map.set(char, (target_map.get(char) ?? 0) + 1);
    }

    const substring_contains_target = () => {
        for (const [char, count] of target_map) {
            if (!string_map.has(char) || string_map.get(char) < count) return false;
        }
        return true;
    };

    let left = 0;
    for (let i = 0; i < s.length; i++) {
        const char = s[i];
        string_map.set(char, (string_map.get(char) ?? 0) + 1);
        while (substring_contains_target()) {
            const distance = i - left + 1;
            if (shortest == "" || distance < shortest.length) {
                shortest = s.substring(left, i + 1);
            }
            string_map.set(s[left], string_map.get(s[left]) - 1);
            left += 1;
        }
    }

    return shortest;
};

55. Jump Game 🚀

Samuel Hinchliffe 🚀 — Thu, 04 Aug 2022 10:52:19 +0000

The Question

For this article we will be covering Leetcode's '55. Jump Game' question. This question is a classic problem. It's a Greedy Algorithm problem or a Dynamic Programming problem depending on your perspective.

Question:

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Explaining The Question

This Question is rated Medium. Which I would say is accurate if you're using the Greedy Algorithm technique. If you're using the Dynamic Programming technique, then this question could be considered a Hard. For this question, we will be using the Greedy Algorithm technique.

What we're being asked to do, is jump from index 0 to the last index of the array. Where each index represents the distance in which it can jump to. So if you're on a index with the value of 2, you can jump 2 indexs forward (Or 1 if you want). This issue at first seems trivial, Brute Force all paths and if we ever reach the last index, we're done. Which mean's this is almost a graph problem. Although, this is not the most efficient way to solve this problem. It's O(n^n) time, it's terribly slow.

Instead, we're going to Greedy and do this O(n) time.

Recommended Knowledge

What do we know?

We've been given an array of non-negative integers.
Each index represents the distance in which we can jump to, we need to jump to the last index.

How we're going to do it:

Initially, you may think, 'Well starting from index 0, keep jumping until we reach the last index and backtrack on a invalid path'. This is a Brute Force solution, a Dynamic Programming solution, that is much alike a Graph Problem with Backtracking.

Instead, we're going to reverse the logic, instead of starting from Index 0, why not start from the last index? We will have a goal post, which is initially the last index, the goal of the goal post is to reach index 0. We will iterate over the array backwards asking, 'Can this element jump to the goal post?' if so, that element becomes the new goal post because it can jump to it. We keep doing this until we've been through the entire array. If we've reached the first index, we can jump to the last index, if the goal post is not, we cannot jump to it.

We're going to initialize a goal post, which is initially the last index.
We're going to setup a For Loop that iterates over the array backwards.
We ask each element 'Can you jump to or over the goal post from here?' if so, we set the goal post to that element.
If not, we continue looping.
We repeat this logic until we've been through the entire array.
Is the goal post now at the first index? If so we can jump to the last index, if not, we cannot jump to it.

Big O Notation:

Time Complexity: O(n) | Where n is the length of the array.
Space Complexity: O(1) | As we never allocate any additional memory.

Python Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:

        goal_post = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            if i + nums[i] >= goal_post:
                goal_post = i

        return (goal_post == 0)

Java Solution

class Solution {
    public boolean canJump(int[] nums) {

        int goal_post = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post) {
                goal_post = i;
            }
        }

        return (goal_post == 0) ? true : false;
    }
}

C++ Solution

class Solution {
public:
    bool canJump(vector<int>& nums) {

        int goal_post = nums.size() - 1;

        for (int i = nums.size() - 1; i >= 0; i--) {
            int jump_distance = i + nums[i];
            if (jump_distance >= goal_post){
                goal_post = i;
            }
        }

        return (!goal_post) ? true : false;
    }
};

Javascript Solution

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {

    let goal_post = nums.length - 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const jump_distance = i + nums[i];
        if (jump_distance >= goal_post) {
            goal_post = i;
        }
    }

    return !goal_post ? true : false;
};

53. Maximum Subarray 🚀

Samuel Hinchliffe 🚀 — Wed, 03 Aug 2022 14:44:00 +0000

The Question

For this article we will be covering Leetcode's '53. Maximum Subarray' question. This question is a classic problem. It's a Greedy Algorithm problem.

Question:

Given an integer array nu`ms, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
A subarray is a contiguous part of an array.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Explaining The Question

This Question is rated Medium. Which is arguable, this could be considered a Easy question, if you're not using the Divide and Conquer technique. If you're using the Greedy Algorithm technique, then this question is considered a Easy.

We're going to be using Kadane's Algorithm, a Dynamic Programming and Greedy Algorithm. Kadane's Algorithm is a greedy algorithm that finds the maximum sum of a subarray. It's a very simple algorithm, and it's entirely possible to come up with this algorithm without knowing it. It's very intuitive.

Recommended Knowledge (Or what you're about to learn)

What do we know?

We have an array, that possibly has negative numbers and we need to find the maximum sum of a given sub array.

How we're going to do it:

We're going to use Kadane's Algorithm to find the maximum sum of a sub array. Meaning that we're going to carry the sum of the current max sub array, and if we find a number that is greater than the sum of the max sub array, restart the sub arrays value to be that of the current number, or we will keep adding the numbers to the sub array.

All the while we're always keep track on if the new max sum array is greater than the current max sum. We repeat this process for every number in the array.

We start with a max sum of 0. As it's possible that we have a array of 1 length, so thus it's max sum is itself.
We also start with a max sub array of -Infinity. This is because we want to find the maximum sub array, and we don't want to start with a sub array of 0 as their is negatives within the array.

Big O Notation:

Time Complexity: O(n) | Where n is the length of the array.
Space Complexity: O(1) | As we never allocate any additional memory.

Can this be improved?
Well, by the big O notation, NO! But we can use a Divide and Conquer technique to improve the speed but that'll use linear memory.

Python Solution

class Solution:
def maxSubArray(self, nums: List[int]) -> int:

    subArraySum = float('-inf')
    maxSubSum   = nums[0]

    for num in nums:
        subArraySum = max(num, subArraySum + num)
        maxSubSum   = max(maxSubSum, subArraySum)

    return maxSubSum;

C++ Solution

`
class Solution {
public:
int maxSubArray(vector& nums) {
int subArraySum = -10000;
int maxSubSum = nums[0];

    for(const auto& num : nums) {   
       subArraySum = max(num + subArraySum, num);
       maxSubSum = max(maxSubSum, subArraySum);
    }

    return maxSubSum;
}

};
`

Javascript Solution

`
var maxSubArray = function (nums) {

let sub_array_sum = -Infinity; 
let max_sub_sum = nums[0]; 

for (const num of nums) {
    sub_array_sum = Math.max(num, sub_array_sum + num);
    max_sub_sum = Math.max(max_sub_sum, sub_array_sum);
}

return max_sub_sum;

};
`

787. Cheapest Flights Within K Stops 🚀

Samuel Hinchliffe 🚀 — Wed, 27 Jul 2022 13:38:45 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '787. Cheapest Flights Within K Stops' question. An Advanced Graph question.

Question:

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei]indicates that there is a flight from city fromto city to with cost price.

You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Explanation:
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.

Explaining The Question

This Question is rated Medium. Which is I would say is in-accurate, even if you know Bellman-Ford or Dijkstra you'll still have an issue solving this question, especially if you're using Dijkstra because Leetcode Runtime constraints are very strict. Due to how strict this question is, I would say this is a hard question if you're using Dijkstra and medium if using Bellman-Ford. For this question, we're going to use Dijkstra to solve it.

Dijkstra is a greedy algorithm that finds the shortest path from a source to a destination. It works a lot like Breadth First Search. We're going to explore the cheapest flights from src to dst within k stops.

How do you think Google Maps knows the shortest distance (Be distance or cost) between your house and New Yorks Airport? Shortest Path algorithms like Dijkstra's Algorithm or Bellman-Ford's Algorithm are used to find the shortest path between two locations.

Recommended Knowledge

What do we know?

We're given an array [flights] where flights[i] = [from, to, price]indicates that there is a flight from city fromto city to with cost price. Which can be represented as a Adjacency List.
We need to go from src to dst within k stops. Where we're looking for the cheapest flight between src and dst within k stops.

How we're going to do it:

We're going to use Dijkstra's Algorithm to find the shortest path between src and dst where we start from the cheapest flights relative to src in ascending order until we reach dst or we reach k stops. Once we reach the dst we can return the the cost of the flight relative to src.

The most important part to note here, is that we need to prevent ourself from going to the same city multiple times. So we use a [Hashmap] to keep track of the number of stops it took to visit that city the first time, so we can see if it's worth revisiting that city on a different path again.

We're going to create a Priority Queue to hold all the nodes that we need to traverse. As in Dijkstra's Algorithm, we're going to use a Priority Queue to hold the nodes that we need to traverse first. (Cheapest flight first)
We're also going to keep a global hashmap to see if we've visited that city before and if we have how many stops it took to get to that city, it lets us know in the future if we should revisit that city. Meaning, that it's cheaper than our current node and we're good to go back here.
As we know we're starting at src, we're going to add it to the Priority Queue with a value of 0, because it cost us nothing as we started here and 0 stops too.
We will then begin performing Dijkstra's Algorithm, where we remove the 'cheapest' item from the Min-Heap, meaning we brute force all the cheapest flights first so long as it's within k stops. We will also register the number of stops it took to get to that city in that Set.
We're then going to continually explore the cheapest flights and add them to the Priority Queue until we reach dst or we reach k stops.

Big O Notation:

Time Complexity: O(((V + E) * K)) | Right so this is a little confusing. Dijkstra's Algorithm is a O(ElogV) algorithm. Where E is the number of edges in the graph and V is the number of vertices in the graph. Which is represented by O(V^2), as in the worst case, every node and it's neighbors will be added and removed from the Min-Heap multiple times. But as we're limited by K, we're going to limit ourself to K stops, so we're going to limit ourself to K * V * E operations. So in it's amortized form, it's O((V + E) * K). In worst case, we can represent it as O((V^2)).
Space Complexity: O(V + E) | As in the worst case, we're going to store the entire graph within our Min-Heap or our visited set.

Is my analysis wrong? Potentially, feel free to correct me. 😁

Leetcode Results:

See Submission Link:

The Solution

const findCheapestPrice = function (n, flights, src, dst, K) {

    // Firstly build an Adjacency List
    // City => [[Out-City, Cost], [Out-City, Cost], ...]
    const node_edge_cost = new Map();
    for (const [from, to, price] of flights){
        let edges = [];
        if (node_edge_cost.has(from)){
            edges = node_edge_cost.get(from);
        }
        edges.push([to, price])
        node_edge_cost.set(from, edges)
    }

    // Dijkstra's Algorithm in this case uses a min-heap to store the cheapest paths.
    const min_heap = new MinPriorityQueue();

    // We also have a distance from K memo.
    // As it's entirely possible to revisit a node again, so it's useful to 
    // know it's distance from K. So we can know if it's worth even visiting it. 
    const distance_from_k_memo = new Map();

    // We want to start of with the provided source node.
    // It's distance from DST is set to the maximum value it
    // can possibly be, that being K. As we don't want to 
    // to visit a node that's too far away. So we use K to dictate that distance.
    // So once, we branch out and get to 0, and not reached K, we'll stop.
    min_heap.enqueue([src, K + 1], 0);

    // Keep running Dijkstra's Algorithm until we've reached the destination.
    // Or the min-heap is empty.
    while (min_heap.size()){

        // Get the cheapest path from the min-heap.
        // Get the price of the cheapest path.
        // And get the city and distance from DST
        const node = min_heap.dequeue();
        const price = node.priority;
        const [to, distance_from_k] = node.element;

        // Set it within the memo, just in case
        // we come across this node again in the future.
        // So we can tell if it's worth even visiting it again. 
        distance_from_k_memo.set(to, distance_from_k);

        // We've reached the cheapest path to the destination.
        // Return the price.
        if (to === dst) return price;

        // Hmm, seems like we're 0 distance from the destination / K.
        // but not at the destination, guess it's time to backtrack.
        if (distance_from_k <= 0) continue;

        // Get the outbound edges from the current node.
        const edges = node_edge_cost.get(to) || [];

        // Go through each edge and enqueue it.
        // So long as it's worth visiting (Meaning, that if we've visited it, is it 
        // cheaper than the current cheapest path?) If so we can add it back into the min-heap.
        for (const [outbound, out_cost] of edges){

            if (distance_from_k_memo.get(outbound) >= distance_from_k - 1) continue;

            // Enqueue into the min heap with updated cost and distance from K.
            min_heap.enqueue([outbound, distance_from_k - 1], out_cost + price)                
        }

    }

    // This is embarrassing, but we've reached the end of the graph 
    // and not found DST within K hops. So we return -1.
    return -1;
};

778. Swim in Rising Water 🚀

Samuel Hinchliffe 🚀 — Wed, 20 Jul 2022 14:50:16 +0000

Solution Developed In:

The Question

For this article, we will be covering Leetcode's '778. Swim in Rising Water' question. An Advanced Graph question.

Question:

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
The rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distances in zero time. Of course, you must stay within the boundaries of the grid during your swim.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).

Input: grid = [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Explaining The Question

This Question is rated Hard. Which is I would say is in-accurate if you're familiar with Dijkstra's Algorithm or Bellman-Ford's Algorithm or any other path finding algorithm, this question should be a Medium. If you've never encounters these algorithm, this will be impossible for the most part.

Most people will study this algorithm in Higher Education. But if you're like me, not having attending higher education mean't I hadn't the slightest clue about Path Finding Algorithms in a Graph. For me I found this question impossible to solve until I read up that it was solved by Dijkstra's Algorithm.

We're given a graph and we're asked to to traverse the entire graph and hit all nodes using the shortest path. Which sounds a lot like Kruskal's Algorithm, except we're not creating a Minimum Spanning Tree but a Shortest Path between k and all the other nodes.

How do you think Google Maps knows the shortest distance between your house and your friend's house? Shortest Path algorithms like Dijkstra's Algorithm or Bellman-Ford's Algorithm are used to find the shortest path between two locations.

Which is exactly what we're going to do. Finding the shortest path between [0][0] and the bottom right of the board in the least amount of time. Where time is represented by the depth of water, which is the value of the item on the board. Meaning, at the depth of 10, we can travel all nodes that are <= 10.

Recommended Knowledge

What do we know?

We're given a M x N matrix.
We need to start at [0][0] and end at [M][N].
We need to find the shortest path between [0][0] and [M][N] as defined by the depth of water.
The depth of water is defined by the [x][y] value of the matrix.
We can only traverse to adjacent nodes if the depth of water is <= the depth of the node.
[M][N] is unique and always unique, never duplicating.

How we're going to do it:

We're going to use Dijkstra's Algorithm to find the shortest path between [0][0] and [M][N]. The shortest path is defined as the least amount of time it takes to travel from [0][0] to [M][N]. Where time is represented by the depth of water, which is the value of the item on the board.

So we're going to re-frame the question, we're instead going to traverse all the nodes in the matrix that requires the least amount of time until we reach [M][N]. So long as they're in connection of where we currently can go, we're going to keep traversing until we reach [M][N].

We're going to create a Priority Queue to hold all the nodes that we need to traverse. As in Dijkstra's Algorithm, we're going to use a Priority Queue to hold the nodes that we need to traverse first. (Cheapest node first)
We're also going to keep note of a global time_passed variable. What this value will be, is the highest value of depth of water we visited.
As we know we're starting with [0][0], we're going to add it to the Priority Queue with a value of whatever is at that location (Normally 0, but don't make that assumption).
We will then begin performing Dijkstra's Algorithm, where we remove the 'cheapest' item from the Min-Heap and set the time_passed to the value of the item. We're also going to add the coordinates of the item to a visited Set().
We will also attempt to add the node above, left, right and below to the Min-Heap if they are within the bounds of the matrix and un-visited. Where we set the priority as the nodes value. Being the value of the item on the board. Thus, we've achieved the effect by only ever travelling the least amount of time.
We repeat this until we reach [M][N]. At this point, we know what was the highest value of depth of water we visited and so that is our answer.
## Big O Notation:
Time Complexity: O(E * (log V)) | Right so this is a little confusing. Dijkstra's Algorithm is a O(ElogV) algorithm. Where E is the number of edges in the graph and V is the number of vertices in the graph. Which is represented by O(V^2), as in the worst case, every node and it's neighbors will be added and removed from the Min-Heap multiple times. I believe, the real time complexity of this algorithm is O( (M x N) * (Log V)). Where M is the number of rows and N is the number of columns and the Log V is the number of nodes that will be inserted and removed from the heap in logarithmic time. Thus we can reduce this to O(n (log n)).
Space Complexity: O(M x N) | As in the worst case, we're going to store the entire matrix within our Min-Heap or our visited set.

Is my analysis wrong? Potentially, feel free to correct me. 😁

Leetcode Results:

See Submission Link:

The Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
 var swimInWater = function (grid) {

    // We're going to use Dijkstra's algorithm to complete
    // to get from 0,0 to the end of the grid (Bottom Right).
    // We need to get from top left to bottom right 
    // in the shortest path. (Shortest in terms of the [i][x] value)

    // What this mean's is we will travel to the cheapest possible
    // operation relative the time passed. So at time 0, we can 
    // only travel to other 0 nodes that are in connection. Once it's 1, 
    // we can travel to other 1 nodes that are in connection. And so on and so on.

    // So instead of us manually passing time, we can use the value of the grid
    // to determine the time and the place within the queue. 

    // So, we add to a min-heap the [x,y] coordinates of the item in the grid
    // by the [x][y] value. So a grid item that is within reach and has a value
    // of 0, will be added to the top of the min-heap.


    let   time_passed = 0;                       // Max Priority of [Node] Visited
    const visit_set   = new Set();               // Don't want to visit the same node twice
    const min_heap    = new MinPriorityQueue();  // [i][x] = Priority / Time Passed

    // Min Maxes of grid and directions we can travel to.
    // Don't want to go out of bounds do we. 
    const max_rows   = grid.length - 1;
    const max_cols   = grid[0].length - 1;
    const directions = [
        [1, 0],
        [-1, 0],
        [0, 1],
        [0, -1],
    ];

    // So we firstly start off with the item in the top left corner.
    // Which could be any value. So we enqueue it as the first place to visit.
    min_heap.enqueue([0, 0], grid[0][0]); // Go to 0,0 at the cost of 0

    // While the heap is not empty and we have not reached the end of the grid.
    // Keep adding to the min-heap. 
    while (min_heap.size()) {

        // Pop node of our min heap.
        const node   = min_heap.dequeue();
        const cost   = node.priority;       // Time required to reach this node.
        const [x, y] = node.element;        // Coordinates of this node.

        // So we have not been here yet, mark it
        // We know this because, we never visit the same node twice. 
        visit_set.add(grid[x][y]);

        // So we're not at the target,
        // increment our result if we have increased.
        // As this mean's our shortest path time has increased and
        // thus so is the time passed. 
        time_passed = Math.max(cost, time_passed);

        // Are we at the target (Bottom Right of Grid)?
        // Meaning, we have found the shortest path?
        if (x === max_rows && y === max_cols) return time_passed;

        // Add the directions to the queue
        // if we have not already been there.
        //   ^
        // < x >
        //   v
        for (const direction of directions) {
            let [new_x, new_y]  = direction;
            new_x               += x; // Update x
            new_y               += y; // Update y

            // Is it out of bounds? Or we have visited it before?
            // If so, skip over this direction.
            if (new_x > max_rows || new_y > max_cols || new_x < 0 || new_y < 0 || visit_set.has(grid[new_x][new_y])) continue;

            // Enqueue the new node. Where the priority is the cost of the path.
            // Meaning, that once the time has become {x} we can visit it next. 
            min_heap.enqueue([new_x, new_y], grid[new_x][new_y]);
        }
    }    
};

743. Network Delay Time 🚀

Samuel Hinchliffe 🚀 — Tue, 19 Jul 2022 16:20:23 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '743. Network Delay Time' question. An Advanced Graph question.

Question:

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Explaining The Question

This Question is rated Medium. Which is I would say is accurate if you're familiar with Dijkstra's Algorithm or Bellman-Ford's Algorithm or any other path finding algorithm. Most people will study this algorithm in Higher Education. But if you're like me, not having attending higher education mean't I hadn't the slightest clue about Path Finding Algorithms in a Graph. For me I found this question impossible to solve until I read up that it was solved by Dijkstra's Algorithm.

Which is exactly what we're going to do. Finding the shortest path between k and all the other nodes.

Recommended Knowledge

What do we know?

We're given an list of Nodes with a connection and it's cost.
It's possible for a node to not have any inbound connections, and so in this case, we must return -1 as it would be impossible to reach all nodes from {k}

How we're going to do it:

We're going to use Dijkstra's Algorithm to find the shortest path between k and all the other nodes.

Firstly, we will generate ourselves a Adjacent List (Node -> [Edge, Cost]). We do this so we know all the connection ands costs in the graph. From here, we generate a empty Minumum Priority Queue and we add the first node to the queue at the cost of 0, as we start here.

We will then, use a while loop to keep looping until the queue is empty, where we will pop off the min-heap which will always give us the next shortest possible path. With this node, we will then keep adding that new nodes edges to the min-heap and update the cost of the node.

The reason we update the cost of the node is because we're moving out relative to {k}, out input node. Meaning the shortest path cascades outwards from {k}. We keep adding the shortest path to the node and it's edges to the min-heap until we've visited all nodes within the graph. We know we've visited all nodes because we use a Set to keep track of which nodes we've visited.

Each time we move a node, we update the global time variable. Where if the time has increased relative to {k} we increase it by the cost of the edge.

Big O Notation:

Time Complexity: O(V^2) | As it is entirely possible for each vertex to be connected to every other vertex. Thus, we could potentially visit every vertex multiple times. Although our set makes sure they don't process it.
Space Complexity: O(V^2) | As we're going to store the operations within a heap.

The Time and Space complexities of Dijkstra's Algorithm are very very confusing so feel free to correct my anlysis of Dijkstra's Algorithm using a Min-heap for this specific quesiton. When figuring out the complexity I imagined a graph where every node is connected to every node except itself.

Leetcode Results:

See Submission Link:

The Solution

/**
 * @param {number[][]} times
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var networkDelayTime = function (times, n, k) {


    // Our return value, how long did it take
    // to reach all nodes within the network from {k}
    let time_taken = 0;

    // A set so we don't visit the same node twice.
    const visited_set = new Set();

    // A min heap, as we want to visit the the node
    // with the cheapest path so far. Relative to {k}.
    // See: https://github.com/datastructures-js/priority-queue
    // Heaps are built into Leetcodes Runtime for JavaScript. 😁😁
    const min_heap = new MinPriorityQueue();

    // An adjacency list, where we store 
    // Node -> [[Edge, Cost],[Edge, Cost]]
    const node_edge_cost = new Map();

    // Build the adjacency list.
    for (const [node, edge, cost] of times) {
        let edges = [];
        if (node_edge_cost.has(node)) {
            edges = node_edge_cost.get(node);
        }
        edges.push([edge, cost]);
        node_edge_cost.set(node, edges);
    }

    // We have been asked to start at {k}
    // So we enqueue {k} at the cost of 0, as of course
    // it costs nothing as we start here.
    min_heap.enqueue([k, 0], 0);

    // Perform Dijkstra's algorithm.
    // Get the cheapest operation relative to {k}
    // and add it's edges to the heap, where we're always
    // updating the cost relative to {k}. Therefore, 
    // we're visiting all the cheapest operations relative to {k}.
    while (min_heap.size()) {

        // Get the cheapest operation relative to {k}
        // Node and cost
        const [node, cost] = min_heap.dequeue().element;

        // Have we already been here? No loops today kiddo
        if (visited_set.has(node)) continue;

        // Set it. We don't want to come back here. 
        visited_set.add(node);

        // Did our distance increase?
        // If so, update it. If not, keep the same
        time_taken = Math.max(cost, time_taken);

        // Get the edges for this node (If any)
        const node_edges = node_edge_cost.get(node) || [];

        // Get all the edges for this node and add them to the heap
        // If they haven't been visited yet. Note:
        // We're adding the cost of the given nde to the cost of the edge.
        // Because we're moving out relative to {k}. Thus,
        // even if all nodes have a cost of 2.
        // It's going to cascade outwards.
        // 2 -> 4 -> 6 -> 8 etc.
        for (const [edge_node, edge_cost] of node_edges) {
            if (!visited_set.has(edge_node)) {

                // Add it to the queue, set the priority to the cost of the edge
                // So we only ever visit the cheapest edge.
                min_heap.enqueue([edge_node, edge_cost + cost], edge_cost + cost);
            }
        }
    }

    // Did we visit every node?
    // If not, we failed to spread the message across the network.
    // If so, return the time taken. 
    return visited_set.size === n ? time_taken : -1;
};

1584. Min Cost to Connect All Points 🚀

Samuel Hinchliffe 🚀 — Fri, 15 Jul 2022 15:56:13 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '1584. Min Cost to Connect All Points' question. This question is very similar to the 684. Redundant Connection question. As we're going to use Union Find to solve this problem. If you have not solved 684. Redundant Connection question using Union Find yet, then you should do so by following this guide here.

Question:

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].
The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: We can connect the points as shown above to get the minimum cost of 20.
Notice that there is a unique path between every pair of points.

Explaining The Question

This Question is rated Medium. Which is false. I consider this question to be a Hard question. As the Datastructre used to solve this question is rarely known and the specific algorithms to use (Kruskals Algorithm or Prims Algorithm) is also rarely seen. I think it would be impossible to solve this question if you hadn't encourted these algorithms / data structures / Minimum spanning tree algorithms. Nonetheless, this is a fantastic problem to solve.

What's expected of you is to use Union Find to solve this problem. Specifically, Union Find by Rank is expected. And given this structure, we will use Kruskals Algorithm to solve this problem.

We have been given a list of Nodes and Edges ([Node -> Edge]). Which forms a Graph, we need to connect this entire graph together at the minimal cost. This forms a Minimum Spanning Tree. The cost of a connection is determined by the Manhattan Distance between two nodes. So we need to connect all nodes to their closest neighbors.

Recommended Knowledge

What do we know?

All pairs are distinct.
We need to connect all nodes to the cheapest connection as defined by the Manhattan Distance.

How we're going to do it:

We're going to use Union Find to solve this problem. Specifically, Union Find by Rank. We're going to use Kruskals Algorithm to create a Minimum Spanning Tree by connecting each node to their cheapest connection. We will union all nodes starting with the operation that is the cheapest.

Meaning, that prior to the union find we will create a list of Operations. An Operation means's that if we was to connect Node_1 to Node_2, how much would it cost? What this forms is an Array of Arrays that looks like this:
[ [1, 2, 1] [2, 1, 1] [3, 4, 2] [4, 3, 2] [5, 6, 3] [6, 5, 3] ] ]
Where [Node_1, Node_2, Cost] is the operation. We sort this list of operations by the cost. So we start with the cheapest connection and then attempt to connect Node_1 to Node_2 using UnionFind. Each time we union two nodes, we will add the cost of the connection to the total cost. Once we have unionised all nodes, we will have a Minimum Spanning Tree and thus our total cost. This is known as Kruskals Algorithm. We will use a Min Heap to find the order the cost of the connections. So we can always start with the cheapest connection.

While we're running through the list of operations, we will also tally the number of operations processed so we can exit the program early, as we could've already connected all the nodes and we're running redundant operations. We will also note the cost if the Union was successful.

Big O Notation:

Time Complexity: O(N x E) | Where n is the number of nodes in the Graph. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. Although we could easily argue it's O(n x e ^ 2) as we're going to visit every node for every node. As every node is a potential connection.
Space Complexity: O(N x E) | As we're going to store the list of operations in a Min Heap.

We did although implemented a Path Compression and Union by Rank technique to achieve a Amortized O(1) time complexity on our Union and Find functions. But as we will still need to iterate through the Nodes, we will still have a O(n x e) time complexity.

Could this be improved?
Yes, Prim's Algorithm is a better algorithm to solve this question. But I think Kruskals Algorithm is a better algorithm to solve this question as you're more likely to come across union find questions than Prim's Algorithm questions.

Leetcode Results:

See Submission Link:
Do note, this question wasn't developed very well for Javascript, as half the time this question won't even count as valid due to taking so long despite being a very valid
answer using Kruskals Algorithm.

The Solution

class UnionFind {
    /**
     * @summary We're going to generate a UnionFind data structure.
     * Union Find is a special data-structure that can be used to form
     * a disjoint set (A tree). For this solution, we're going to use
     * the Rank variant of Union Find. All this mean's is that we keep
     * track the number of nodes a given tree has. It allows us to merge
     * trees that will require the minimal amount of work (Increases
     * the Amortized Complexity).
     *
     * @param  {Array} edges [[node, edge_to_connect_to], [node, edge_to_connect_to]]
     */
    constructor(edges) {
        // Create a array of Ranks (Index -> Tree Size)
        // Looks Like: [1,1,1,1]
        // (Each node is a tree of size 1 by default)
        this.ranks = new Array(edges.length).fill(1);

        // Create a array of Parents (Index -> Index of Parent)
        // If we keep following the parent, we'll eventually find
        // the root of the tree.
        // Looks Like: [0,1,2,3]
        // (Each node's parent is itself by default, as it's the root of it's tree)
        this.parents = Array.from(Array(edges.length).keys());
    }

    /**
     * @summary Find the root of a given node, we do this by asking the parents
     * list 'Who's the parent of this node's index?', we repeat this until the parent
     * of the node is itself. Meaning, we have reached the root of the tree.
     * We have also utilized a concept called 'Path Compression'. This mean's
     * instead of going up the tree one node at a time, we go up the tree 2 nodes
     * at a time. Tree height should be very small due to the 'rank' concept.
     *
     * Time Complexity: Amortized O(1) (Best, tree height is small)
       *              : O(log n) (Average)
       *              : O(n) (Worst, linked list tree)
     *
     * Space Complexity: O(1) (Finding allocated no space)
     *
     * Technically, we rate an algorithm by it's worst case. Thus this is
     * O(n) in time. But it's such a rare case that we don't care, so it's better
     * to use the amortized case of O(1)
     *
     * @param  {Number} index (Index of node in [Parents, Ranks, Edges])
     * @return {Number}       (Index of parent, the root node of the tree)
     */
    find(index) {
        // Get parent of node
        let parent = this.parents[index];

        // Keep getting parents until we reach the root of the tree
        while (parent != this.parents[parent]) {
            // Path Compression
            parent = this.parents[this.parents[parent]];
        }
        return parent;
    }

    /**
     * @summary Merge two trees by connecting the root of the  tree by rank.
     * What this mean's, is we're going to find the parents of both of the supplied
     * nodes, and then figure out which tree is larger. We then connect the root of
     * the smaller tree to the root of the larger tree.
     * Why? Because, during the Find() operation, we want to reduce the number of
     * steps required to get to the root of a given tree. By merging smaller into larger
     * we won't need as many steps to find the root of a given parent.
     *
     * This is called Union by Rank. Rank meaning, size of a given tree. When you combine
     * Path Compression and Union by Rank, you get a amortized O(1) time complexity.
     *
     * Time and Space Complexity is the same as Find() as we utilise that function.
     *
     * @param  {Number} n1 (Index of node 1)
     * @param  {Number} n2 (Index of node 2)
     * @return {Boolean}   (False if nodes are already in the same tree)
     */
    union(n1, n2) {
        // Find the parents of each node.
        const n1_parent = this.find(n1);
        const n2_parent = this.find(n2);

        // Are the nodes already in the same tree?
        // REDUNDANT CONNECTION!!!
        if (n1_parent === n2_parent) return false;

        // Union by rank, merge smallest into largest.
        if (this.ranks[n1_parent] > this.ranks[n2_parent]) {
            // Update parent and ranks
            this.parents[n2_parent]  = n1_parent;
            this.ranks  [n2_parent] += this.ranks[n1_parent];
        } else {
            // Merge n1 into n2
            this.parents[n1_parent]  = n2_parent;
            this.ranks  [n1_parent] += this.ranks[n2_parent];
        }

        // Successfully merged. Ranks and parents updated
        return true;
    }
}


/**
 * @param {number[][]} points
 * @return {number}
 */
var minCostConnectPoints = function (points) {
    // We're going to perform Kruskal's algorithm to find the minimum cost of connecting all the points.
    // Which results in a minimum spanning tree. (MST). Kruskal's algorithm is a greedy algorithm,
    // that connects a node with another node based on the smallest distance. So we always
    // connect 2 nodes together knowing that it's the smallest distance.

    // We're going to create a list of possible operations, Node -> Closest Node.
    // We're going to union these 2 nodes by rank and note the cost. We run through all
    // the cheapest operations and connect the nodes together. We then return the cost once
    // we have connected all the nodes.

    // Base case
    if (points.length === 1) return 0;

    // STAGE 1
    // Create a list of operations
    // Node -> [All Nodes except itself] | Cost
    // As all nodes are a candidate for connecting. Once created, we sort our operations by cost.
    // as in Kruskal's algorithm, we always start by connecting the cheapest nodes together.
    // We will use a MinHeap to achieve this. [Cost (Priority)] -> [Node, Vertex]
    const node_edge_cost = new MinPriorityQueue();

    // Prevent Duplicate Operations (Not Needed)
    const operation_set = new Set();

    /**
     * @summary: Manhattan distance between 2 nodes on this graph.
     * Time    : O(1)
     * Space   : O(1)
     *
     * @param  {number} point1
     * @param  {number} point2
     * @return {number} Manhattan distance
     */
    const distance = (point1, point2) => {
        return Math.abs(point1[0] - point2[0]) + Math.abs(point1[1] - point2[1]);
    };

    // Populate the heap  with all possible
    // operations. Except for itself. We do this because any node
    // could be the closest to said node.
    for (let i = 0; i < points.length; i++) {
        for (let j = 0; j < points.length; j++) {
            if (i != j && !operation_set.has(`${j}-${i}`)) {
                // Add the operation to the adjacency list
                // [Node, Possible Connection] => Operation Cost
                node_edge_cost.enqueue([i,j],  distance(points[i], points[j]))
            }
        }
    }

    // Unlock our Union Find
    const UF = new UnionFind(points);

    // Unionise all nodes
    // with their cheapest node and note it's cost
    // Merge into the smallest tree
    let union_cost            = 0;
    let number_of_connections = 0;

    // Starting at the smallest operation, unionise all nodes to
    // their closest connection. If union is successful, add the cost. (Distance) (Priority in heap)
    // We also keep track of the number of unions that occur, as many connections
    // will accidentally be duplicates. It mean's we can exit the loop early. Preventing
    // lots of unnecessary work.

    while (node_edge_cost.size()){

        // Get the cheapest operation from the heap
        const node = node_edge_cost.dequeue();
        const vertex = node.element[0];
        const edge = node.element[1];

        // Early exit if we've already connected all the nodes.
        if (number_of_connections === points.length - 1) return union_cost;

        // Unionise the nodes, add the cost. 
        if (UF.union(vertex, edge)) {
            number_of_connections += 1;
            union_cost            += node.priority;
        }
    }

    // Optimisations Made (Not Required, but increases the Amortized Complexity)
    // Union Find by Rank
    // Find by Path Compression
    // Early Exit by connection counting.
    // Duplicate Operations Check. (Prevents extra node finding)
    // We also used a heap to prevent a O(n^2) time of sorting.

    // Time and Space: O(n^2) due to building the adjacency list.
    return union_cost;
};

684. Redundant Connection 🚀

Samuel Hinchliffe 🚀 — Thu, 14 Jul 2022 15:04:00 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '684. Redundant Connection' question. Knowing how to solve this problem with UnionFind will be vital to solving 1584. Min Cost to Connect All Points' with Kruskal's Algorithm.

Question:

In this problem, a tree is an undirected graph that is connected and has no cycles.
You are given a graph that started as a tree with n nodes labeled from 1 to n, with one additional edge added. The added edge has two different vertices chosen from 1 to n, and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the graph.
Return an edge that can be removed so that the resulting graph is a tree of n nodes. If there are multiple answers, return the answer that occurs last in the input.

Input: edges = [[1,2],[1,3],[2,3]]
Output: [2,3]

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. This question is kinda of a trick question, if you're like me you'll probably think 'Greedy Depth First Search on all nodes until we find out last loop'. Which works, but is not the best way to solve this problem.

What's expected of you is to use Union Find to solve this problem. Specifically, Union Find by Rank is expected.

This question is only Medium if you know how to use Union Find with Union Find by Rank.

We have been given a list of Nodes and Edges ([Node -> Edge]). Which forms a Graph, we need to find the Redundant Edge. Which is the last connection between two nodes that forms a Cycle.

Recommended Knowledge

What do we know?

We have a 2D Array of '1's and '0's.
It's a M x N Matrix
Neighbors are left, right, top, and bottom.
We need to find the max area of an island. Meaning, the number of cells in the island.

How we're going to do it:

We're going to find this Redundant Edge by using a Union Find data structure. We'll be creating a Tree from the provided Node & Edge array. The reasons this will work is because within a tree, there are no cycles. So when we're creating the tree, we'll be checking if the 2 given nodes have the same parent. What that mean's their was an attempt to create a connection in what was once a perfect tree.

Once we detect that attempted connection, we can identify the Node Edge that would've created a redundant connection.

We're going to firstly define our Ranks and Parents. A rank is the number of nodes that tree has. A parent is the node that is the parent of the current node. With this information, we know the size and structure of the tree.
We're going to define our Find() function. When we're Unioning two nodes, we need to find the parents of the given node. We implement this function by asking the parents array, 'Who this nodes parent?' and we keep asking this question until the parent of a node is itself (Meaning, it's the root). We also implement a Path Compression technique to speed up this process to achieve an Amortized O(1) time complexity.
We're going to define our Union() function. The purpose of this function is to merge 2 trees together. Firstly, we need to Find() the root nodes of the 2 supplied nodes. We check if they're of the same parent, meaning it's a redundant connection and we need to stop execution. If they're not, we need to merge the 2 trees. We do this by setting the parent of the 2 nodes to the same parent. As well as updating their ranks
Now we have all of our functions for a UnionFind structure, we will now attempt to Union all the supplied nodes. If at any point our Union connection returns false (Found a redundant connection), we can stop execution and return that edge.

Big O Notation:

Time Complexity: O(V * E) / O(n) | Where n is the number of nodes in the Graph. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. As in the worst case, the last node will attempt a redundant connection.
Space Complexity: O(h) | Where h is the largest number of nodes within our graph. As we're going to create a tree from the graph. Which will be the same as the number of nodes in the graph.

Leetcode Results:

See Submission Link:

Runtime: 78 ms, faster than 85.83% of JavaScript online submissions for Max Area of Island
Memory Usage: 45.1 MB, less than 67.24% of JavaScript online submissions for Max Area of Island.

The Solution

class UnionFind {

    /**
     * @summary We're going to generate a UnionFind data structure.
     * Union Find is a special data-structure that can be used to form
     * a disjoint set (A tree). For this solution, we're going to use
     * the Rank variant of Union Find. All this mean's is that we keep
     * track the number of nodes a given tree has. It allows us to merge
     * trees that will require the minimal amount of work (Increases
     * the Amortized Complexity).
     *
     * @param  {Array} edges [[node, edge_to_connect_to], [node, edge_to_connect_to]]
     */
    constructor(edges) {

        // Create a array of Ranks (Index -> Tree Size)
        // Looks Like: [1,1,1,1]
        // (Each node is a tree of size 1 by default)
        this.ranks = new Array(edges.length).fill(1);

        // Create a array of Parents (Index -> Index of Parent)
        // If we keep following the parent, we'll eventually find
        // the root of the tree.
        // Looks Like: [0,1,2,3]
        // (Each node's parent is itself by default, as it's the root of it's tree)
        this.parents = Array.from(Array(edges.length).keys());
    }

    /**
     * @summary Find the root of a given node, we do this by asking the parents
     * list 'Who's the parent of this node's index?', we repeat this until the parent
     * of the node is itself. Meaning, we have reached the root of the tree.
     * We have also utilized a concept called 'Path Compression'. This mean's
     * instead of going up the tree one node at a time, we go up the tree 2 nodes
     * at a time. Tree height should be very small due to the 'rank' concept.
     *
     * Time Complexity: Amortized O(1) (Best, tree height is small)
       *              : O(log n) (Average)
       *              : O(n) (Worst, linked list tree)
     *
     * Space Complexity: O(1) (Finding allocated no space)
     *
     * Technically, we rate an algorithm by it's worst case. Thus this is
     * O(n) in time. But it's such a rare case that we don't care, so it's better
     * to use the amortized case of O(1)
     *
     * @param  {Number} index (Index of node in [Parents, Ranks, Edges])
     * @return {Number}       (Index of parent, the root node of the tree)
     */
    find(index) {
        // Get parent of node
        let parent = this.parents[index];

        // Keep getting parents until we reach the root of the tree
        while (parent != this.parents[parent]) {
            // Path Compression
            parent = this.parents[this.parents[parent]];
        }
        return parent;
    }

    /**
     * @summary Merge two trees by connecting the root of the  tree by rank.
     * What this mean's, is we're going to find the parents of both of the supplied
     * nodes, and then figure out which tree is larger. We then connect the root of
     * the smaller tree to the root of the larger tree.
     * Why? Because, during the Find() operation, we want to reduce the number of
     * steps required to get to the root of a given tree. By merging smaller into larger
     * we won't need as many steps to find the root of a given parent.
     *
     * This is called Union by Rank. Rank meaning, size of a given tree. When you combine
     * Path Compression and Union by Rank, you get a amortized O(1) time complexity.
     *
     * Time and Space Complexity is the same as Find() as we utilise that function.
     *
     * @param  {Number} n1 (Index of node 1)
     * @param  {Number} n2 (Index of node 2)
     * @return {Boolean}   (False if nodes are already in the same tree)
     */
    union(n1, n2) {

        // Find the parents of each node.
        const n1_parent = this.find(n1);
        const n2_parent = this.find(n2);

        // Are the nodes already in the same tree?
        // REDUNDANT CONNECTION!!!
        if (n1_parent === n2_parent) return false;

        // Union by rank, merge smallest into largest.
        if (this.ranks[n1_parent] > this.ranks[n2_parent]) {
            // Update parent and ranks
            this.parents[n2_parent]  = n1_parent;
            this.ranks  [n2_parent] += this.ranks[n1_parent];
        } else {
            // Merge n1 into n2
            this.parents[n1_parent]  = n2_parent;
            this.ranks  [n1_parent] += this.ranks[n2_parent];
        }

        // Successfully merged. Ranks and parents updated
        return true;
    }
}

/**
 * @param {number[][]} edges
 * @return {number[]}
 */
var findRedundantConnection = function (edges) {
    // The basic premise of this solution is
    // to use UnionFind to find the redundant edge.
    // UnionFind will attempt to create a tree by merging nodes
    // together. If at any point, two nodes are already connected,
    // meaning, they're in the same tree, we have found the redundant connection.

    // We're going to initialize a Union Find data structure
    // so we can attempt to build our tree.
    const Union_Find = new UnionFind(edges);

    // Let's build our tree.
    // Union each node and their edges together.
    // If at any point, a node and edge are already in the same Tree.
    // END loop, we found the redundant connection.
    for (const [node, edge] of edges) {
        if (!Union_Find.union(node, edge)) return [node, edge];
    }
};

332. Reconstruct Itinerary 🚀

Samuel Hinchliffe 🚀 — Fri, 08 Jul 2022 14:29:39 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '332. Reconstruct Itinerary' question. This question is the first Boss Battle of the Graph Questions. You will find that to solve this question, you will need to know lot's of Graph Patterns. This is no simple question.

Question:

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
-For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Explaining The Question

This Question is rated Hard. Which is very accurate. This question combines a handful of Graph Patterns, making it very difficult to solve. Despite this, this is an excellent question to learn all of those concepts.

We're given an array of tickets, where each ticket contains a departure and arrival airport. We need to reconstruct the itinerary in order and return it. We always know we start at JFK.

We need to perform Depth First Search on a Adjacency List where each city has it's airport arrivals lexicographically sorted. Where we need to return the Topological Sort from JFK to the last destination. As this is a Directed Graph, we need to also implement backtracking just in case we accidentally go to the last destination too early.

Lot's of concepts to know. It's a very interesting question.

Recommended Knowledge

What do we know?

We're given a list of tickets, where each ticket contains a departure and arrival airport. We need to reconstruct the itinerary in order and return it.
We know we need to visit in lexicographical order first.

How we're going to do it:

Well, we know we can build an Adjacency List where each city has it's airport arrivals are lexicographically sorted. Lexicographical order is the order in which the letters are sorted in a word (A fancy way of saying alphabetical order 😁). Given this information, we know each departure at each airport, but we just don't know the full order, it may be lexicographically sorted but that may not be the order the ticket owner traveled by. The ticket owner didn't travel in lexicographic order.

So given this information, we can perform Depth First Search on this graph. To explore each airport from it's source. While we're travelling in our Depth First Search, we're removing that airport from the current node, because we do want to revisit this airport, just not again from this airport. So we remove it from the adjacency list edges.

During this Depth First Search, we're adding the cities we visit in Topological Order to a stack. This stack will be our itinerary. We're always checking if we're going in the correct direction, we know this by checking the length of the tickets array and if we're at the last ticket, and we have children still to visit, then we're going the wrong way. So in this situation, we're going to use Backtracking to go back to the last city we visited and try another route until we fully construct our itinerary.

Firstly, we're going to Topological Sort our tickets array. This will give us a lexicographically sorted array of cities.
With this array, we're going to create an Adjacency List where each city has it's airport arrivals are lexicographically sorted.
We will then perform Depth First Search on this graph, for each city, we remove it's edges from the adjacency list, as to not revisit that city again from this airport.
We're adding the airports in Topological Order to a stack. This stack is going to be our return value for this entire problem.
We need to check if we're going in the correct direction, we do this by checking the length of the tickets array, if we have no children, then we're going the wrong way. So we're going to use Backtracking to go back to the last city we visited and try another route until we fully construct our itinerary. We remove it from our stack, and we're going to try another route.

Big O Notation:

Time Complexity: O( (V * E) ^ 2 ) / O(n ^ 2) | Where V is the number of vertices and E is the number of edges. It's (V * E) because we're going to perform Depth First Search and visit every node. And it's (V * E) ^ 2 because we're going to perform Depth First Search on each node, and potentially visit each node again due to the Backtracking situation. As we don't know the order, in the worst case we might have to visit each node multiple times.
Space Complexity: O(h) | Where h is the size of the call stack. Because we perform Depth First Search on each node, and we're going to add each node to the call stack.

The Big O Notation analysis for this problem is a little confusing as it combines a handful of different concepts all with their own Big O Notations. I could be wrong, let me know.

Could this be improved? Yes, with Eulerian Path.I choose the DFS because it's the intuitive way to go. While Eulerian Path is faster, it isn't something you could just come up with.

Leetcode Results:

See Submission Link:

Runtime: 113 ms, faster than 71.71% of JavaScript online submissions for Max Area of Island
Memory Usage: 50 MB, less than 21.34% of JavaScript online submissions for Max Area of Island.

The Solution

/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {

    // We have been given a directed graph.
    // We know we always start at JFK.
    // We need to return the flight path the user took.
    // We will use a adjacency list to store the graph.
    // Node -> [destination, destination, destination]

    // For each node we visit in topological order, we add to the path.
    // Starting with JFK and the lexicographically closest node.
    // Although the issue is that it isn't going to always be right.
    // We could accidentally take a node that is lexicographically correct
    // but is just the last destination in a series of travels. Meaning
    // the man has traveled the entire world, came back to Jfk and gone to the last
    // dest. Which we cannot miss, so we check this. If a node has no given edges,
    // and it isn't the last destination, we backtrack our results. Act as if we haven't
    // visited him yet and do the rest, repeating this logic.

    // We repeat this until we have visited all nodes, we know this by the size of our
    // output array matching the size of our input array or we just have no more nodes with edges
    // anymore.

    // Flights paths will be our adjacency list.
    const flight_paths = new Map();

    // This is what we will return, we always know we start at JFK.
    const flight_path_order = ["JFK"];

    // Thankfully, javascript's default sort is lexicographical.
    // We do this as we need to visit the lexicographically closest node first.
    // Assuming we don't backtrack on it later.
    tickets = tickets.sort(); // O(n^2);

    // Create the adjacency list.
    for (const [source, dest] of tickets) {
        let edges = [];
        if (flight_paths.has(source)) {
            edges = flight_paths.get(source);
        }
        edges.push(dest);
        flight_paths.set(source, edges);
    }

    // Depth first search.
    const depth_first_search = (city) => {
        // Have we already been to all the nodes?
        // Meaning we have visited all the tickets?
        if (flight_path_order.length === tickets.length + 1) return true;

        // Get the departures of flights from this city.
        // If their isn't any, we need to back track on this node
        // Because we know we have more flights to go and we have already
        // somehow visited our destination. Which is incorrect.
        const cities_to_go_to = flight_paths.get(city) || [];
        if (!cities_to_go_to.length) return false;

        // So we have other cities to go to from here.
        // Let's create a copy of those cities because we're going to
        // be dynamically adding and removing from that array. Something our
        // for loop wouldn't be able able to handle otherwise.
        const cities_copied = Array.from(cities_to_go_to);

        // Visit all connecting cities.
        for (const other_city of cities_copied) {
            // Add to our output, as we're doing this in topological sort
            flight_path_order.push(other_city);

            // Remove the city from the edges of the graph.
            // As we don't want to revisit it. Otherwise we would have a loop.
            // Note: we're passing this array by reference. So we don't need to re-set it.
            // We use shift here because we've done this in lexicographical order starting from
            // the beginning.
            cities_to_go_to.shift();

            // If it returns true, it mean's we've visited all cities
            // and that mean's we have nothing else to do.
            if (depth_first_search(other_city)) {
                return flight_path_order;
            } else {
                // BACKTRACKING!
                // We've visited the wrong city!
                // Undo our work here, as this is not the right city,
                // we need to revisit this city later on and not now.
                // What this does is visit all other cities
                // then backtrack on this city.
                flight_path_order.pop();
                cities_to_go_to.push(other_city);
            }
        }

        return false;
    };

    // Start at JFK airport
    return depth_first_search("JFK");

    // In the end this is O (v + e) ^ 2 time O(e) space
    // We could better solve this using Eulerian path.
};

130. Surrounded Regions 🚀

Samuel Hinchliffe 🚀 — Mon, 04 Jul 2022 15:14:37 +0000

Solution Developed In:

The Question

For this article we will be covering Leetcode's '130. Surrounded Regions' question.

Question:

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally > surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. But this is ONLY Medium if you have a good grasp of Depth First Search or Breadth First Search on Graph Theory. As well as knowing how to apply these ideas to Matrixes. If you don't know how to do those, you're going to have a difficult time solving this problem.

We've been given a matrix, we're told to capture all regions that do not border the edge of the matrix.
At first glance, this question is simple, run Depth First Search and see if anything borders the edge. If it does, then we know that the region is surrounded. If it doesn't, then we know that the region is not surrounded.

Recommended Knowledge

What do we know?

We have a Matrix full of 'X' and 'O'
It's a M x N Matrix
We need to convert all surrounded regions to 'X'

How we're going to do it:

Well we know that all the invalid islands that cannot be surrounded by 'X' are connected to the edges of the matrix. So firstly, we're going to visit all the border of the matrix asking if any of the given nodes are 'O', if they're we already know they're invalid, so we mark the entire island as 'T' meaning temp. As we're going to un-convert them later on.

Once we have marked all the invalid islands, we automatically capture all regions that are not 'T'. All the temp regions are converted back to their original 'O' state.

Run all the edges of the matrix in search for invalid islands.
Perform Depth First Search on the invalid islands and mark the invalid islands as 'T'
Run through the entire matrix and automatically capture all the regions that are not 'T'
Then convert all the 'T' regions back to 'O'

Big O Notation:

Time Complexity: O((V * E) + b) / O(n) | Where n is the number of nodes in the Matrix. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. And where b represents the border of the matrix. As in the worst case, we will visit each node and each one of it's vertexes, which would mean the entire matrix is an island.
Space Complexity: O(h) | Where h is the largest number of nodes within a border island, as we will store all of those nodes within the Call Stack to perform our Depth First Search.

The Solution

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {

    /* -------------------------------------------------------------------------- */
    /*                          130. Surrounded Regions                           */
    /* -------------------------------------------------------------------------- */

    /* ---------------------------- Solution Concept ---------------------------- */

    // We need to capture all regions that are not bordered to the edge of the matrix.
    // We could perform Depth First Search on all the cells in the matrix and ask
    // if any of them border the edge. Instead, we're going to do all the edges
    // of the matrix and convert all island that border the island to temp nodes.
    // We do this because we already know that the bad nodes border the edge 
    // of the matrix.

    // Once we've marked all the bad islands. We run through the entire matrix
    // automatically capturing all the nodes that are not marked as bad. And all
    // the previously marked bad nodes are converted to back to islands.

    /* ---------------------------- Solution as Code ---------------------------- */

    // Matrix Maxes (Makes our life's easier)
    const max_rows = board.length - 1;
    const max_cols = board[0].length - 1;

    // During our search, we can go up, down, left and right.
    // We cannot go diagonally! We can only go up, down, left and right.
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    // Our helper depth first function that converts all bad
    // islands to marked nodes.
    const depth_first_search = (row_index, col_index) => {

        // Is it within bounds of the matrix?
        // And are we allowed to do dfs on this node?
        if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
            return false
        }

        // So node is within bounds, it bordered the edges of the matrix
        // and thus it's a invalid island. As we cannot Surround the Region
        // So let's mark it as a 't'. We do this to let us know not to 
        // convert this node into a 'x'.

        board[row_index][col_index] = "T";

        // Search in all directions for the rest of the island.
        for (const [x, y] of directions){
            depth_first_search(row_index + x, col_index + y);
        }
    }


    // let's check all the edges of the matrix checking 
    // for these bad nodes. If we ever find one, we run 
    // DFS on it to mark it. Starting with:

    // Top and Bottom of matrix
    for (let i = 0; i <= max_cols ; i++){
        const top = board[0][i];
        const bottom = board[max_rows][i];

        if (top === "O"){
            depth_first_search(0, i);
        }

        if (bottom === "O"){
            depth_first_search(max_rows, i);
        }
    }

    // Left and Right of matrix
    for (let i = 0; i <= max_rows ; i++){
        const left = board[i][0];
        const right = board[i][max_cols];

        if (left === "O"){
            depth_first_search(i, 0);
        }

        if (right === "O"){
            depth_first_search(i, max_cols);
        }
    }

    // Now we have gone through the entire border of the matrix
    // we have now marked all bad islands if their was any.
    // Meaning we can automatically capture all regions that 
    // didn't border that edge.

    // We will also unmark all the marked nodes that did border 
    // the edge of the matrix. We do this because we know that it's an invalid island.
    board.forEach((row, row_index) => {
        row.forEach((col, col_index) => {

            // Capture unmarked regions.
            if (col === "O") board[row_index][col_index] = "X"

            // Converted marked regions back to a normal island
            if (col === "T") board[row_index][col_index] = "O"
        })
    })

    // Return Nothing. We modified our input in place.

};