LeetCode Solutions in Javascript

Longest Substring Without Repeating Characters

Problem:

Given a string, find the length of the longest substring without repeating characters.

Examples

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution

Keep tracking the rightest qualified substring (head).

  head           i
   |             |
   ======c=======c······
   |<--length-->|

         head    i ->
          |      | 
   ······c======c======
          |<---length--->

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  const len = s.length
  if (len <= 1) { return len }
  
  const indices = { [s[0]]: 0 }
  let max = 1
  let head = 0
  let i = 0
  while (++i < len) {
    const last = indices[s[i]]
    if (last >= head) {
      max = Math.max(max, i - head)
      head = last + 1
    }
    indices[s[i]] = i
  }
  
  return Math.max(max, i - head)
};

Add Two Numbers

Problem:

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 contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution:

Mind the last carry.

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  const prehead = new ListNode()
  let p = prehead
  let carry = 0
  
  for (let p1 = l1, p2 = l2: p1 || p2 || carry > 0; p = p.next) {
    let sum = carry
    if (p1) {
      sum += p1.val
      p1 = p1.next
    }
    if (p2) {
      sum += p2.val
      p2 = p2.next
    }
    carry = sum / 10 | 0
    p.next = new ListNode(sum % 10)
  }
  
  return prehead.next
};

Two Sum

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

Map the numbers to their indices as we iterate, so that we can look them back up in O(1) time complexity.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const indicies = {}
  
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i]
    if (indicies[target - num] != null) {
      return [indicies[target - num], i]
    }
    indicies[num] = i
  }
};