Forem: Urfan Guliyev

Leetcode - Binary Search (with JavaScript)

Urfan Guliyev — Fri, 02 Oct 2020 07:03:53 +0000

Today I am going to show how to solve the Binary Search algorithm problem.

Here is the problem:

Binary search algorithm is one of the most famous searching algorithms. Even though it is not very difficult to understand, it is very important that we understand it thoroughly and know how to properly implement it.

Binary search algorithm helps us to find the position of a target value within a sorted array. It gives us O(log n) time complexity.

Binary search compares the target value to the middle element of the array. If they are not equal, based on that comparison either the first half or the second half of the array is selected while the other one is eliminated. The search then continues on the remaining half. The middle element is again compared to the target value. This process repeats itself until the target value is found.

First, I am going to declare two pointers to solve this problem:

Left pointer, which is going to point to the first number in the array and;
Right pointer, which is going to point to the last number in the array.

Then, I calculate the middle number by taking the sum of the left pointer and the right pointer and dividing that by two. Since we're dealing with indices and we know that an index cannot be a decimal number, we have to round this number down.

Now that we have the middle number, we are going to compare it to our target number.

If they are equal, we will return the index of the middle number.
If the middle number is less than the target number, we will eliminate the second half of the array on the right side of the middle number. We will then move our left pointer and repeat this until the target value is found.
If the middle number is more than the target number, we will eliminate the first half of the array on the left side of the middle number. We will then move our right pointer and repeat this until the target value is found.

var search = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        const middle = Math.floor((left + right) / 2);
        const potentialMatch = nums[middle];
        if(target === potentialMatch) {
            return middle;
        } else if (target < potentialMatch){
            right = middle - 1;
        } else {
            left = middle + 1
        }
    }
    return -1
};

Leetcode - 3SUM (with JavaScript)

Urfan Guliyev — Sat, 26 Sep 2020 19:34:26 +0000

Today I am going to show how to solve the 3 Sum algorithm problem.

Here is the problem:

In my previous blog, I talked about the solution to the 2Sum algorithm. For this problem. we could’ve used a hash table to store every number, similar to the solution in the 2Sum algorithm. Then we could’ve done double “for” loops and checked if the current number’s complement already exists in the table. But that wouldn’t be the most efficient way to solve this problem.

Instead, I am going to solve this problem by using two pointers that will give us O(n^2) time complexity. In this approach, the first thing we need to do is to sort the given array in ascending order.

After sorting the array, we are going to iterate through it and set our two pointers. A left pointer will be set to a number that comes immediately after the current number and a right pointer will be set to the number at the end of the array. Then we are going to find our current sum which is the sum of our current number, a left number, and a right number.

Now we check if our current sum is equal to our target sum, which in this case is 0.

If it is equal, we just add those three numbers to our final array (triplets).

If the current sum is less than 0, we move the left pointer to the right by one to increase the sum. Because we earlier sorted the given array in ascending order, we know that each number is greater than the number to its left.

If the current sum is greater than 0, because we know that each number is smaller than the number to its right, we can move the right pointer to the left by one to decrease the sum.



var threeSum = function(array) {
     array.sort((a,b) => a - b);
    const triplets = [];

    for(let i=0; i < array.length - 2; i++){
        if(array[i] != array[i-1]){ // making sure our solution set does not contain duplicate triplets
            let left = i + 1;
          let right = array.length - 1;

            while (left < right){
                const currentSum = array[i] + array[left] + array[right];
                if (currentSum === 0){
                    triplets.push([array[i], array[left], array[right]]);
                    while(array[left] == array[left + 1]) left ++
                    while(array[right] == array[right - 1]) right -- // making sure our solution set does not contain duplicate triplets
                    left ++;
                    right --;
                } else if(currentSum < 0) {
                    left ++
                } else if(currentSum > 0){
                    right --
                }
            }
        }
    }
    return triplets
};

Leetcode - Validate Binary Search Tree (with JavaScript)

Urfan Guliyev — Sun, 20 Sep 2020 22:37:46 +0000

Today I am going to show how to solve the Validate Binary Search Tree.

Here is the problem:

Before explaining the solution to this problem, I am going to shortly go over what a Binary Search Tree (BST) is.

