DEV Community: codingpineapple

Leetcode 163. Missing Ranges (javascript solution)

codingpineapple — Tue, 07 Dec 2021 05:33:50 +0000

Description:

You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.

A number x is considered missing if x is in the range [lower, upper] and x is not in nums.

Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.

Each range [a,b] in the list should be output as:

"a->b" if a != b
"a" if a == b

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

var findMissingRanges = function(nums, lower, upper) {
    // array to add ranges
    const result = []
    // start at lower - 1 for edge case where lower === nums[0]
    let prev = lower - 1;
    // loop for nums.length times so we can compare the last value with upper
    for (let i = 0; i <= nums.length; i++) {
        // current number to compare to prev
        // when i === nums.length we will compare prev = nums[nums.length-1] and upper
        // the upper+1 is to account for nums[nums.length-1]===upper
        let curr = (i < nums.length) ? nums[i] : upper + 1;
        // check if we need to add a range to the array
        if (prev + 1 <= curr - 1) {
            // if equal then add any of the numbers to the array
            // if < than, then add the range string to the array
            result.push(prev + 1===curr - 1?`${prev + 1}`:`${prev + 1}->${curr - 1}`);
        }
        // set prev to compare in the next iteration
        prev = curr;
    }
    return result 
};

LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram (javascript)

codingpineapple — Fri, 03 Sep 2021 02:32:09 +0000

Description:

Given two equal-size strings s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

var minSteps = function(s, t) {
    // Array to hold the counts of each letter
    const counts = new Array(26).fill(0);

    // Add counts of each letter to the array
    // zero = no difference, positive or negative count = count difference between the two strings for a particular
    for (let i = 0; i < s.length; i++) {
        counts[t.charCodeAt(i) - 97]++;
        counts[s.charCodeAt(i) - 97]--;
    }

    let output = 0;

    // Add the letter count differences together
    for (let i = 0; i < 26; i++) {
        if (counts[i] > 0) output += counts[i];
    }

    return output;
};

LeetCode 128. Longest Consecutive Sequence (javascript solution)

codingpineapple — Sun, 29 Aug 2021 20:46:16 +0000

Description:

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

var longestConsecutive = function(nums) {
    // Handle base case of empty array
    if (!nums.length) return 0;

    // Give ability to look up nums by value
    const set = new Set(nums);
    let max = 0;

    for (const num of set) {
        // Make sure we are starting at the beginning of the sequenece
        if (set.has(num - 1)) continue;

        let currNum = num;
        let currMax = 1;

        // Look numbers that make a consecutive sequence
        while (set.has(currNum + 1)) {
          currNum++;
          currMax++;
        }
        // Update max
        max = Math.max(max, currMax);
    }

    return max;
};

LeetCode 417. Pacific Atlantic Water Flow (javascrpt solution)

codingpineapple — Sat, 28 Aug 2021 23:33:37 +0000

Description:

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n^2)

var pacificAtlantic = function(heights) {
    // Set amount of rows and columns to variables
    const numRows = heights.length
    const numCols = heights[0].length

    // Create matrixes to hold which cells can visit each ocean
    const pacific = Array(numRows).fill().map(() => Array(numCols).fill(false))
    const atlantic = Array(numRows).fill().map(() => Array(numCols).fill(false))

    // Run dfs on first and last columns that touch an ocean
    for (let col=0 ;col<heights[0].length;col++){
       dfs(0, col, -Infinity, pacific)
       dfs(numRows - 1, col, -Infinity, atlantic)
    }

    // Run dfs on each cell on the top and bottom rows that touch an ocean
    for (let row = 0;row<heights.length; row++){
        dfs(row, 0, -Infinity, pacific)
        dfs(row, numCols - 1, -Infinity, atlantic)
    }

    // Starting from an edge of heights that touches an ocean, move inward and add all cells to the ocean matrix that can spill into the previously vistited cell
    function dfs(i, j, prev, ocean){
        // Stop dfs if we given coordinates that are not on the board, if the value of the cell we are visiting cannot spill water into the previous cell, or if we have already visited this cell
        if (i<0 || i >= numRows || j < 0 || j >= numCols || heights[i][j] < prev || ocean[i][j]) {
            return
        }

        // Set this cell as visited by the current ocean
        ocean[i][j] = true

        // Look in all directions to find more nodes that can visit the current ocean by flowing into the cell at [i, j]
        dfs(i+1, j, heights[i][j], ocean)
        dfs(i-1, j, heights[i][j], ocean)
        dfs(i, j+1, heights[i][j], ocean)
        dfs(i, j-1, heights[i][j], ocean)    
    }

    const res = []

    // Check which cells [i, j] are able to touch both oceans by checking if a cell is in both ocean matrixes
    for (let i=0;i<numRows;i++){
        for (let j=0;j<numCols;j++){
            if (atlantic[i][j] && pacific[i][j]){
                res.push([i, j])
            }
        }
    }
    return res
}

LeetCode 133. Clone Graph (javascript solution)

codingpineapple — Mon, 23 Aug 2021 04:03:42 +0000

Description:

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {
public int val;
public List neighbors;
}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// DFS approach
var cloneGraph = function(node) {
    // Nodes we have already copied
    const visited = {};

    // DFS function to copy graph
    const dfs = (node) => {
        if (!node) return node;
        // If we have seen this node before, return it
        if (visited[node.val]!=null) return visited[node.val];

        // Create base for copied node
        const root = new Node(node.val);
        // Add this copied node to group of nodes we hav copied
        visited[node.val] = root;

        // Add copied neighbors to the current copied node
        node.neighbors.forEach(n => root.neighbors.push(dfs(n)))
        return root;
    }

    // Return new copied graph
    return dfs(node);
};

