Press "Enter" to skip to content

Posts published in “Easy”

LeetCode 9. Palindrome Number (javascript)

By stone on March 28, 2021

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Example 4:

Input: x = -101
Output: false

Constraints:

  • -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    // negative number is not a Palindrome Number
    if (x < 0) return false;
    let y = x;
    let reverse = 0;
    while (y > 0) {
        let lastDigit = y % 10;
        reverse = reverse * 10 + lastDigit;
        y = parseInt(y / 10);
    }
    return reverse === x ;
};

LeetCode 7. Reverse Integer (javascript)

By stone on March 27, 2021

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

Input: x = 123
Output: 321

Example 2:

Input: x = -123
Output: -321

Example 3:

Input: x = 120
Output: 21

Example 4:

Input: x = 0
Output: 0

Constraints:

  • -231 <= x <= 231 - 1

Solution:

/**
 * @param {number} x
 * @return {number}
 */

var reverse = function(x) {
    const str      = "" + Math.abs(x);   // convert absolute value to string
    const reversed = str.split("")       // get array of digit characters
                   .reverse()            // reverse it
                   .join("");            // join into string again;
    const num      = parseInt(reversed); // convert to integer
    const revNum = Math.sign(x) * num;   // multiple the sign
    // if out of range return 0
    if (revNum < Math.pow(-2, 31) || revNum > Math.pow(2, 31) - 1) return 0;
    return revNum;
}

LeetCode 14. Longest Common Prefix (javascript)

By stone on March 27, 2021

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] consists of only lower-case English letters.

Idea:

  • Use first string for comparison
  • loop through each string:
    • store the common letter if match
    • or return the answer if no match

Solution:

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) return "";
    let ans = "";
    for (let i = 0; i < strs[0].length; i++) {
        for (let s of strs) {
            if (s.length <= i || s[i] !== strs[0][i]) return ans;
        }   
        ans += strs[0][i];
    }
        
    return ans;
};

LeetCode 876. Middle of the Linked List (javascript)

By stone on March 27, 2021

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

Idea:

Use fast and slow pointers traversal

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    let slow = head;
    let fast = head;
    
    while(fast) {
        if (!fast.next) break;
        fast = fast.next.next;
        slow = slow.next;
    }
    
    return slow;
};

LeetCode 202. Happy Number (javascript)

By stone on March 27, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

  • 1 <= n <= 231 - 1

Idea:

create a function to calculate the sum of the squares of its digits.

use fast and slow pointers traversal concept (the other one execute function twice) to check if they can reach 1 (means it is happy number)

Solution:

/**
 * @param {number} n
 * @return {boolean}
 */
var isHappy = function(n) {
    let slow = n;
    let fast = n;
    
    do {
        slow = squareSum(slow);
        fast = squareSum(squareSum(fast));
    } while (slow !== fast);
    
    return fast === 1;
};

var squareSum = function(n) {
    let sum = 0;
    while(n) {
        sum += (n % 10) * (n % 10);
        n = parseInt(n / 10);
    }
    return sum;
};

LeetCode 141. Linked List Cycle (javascript)

By stone on March 27, 2021

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

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

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

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

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

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

Idea:

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

Solution:

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

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

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

By stone on March 27, 2021

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

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

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

Example 1:

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

Example 2:

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

Constraints:

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

Idea:

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

Solution:

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

LeetCode 26. Remove Duplicates from Sorted Array (javascript)

By stone on March 26, 2021

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

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

Clarification:

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

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

Internally you can think of this:

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

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

Example 1:

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

Example 2:

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

Constraints:

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

Solution:

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

LeetCode 2. Add Two Numbers

By stone on March 18, 2021

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.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]

Output: [7,0,8]

Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]

Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each linked list is in the range [1, 100].
  • 0 <= Node.val <= 9
  • It is guaranteed that the list represents a number that does not have leading zeros.
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let head = new ListNode();
    let temp = head;
    let sum = 0;
    let carry = 0;
    while (l1 !== null || l2 !== null) {
        sum = carry + (l1 !== null ? l1.val : 0) + (l2 !== null ? l2.val : 0);
        carry = sum >= 10 ? 1 : 0;
        sum = sum % 10;
        
        temp.next = new ListNode(sum);
        temp = temp.next;
        
        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
        
        if (carry) temp.next = new ListNode(carry);
    }
    return head.next;
};

LeetCode 387. First Unique Character in a String

By stone on March 18, 2021

Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

Note: You may assume the string contains only lowercase English letters.

Idea: Hashtable

Solution:

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    let map = new Map;
    
    for (let i = 0; i < s.length; i++) {
        if (map.has(s[i])) {
            map.set(s[i], map.get(s[i]) + 1);
        } else {
            map.set(s[i], 1);
        }
    }
    
    for (let i = 0; i < s.length; i++) {
        if (map.get(s[i]) === 1) return i;
    }
    return -1;
};