Generally a tree is a data structure composed of nodes. Each tree has a root node which is the highest node and has zero or more child nodes. As stated in the problem, a Binary Search Tree is a type of tree in which each node has up to two children and adheres to the following properties:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Based on all of this, we can say that every node in BST has a minimum value and a maximum value.

Therefore, I am going to traverse the entire given tree by starting from the root node. Then, I move down from the root to validate all the subtrees by checking if all of the subtrees’ nodes are wrapped between their minimum value and maximum value. I will do this until I reach null values i.e. leaf nodes that don't have any child nodes.

For this, I created a helper method (validateBst) which takes in additional arguments, a minValue and a maxValue, and I pass down values as we traverse the tree. When I call the helper method on the left subtree of a node, I change the maximum value to be the value of our current node. When I call the function on our left subtree, I change the maximum value to be the current value of our node.

var isValidBST = function(root) {
    return validateBst(root, -Infinity, Infinity)
};

function validateBst(root, minValue, maxValue) {
    if(root == null) return true;
     if(root.val >= maxValue || root.val <= minValue) return false;
    return validateBst(root.right, root.val, maxValue) &&
            validateBst(root.left, minValue, root.val)
}

Leetcode - Longest Palindromic Substring (with JavaScript)

Urfan Guliyev — Mon, 14 Sep 2020 01:26:27 +0000

Today I am going to show how to solve the Longest Palindromic Substring.

Here is the problem:

In my last blog I talked about how to determine whether or not a string is a palindrome. A palindrome is a string that's written the same forward as backward.

But this problem is a bit different in that not only do we have to find out if a string is a palindrome, we also have to find the longest palindromic substring.

Before diving into the solution, I’d like to note that a single character is considered a palindrome. For instance, the letter 'a' alone is considered to be a palindrome because it's written the same forward as backward.

We know that every palindrome has a center. If it's of odd length, then the center of the palindrome is a letter. But if it's of even length, then the center of the palindrome is just in between two letters.

We can iterate through our input string and treat each given point as if it could be the center of a palindrome. The center could be at the given letter, or between the given letter and the previous letter. When we are in the middle of a palindrome, we can then expand and look at the two next letters to the side of it and see if they're equal to each other. And then update our current longest palindrome accordingly.

We never actually have to store the palindromes; we can just store the index of the starting letter of the palindrome and the index of the last letter.

We essentially continue to check the center of a potential palindrome and expand from it. And that's going to end up running in O(n^2).

var longestPalindrome = function(s) {
    let currentLongest = [0, 1];

    for (let i=1; i< s.length; i++){
        const odd = expandAroundCenter(s, i-1, i+1); // treating the given letter as a center and checking its surrounding letters 
        const even = expandAroundCenter(s, i-1, i); // checking if the  center is between the given letter and the previous letter
        const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even; // choosing the longest palindrome between odd and even
        currentLongest = currentLongest[1] - currentLongest[0] > longest [1] - longest[0] ?  currentLongest : longest // comparing the longest to the current longest palindrome and updating current longest accordingly
    } 
    return s.slice(currentLongest[0], currentLongest[1]);
};

function expandAroundCenter(s, leftIdx, rightIdx){
    while (leftIdx >= 0 && rightIdx < s.length){
        if(s[leftIdx] !== s[rightIdx]) break;
        leftIdx--;
        rightIdx++;
    }
    return[leftIdx + 1, rightIdx] 
}

Leetcode - Climbing Stairs (with JavaScript)

Urfan Guliyev — Sun, 06 Sep 2020 22:31:21 +0000

Today I am going to show how to solve the Climbing Stairs algorithm problem.

Here is the problem:

I am going to build a tree to help better understand the solution to this problem.

Let’s determine in how many distinct ways we can climb to the top of a 4-step staircase.

I am going to add branches to the tree based on the number of steps we can take. In this problem, we can either take 1 step or 2 steps. If we take 1 step, we will have to climb 3 more steps. If we take 2 steps, we will have 2 steps left. I will continue to add branches until I reach the base cases:

When we have 0 steps, how many ways are there to climb? There's 1 way - we just don’t climb.
When we have 1 step, how many ways are there to climb? There's 1 way - just climbing on that one step.

To calculate the total number of ways to climb the staircase, we have to first figure out how many ways there are to get to each step, starting from the bottom. We then add the number of ways for each step together and find that there are a total of 5 ways to climb a 4-step staircase.