LeetCode 91. Decode Ways (javascript solution)

codingpineapple — Mon, 09 Aug 2021 04:05:39 +0000

Description:

A message containing letters from A-Z can be encoded into numbers using the following mapping:

'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// DP solution
var numDecodings = function(s) {
    // Create dp array
    const dp = Array(s.length+1).fill(0);
    // If the first number is 0 then return we cannot decode this string
    if(s[0]==='0') return 0
    // Base cases
    dp[0] = 1;
    dp[1] = 1

    for(let i = 2; i <= s.length; i++) {
        // Get values for one and two digit numbers
        const oneDigit = +s.slice(i-1, i);
        const twoDigits = +s.slice(i-2, i);
        // Check if one digit and/or two digit numbers are valid
        if(oneDigit > 0) dp[i] = dp[i-1];
        if(twoDigits >= 10 && twoDigits <= 26) dp[i] += dp[i-2]
    }    
    return dp[s.length];
};

LeetCode 300. Longest Increasing Subsequence (javascript solution)

codingpineapple — Wed, 28 Jul 2021 01:56:30 +0000

Description:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Solution:

Time Complexity : O(n^2)
Space Complexity: O(n)

// Dynamic programming
var lengthOfLIS = function (nums) {
    // Create dp array
    const dp = Array.from(nums, () => 1);
    // Max subsequence length
    let max = 1
    // Check all increasing subsequences up to the current ith number in nums
    for (let i = 1; i < nums.length; i++) {
        // Keep track of subsequence length in the dp array
        for (let j = 0; j < i; j++) {
            // Only change dp value if the numbers are increasing
            if (nums[i] > nums[j]) {
                // Set the value to be the larget subsequence length
                dp[i] = Math.max(dp[i], dp[j] + 1)
                // Check if this subsequence is the largest
                max = Math.max(dp[i], max)
            }
        }
    }
  return max;
};

LeetCode 11. Container With Most Water (javascript solution)

codingpineapple — Mon, 26 Jul 2021 00:40:15 +0000

Description:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

// 2 pointers
var maxArea = function(height) {
    // Max amountof water
    let max = 0
    // Pointer to move possible heights
    let left = 0
    let right = height.length-1
    // Use 2 pointers to find the max area
    while(left < right) {
        // Current area
        const area = Math.min(height[left], height[right]) * (right - left)
        // Check if current area is greater than previous max
        max = Math.max(max, area)
        // Move the pointer that has the lowest height
        if(height[left]>height[right]) {
            right--
        } else {
            left++
        }
    }
    return max
}

LeetCode 33. Search in Rotated Sorted Array (javscript solution)

codingpineapple — Sat, 24 Jul 2021 20:53:09 +0000

Description:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Solution:

Time Complexity : O(log n)
Space Complexity: O(1)

// Binary search
var search = function(nums, target) {
    let left = 0, right = nums.length-1;
    while(left < right){
      const mid = left + Math.floor((right - left)/2)
      if(nums[mid]===target) return mid
      // When middle element is less than the last element
      if (nums[mid] < nums[right]) {
            if (target > nums[mid] && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        } 
        // When middle element is greater than the last element
        else {
            if (target > nums[mid] || target < nums[left]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
    }
    return left
};

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

codingpineapple — Mon, 19 Jul 2021 05:33:45 +0000

Description:

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

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

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

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

var maxProfit = function(prices) {
    let profit = 0
    let min = prices[0]
    for(let i = 1; i < prices.length; i++){
        // The day we should buy at
        min = Math.min(min, prices[i-1])
        // Check if selling at the current day gives us the most profit
        profit = Math.max(prices[i]-min, profit)
    }
    return profit
};

LeetCode 153. Find Minimum in Rotated Sorted Array (javascript solution)

codingpineapple — Sun, 27 Jun 2021 00:56:58 +0000

Description:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Solution:

Time Complexity : O(log(n))
Space Complexity: O(1)

// Binary Search 
var findMin = function(nums) {
    let left = 0, right = nums.length-1;
    while(left < right) {
        const mid = left + Math.floor((right-left)/2)
        // Move right pointer if num at mid is less than or equal to num at right. This means that the smallest number must be on the left side of mid including mid.
        if(nums[right] >= nums[mid]) {
            right = mid
        } else {
            left = mid+1
        }
    }
    return nums[left]
};

LeetCode 152. Maximum Product Subarray (javascript solution)

codingpineapple — Wed, 16 Jun 2021 06:10:20 +0000

Description:

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

It is guaranteed that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Solution:

Time Complexity : O(n)
Space Complexity: O(1)

var maxProduct = function(nums) {
    // Max product in the current contiguous array
    let currentMax = nums[0];
    // Mind product in the current contiguous array. We need this value in case we encounter 2 negative numbers whose product could potentially give us the max product of the entire array
    let currentMin = nums[0];
    // Max product of a contiguous array
    let finalMax = nums[0];

  for(let i = 1; i < nums.length; i++){
    let temp = currentMax
    // Because we are looking for a contiguous subarray product, the current max must contain the current number in the array. 
    currentMax = Math.max(Math.max(currentMax * nums[i], currentMin*nums[i]), nums[i])
    // Use temp here in case the previous currentMax was negative
    currentMin = Math.min(Math.min(temp * nums[i], currentMin*nums[i]), nums[i])
    // Record highest max at the end of every contiguous subarray
    finalMax = Math.max(currentMax, finalMax);
  }

  return finalMax;
};