Now we can see that the solution to this problem is the sum of its subproblems. In our case, the total number of ways to climb a 4-step staircase is the sum of the total ways to climb a 3-step staircase and a 2-step staircase. Based on that we can write:
num_ways(4) = num_ways(3) + num_ways(2)
For n number of steps, the equation is:
num_ways(n) = num_ways(n-1) + num_ways(n-2)

This is actually a fibonacci sequence. Each number in a fibonacci sequence is the sum of the two preceding ones, starting from 0 and 1.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Fib(n)=Fib(n−1)+Fib(n−2)

So the solution will be:



var climbStairs = function(n) {
    if (n == 1 || n == 0) return 1 // our base cases

    let first = 1;
    let second = 2;

    for (let i = 3; i <= n; i++) {
        let third = first + second;
        first = second;
        second = third;
    }
    return second;

};

Leetcode - Valid Palindrome (with JavaScript)

Urfan Guliyev — Sun, 30 Aug 2020 19:22:47 +0000

Today I am going to show how to solve the Valid Palindrome algorithm problem.

Here is the problem:

Let’s take a simple example and determine whether or not this string is a palindrome. A palindrome is a string that's written the same forward as backward.

"abcdcba"

There are several ways to solve it. First, I’ll look at the simplest and most straightforward ways.

We can build up a new string (newString += s[i]) that is going to be the reversed version of our input string. We then compare that new string to the input string to see if they are equal to each other. If they are equal, it means our input string is a palindrome.

This solution will give us O(N) space and O(n^2) time complexity. We can improve the time complexity from O(n^2) to O(n) by using an array.

Instead of creating a new string, we can just store everything in an array. Then at the end, we can join all the elements of the array into one string and then do the comparison to determine if the string is a palindrome.

We can improve this solution by iterating through the string and using pointers.

We can start with a pointer on the first letter and a pointer on the last letter. Then we compare the two. If they are equal to each other, we keep moving the pointers to the next letters until the pointers overlap. Then we return true, indicating that the string is indeed a palindrome. If they are not equal to each other, then we return false.

var isPalindrome = function(s) {

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};

What do we do if a string has spaces or other symbols in it?

"A man, a plan, a canal: Panama"

There is no inbuilt method in Javascript to determine if the specified character is a letter or digit. We could build a helper method to pass the string through. But I am going to use a different approach. Before iterating through the string, I am going to remove all spaces and symbols. by using the replace() method with regex. It takes two parameters, the string to be replaced and the string we are replacing it with.

NOTE: https://regexr.com/ is a good resource for learning and practicing regex expressions.

var isPalindrome = function(s) {
    s = s.replace(/[^a-zA-Z0-9]/g,"").toLowerCase();

    let leftIdx = 0;
    let rightIdx = s.length - 1;

    while(leftIdx < rightIdx){
        if (s[leftIdx] !== s[rightIdx]) return false

        rightIdx --
        leftIdx ++ 

    }
    return true
};

Leetcode - Symmetric Tree (with JavaScript)

Urfan Guliyev — Sun, 23 Aug 2020 03:00:59 +0000

Today I am going to show how to solve the Symmetric Tree algorithm problem.

Here is the problem:

In this problem we need to test whether or not a binary tree is symmetrical in its structure and value. The question then is: when are two trees a mirror reflection of each other?

A tree is symmetric if the left subtree is a mirror reflection of the right subtree. If we draw a line down the middle of our tree, the tree can fold on itself and its node values will be equivalent.

Now, I am going to solve it recursively.

1) First, I check the root node. If it is null, no further action is needed. If it is not null, we need to go into recursion and check both the left and right subtrees.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

2) If a left subtree and a right subtree are both null, it means that they are symmetric. If just one of them is null, then they are asymmetric.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;
}

3) If they are both not null, we need to check their values. If they are the same, we are going to continue our recursion to the left and to the right of the nodes. We have to make sure that our left subtree’s left node is equivalent to our right subtree’s right node, and our left subtree’s right node is equivalent to our right subtree’s left node.

var isSymmetric = function(root) {
    if (root == null) return true;
    return isMirror(root.left, root.right);
};

const isMirror = function(leftSub, rightSub) {
    if (leftSub == null && rightSub == null) return true;
    if (leftSub == null || rightSub == null) return false;

    return (leftSub.val === rightSub.val 
            && isMirror(leftSub.left, rightSub.right) 
            && isMirror(leftSub.right, rightSub.left))
}

Leetcode - Move Zeros (with JavaScript)

Urfan Guliyev — Sat, 15 Aug 2020 17:32:29 +0000

Today I am going to show how to solve the Move Zeros algorithm problem.

Here is the problem:

There are multiple ways to solve this problem. Brute Force is the first method everybody comes up with. We iterate through the given array, push all non-zero elements to the newly created array, and then fill the rest of it with 0’s.

But as noted in the problem, we should solve this in-place without making a copy of the array. That’s why I am using the two pointer approach.

1) First, I declare variable nonZeroIndex to keep track of where (index) I am going to place the variable if it is not 0.



var moveZeroes = function(nums) {
    let nonZeroIndex = 0;
};

2) I walk through the array by using the “for” loop to check whether or not an element is 0. As we keep finding new non-0 elements, we just overwrite them at the "nonZeroIndex + 1" 'th index.



var moveZeroes = function(nums) {

    let nonZeroIndex = 0;

    for(let i=0; i < nums.length; i++){
        if(nums[i] != 0) {
            nums[nonZeroIndex] = nums[i];
            nonZeroIndex ++;
        }
    }
};

3) Once we’ve reached the end of the array, we see that all of the non-zero elements have been moved to the beginning of the array in their original order. We now need to move all of the 0's to the end. We do this by simply filling the rest of the array (all the indexes after the "nonZeroIndex" index) with 0’s.



var moveZeroes = function(nums) {

    let nonZeroIndex = 0;

    for(let i=0; i < nums.length; i++){
        if(nums[i] != 0) {
            nums[nonZeroIndex] = nums[i];
            nonZeroIndex ++;
        }
    }

    for(let i = nonZeroIndex; i < nums.length; i++) {
        nums[i] = 0;
    }

};

Leetcode - Reverse Linked List(with JavaScript)

Urfan Guliyev — Mon, 10 Aug 2020 00:29:20 +0000

Today I am going to show how to solve the Reverse Linked algorithm problem.

Here is the problem:

In this blog I am going to use both the iterative and recursive ways to reverse a single link list.

1. Iterative solution:

First, I’m going to initialize 3 pointers:

prev -> Because it’a a singly linked list, a node does not have reference to its previous node. That’s why we need prev pointer to store a previous element of the node beforehand.
curr -> to know which node we are currently at.
nextTemp -> to store the next node before changing the reference. If we change the current’s next value without saving it, we are going to lose our next pointer in the iteration.



var reverseList = function(head) {
    let prev = null;
    let curr = head;
    let nextTemp = curr.next;

Then, I iterate through all nodes to traverse the list.



var reverseList = function(head) {
    let prev = null;
    let curr = head;
    let nextTemp = null;

    while(curr!= null) {
        nextTemp = curr.next; // As I explained earlier, I save the next pointer in the temp variable.
        curr.next = prev;  // Then I reverse the pointer of the current node to its previous node.
        prev = curr;  //  The previous node becomes the node we are currently at.
        curr = nextTemp;  // And the current nodes becomes the
next node we saved earlier. And we keep iterating.
    }
    return prev // At the end, our previous node will be the head node of the new list. 
};

2. Recursive solution:

I will use the linked list below for explaining this solution:

1 -> 2 -> 3 -> 4 ->null

The first call will be from the main method and it will pass in the head of the list (node 1). This method needs to return a new head (node 5), which is the last element of the linked list.

We therefore need to go all the way to the end of the list, just as we would in recursion. Once we hit that 5 we should hopefully hit our base case, which will then allow us to go backwards and finish up the algorithm.

Like in all recursive methods, we need to have a base case. The base case indicates how this method is going to stop recursively calling itself. Our base is going to include 2 parts. One of them will check if the next node is null. If it is null, then it means we are on the last element, which will be returned as a new head node of the reversed linked list.



var reverseList = function(head) {
    if(head == null || head.next == null) {
        return head
    }
};

Because this is a recursive method, the system returns node 5 back to the previous caller (node 4) and stores it in the head variable.
Now we need to reverse the linked list by making node 5 to point to node 4.

Because we are currently at 4 (head), we need to go to the next node (head.next) and point it back to itself (head.next.next = head).
We want essentially the end of the linked list to point to null. Let’s now point 4 to null by saying node.next = null

This process keeps going until we reverse all nodes.



var reverseList = function(head) {
    if(head == null || head.next == null) {
        return head
    }
    newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

Leetcode - House Robber (with JavaScript)

Urfan Guliyev — Mon, 03 Aug 2020 04:01:12 +0000

Today I am going to show how to solve the House Robber algorithm problem.

Here is the problem:

For solving this problem, I’ll use dynamic programming to keep an array of the maximum amounts of money that we can rob, as I loop through an array of houses.

Before doing all of that, I write the first case of when there is no house to rob:

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

};

Now I make a dynamic programming array and start looking at the houses one by one.

The maximum amount of money we can rob up to the 1st house(nums[0]) is just for robbing that house.
The maximum amount of money we can rob up to the 2nd house (nums[1]) would be either the maximum of the 1st (nums[0]) or of the 2nd (nums[1]) house, whichever is greater.

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

    dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

};

At the 3rd (nums[2]) house, everything gets more interesting. Because we can not rob adjacent houses, we have to decide between robbing both the 3rd and the 1st house, or just robbing the 2nd house.

Because we’ve already checked the first 2 houses, I will start looping at the third house, where i=2.

The loop will check which is greater: robbing the current house + the maximum amount of money we can get from the 2 houses before it, or the previous maximum amount of money we robbed.

At the end, all we have to do is just return the last element of the dp array.

var rob = function(nums) {

    if( nums == null || nums.length == 0) {
        return 0
    }

    dp = []
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

    for (let i = 2; i < nums.length; i++){
        dp[i] = Math.max(dp[i-1], nums[i] + dp[i-2])
    }

    return dp[nums.length - 1]

};

Leetcode - Pascal's Triangle (with JavaScript)

Urfan Guliyev — Sun, 26 Jul 2020 23:44:06 +0000

Today I am going to show how to solve the Pascal's Triangle algorithm problem.

Here is the problem:

Before solving the problem, we should understand how Pascal's Triangle works:

Pascal's Triangle starts with "1" at the top, then continues placing numbers below it in a triangular pattern.
Each number is the sum of the two numbers directly above it.
The first and last row elements are always 1.

Now let’s start to solve the problem

1) First I wrote the base case. If a user requests zero rows, they get zero rows.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }
}

2) Next, I iterate numRows times using for loop to build Pascal's Triangle. Then I add the second base case -> the first row of the triangle and the first element of all rows are always 1.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }

    for (var i = 0; i < numRows; i++) {

        triangle[i] = [];
 //Second base case
        triangle[i][0] = 1;
    }
}

3) While I iterate the rows, I also use the second loop to build the elements of each row. Each triangle element (other than the first and last of each row) is equal to the sum of the elements above-and-to-the-left and above-and-to-the-right.

var generate = function(numRows) {
    var triangle = [];

//First base case
    if(numRows == 0) { 
        return triangle
    }

    for (var i = 0; i < numRows; i++) {

        triangle[i] = [];
//Second base case
        triangle[i][0] = 1;

        for (var j = 1; j < i; j++) {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
//The last element of all rows are always 1.
        triangle[i][i] = 1;
    }

    return triangle;
}

Leetcode - Missing Number (with JavaScript)

Urfan Guliyev — Mon, 20 Jul 2020 02:07:05 +0000

Today I am going to show how to solve the Missing Number algorithm problem.

Here is the problem:

Solution:
I solved this problem in 2 different ways.

The first one is easier and simpler. I used a Set data structure to store an array. Then I iterate through it to find which number is missing.



var missingNumber = function(nums) {
    let map = new Set(nums);

    let expectedLength = nums.length + 1

    for (let number = 0; number < expectedLength; number++) {
        if (!map.has(number)) {
            return number
        }
    }

    return -1
};

For the second solution I use Gauss' formula, which helps to sum sequences of numbers. You can see the formula below:

Essentially, all we have to do is to find the expected sum by using Gauss’ formula and then subtract from it the actual sum of the array.



var missingNumber = function(nums) {
    let expectedSum = nums.length*(nums.length + 1)/2
    let actualSum = nums.reduce((a, b) => a + b, 0)
    let missingNumber = expectedSum - actualSum

    return missingNumber 
};