DSJSApp

/* 1 Return indices of 2 numbers in Array, which add up to another number.


Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. */

// 1
let twoSum = function(nums, target) {
    const seenNumsWithIndexes = {};

    for (let i = 0; i < nums.length; i++) {
      const num = nums[i];
      if (seenNumsWithIndexes[target - num] !== undefined) {
        return [seenNumsWithIndexes[target - num], i];
      }
      seenNumsWithIndexes[num] = i;
    }
  };

//   console.log(twoSum([2,8,3,7],9)); // [ 0, 3 ]

/* 2 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 */

/** 2 @param {ListNode} l1 | @param {ListNode} l2 | @return {ListNode} */
var addTwoNumbers = function(l1, l2) {
    var carry = 0;
    var digitSum = 0;
    var head = new ListNode();
    var now = head;
    while (l1 || l2) {
      digitSum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
      carry = digitSum > 9 ? 1 : 0;
      now.next = new ListNode(digitSum % 10);
      now = now.next;
      l1 = l1 ? l1.next : null;
      l2 = l2 ? l2.next : null;
    }
    if (carry) now.next = new ListNode(carry);
    return head.next;
  };
  //  Time complexity : O(max(m,n)). Space complexity : O(max(m,n)).

//   console.log(listToArray(addTwoNumbers(arrToList([2,4,3]), arrToList([5,6,4])))); // [ 7, 0, 8 ]
//   // listToArray(addTwoNumbers(arrToList([9,9,9,9,9,9,9]), arrToList([9,9,9,9]))); // [8,9,9,9,0,0,0,1]

  // Helper functions
  function ListNode(val, next) {
       this.val = (val ? val : 0)
       this.next = (next ? next : null);
   }

  function listToArray(list) {
    let arr = []; // Initialise an array to return
     while (list) {
      arr = [...arr, list.val];
      list = list.next;
    };
    return arr;
  }

  function arrToList (arr) {
    let obj = null;
    for(i=0;i<arr.length;i++){
      obj = {val: arr[i], next: arrToList(arr.slice(i+1,arr.length))}
    }
    return obj;
  }

/* 3 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. */

/** 3 @param {string} s| @return {number} */
let lengthOfLongestSubstring = function(s) {
    let map = {};
    let max = 0;
    let start = 0;
    for (let i = 0; i < s.length; i++) {
      if (map[s[i]] !== undefined) {
        start = Math.max(start, map[s[i]] + 1); // start from latest instance of char
      }
      map[s[i]] = i;
      max = Math.max(max, i - start + 1);
    }
    return max;
  };

//   console.log(lengthOfLongestSubstring("pwwkew")); // 3

/* 8 Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

Only the space character ' ' is considered as whitespace character.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INTMAX (231 − 1) or INTMIN (−231) is returned.
Example 1:

Input: "42"
Output: 42
Example 2:

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.
Example 3:

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.
Example 4:

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical
             digit or a +/- sign. Therefore no valid conversion could be performed.
Example 5:

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned. */

/** 8 @param {string} str | @return {number} */
let myAtoi = function(str) {
    let i = 0;
    let sign = 1;
    let res = 0;
    // str = str.trim();
    let INT_MAX = Math.pow(2, 31) - 1;
    let INT_MIN = - Math.pow(2, 31); // 2147483648

    while (str[i] === ' ') i++; // str.trim();

    if (str[i] === '+' || str[i] === '-') {
      sign = str[i] === '+' ? 1 : -1;
      i++;
    }

    while (str[i] >= '0' && str[i] <= '9') {
      res = (res * 10) + (str[i] - 0);
      if (sign === 1 && res > INT_MAX) return INT_MAX;
      if (sign === -1 && res > INT_MIN) return INT_MIN;
      i++;
    }

    return res * sign;
  };
  //  Time complexity : O(n). Space complexity : O(1).

//   console.log(myAtoi("-2147483649")); // -2147483648
//   console.log(myAtoi("lala -2147483649")); // 0
//   console.log(myAtoi("83649 jin")); // 0

// let numbers = [4, 2, 5, 1, 3];
// numbers.sort((a, b) => a - b);
// console.log('sorted numbers', numbers);

/* 11 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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2. */

/** 11 | @param {number[]} height |@return {number} */
var maxArea = function(height) {
    var max = 0;
    var l = 0; // left
    var r = height.length - 1; // right
    while (l < r) {
      max = Math.max(max, Math.min(height[l], height[r]) * (r - l));
      if (height[l] < height[r]) {
        l++;
      } else {
        r--;
      }
    }
    return max;
  };
  // Time complexity : O(n) | Space complexity : O(1).

//   console.log(maxArea([1,8,6,2,5,4,8,3,7]));

/* 15 Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
] */

/** 15 @param {number[]} nums | @return {number[][]} */
 var threeSum = function(nums) {
  var len = nums.length;
  var res = [];
  var l = 0; // left
  var r = 0; // right
  nums.sort((a, b) => (a - b));
  for (var i = 0; i < len; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    l = i + 1;
    r = len - 1;
    while (l < r) {
      if (nums[i] + nums[l] + nums[r] < 0) {
        l++;
      } else if (nums[i] + nums[l] + nums[r] > 0) {
        r--;
      } else {
        res.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) l++;
        while (l < r && nums[r] === nums[r - 1]) r--;
        l++;
        r--;
      }
    }
  }
  return res;
};
//Time complexity : O(n^2) | Space complexity : O(1)
// console.log(threeSum([-1,0,1,2,-1,-4]));

/* 16 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2). */

/** 16  @param {number[]} nums | @param {number} target | @return {number} */
 var threeSumClosest = function(nums, target) {
  var len = nums.length;
  var res = nums[0] + nums[1] + nums[2];
  var sum = 0;
  var l = 0; // left
  var r = 0; // right
  nums.sort((a, b) => (a - b));
  for (var i = 0; i < len - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    l = i + 1;
    r = len - 1;
    while (l < r) {
      sum = nums[i] + nums[l] + nums[r];
      if (sum < target) {
        l++;
      } else if (sum > target) {
        r--;
      } else {
        return sum;
      }
      if (Math.abs(sum - target) < Math.abs(res - target)) res = sum;
    }
  }
  return res;
};
// Time complexity : O(n^2) Space complexity : O(1)
// console.log(threeSumClosest([-1, 2, 1, -4],1));

/* Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid. */

/** 20 @param {string} s | @return {boolean} */
 var isPranthesisValid = function(s) {
  var stack = [];
  var len = s.length;
  var map = {
    '(': ')',
    '[': ']',
    '{': '}'
  };
  for (var i = 0; i < len; i++) {
    if (stack.length > 0 && map[stack[stack.length - 1]] === s[i]) { // value at map's key complements s[i]
    // if (stack.length > 0 && s[i] != s[i+1]) { // generic solution
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  return stack.length === 0;
};
// Time complexity : O(n) Space complexity : O(n)
// console.log(isPranthesisValid("()[]{}}"));
// console.log(isPranthesisValid("([{}])"));

// const animals = ['pigs', 'goats', 'sheep'];
// console.log(animals.push('chickens', 'cats', 'dogs')); // 6
// console.log(animals.pop()); // dogs

/* 21 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4 */

/** 21 @param {ListNode} l1 | @param {ListNode} l2 | @return {ListNode} */
var mergeTwoLists = function(l1, l2) {
  var head = new ListNode();
  var now = head;
  while (l1 || l2) {
    if (l1 === null || (l2 !== null && l2.val < l1.val)) {
      now.next = l2;
      l2 = l2.next;
    } else {
      now.next = l1;
      l1 = l1.next;
    }
    now = now.next;
  }
  return head.next;
};
// Time complexity : O(m+n) | Space complexity : O(m+n)


// console.log(listToArray(mergeTwoLists(arrToList([1,2,4]), arrToList([1,3,4])))); // [ 1,1,2,3,4,4 ]

/* Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both? */

/* Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf(). */

/** 28 @param {string} haystack | @param {string} needle | @return {number} */
 var strStr = function(haystack, needle) {
  var len1 = haystack.length;
  var len2 = needle.length;
  if (!len2) return 0;
  for (var i = 0; i < len1; i++) {
    for (var j = 0; j < len2; j++) {
      if (i + j === len1) return -1;
      if (haystack[i + j] !== needle[j]) break; // chars don't match
      if (j === len2 - 1) return i;
    }
  }
  return -1; // not found
};
// Time complexity : O(n*m) | Space complexity : O(1)
// console.log(strStr('Hello', 'llp')); // 2

var trap = function(height) {
  var res = 0;
  var left = 0;
  var right = height.length - 1;
  var leftMax = 0;
  var rightMax = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        res += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        res += rightMax - height[right];
      }
      right--;
    }
  }

  return res;
};
// Time complexity : O(n) | Space complexity : O(1)
// console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1])); // 6
// console.log(trap([1,0,1]));

/* Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both? */

/** 206 1 | @param {ListNode} head |@return {ListNode} */
var reverseList = function(head) {
    var newHead = null;
    var tmp = null;
    while (head) {
      tmp = head.next;
      head.next = newHead;
      newHead = head;
      head = tmp;
    }
    return newHead;
  };

//Time complexity : O(n). Space complexity : O(1).

// console.log(listToArray(reverseList(arrToList([2,4,3]))));

/** 206 2 | @param {ListNode} head |@return {ListNode} */
var reverseListRecursion = function(head) {
  return reverse(null, head);
};

var reverseRecursion = function (newHead, head) {
  if (!head) return newHead;
  var tmp = head.next;
  head.next = newHead;
  return reverse(head, tmp);
};

// Time complexity : O(n). Space complexity : O(n).

// console.log(listToArray(reverseListRecursion(arrToList([2,4,3]))));

/**  @param {number} num | @return {string} */
 var intToRoman = function(num) {
  var map = [
    [1, "I"],
    [4, "IV"],
    [5, "V"],
    [9, "IX"],
    [10, "X"],
    [40, "XL"],
    [50, "L"],
    [90, "XC"],
    [100, "C"],
    [400, "CD"],
    [500, "D"],
    [900, "CM"],
    [1000, "M"]
  ];
  var res = '';
  var i = 12;
  var tmp = 0;
  while (num > 0) {
    res += map[i][1].repeat(Math.floor(num / map[i][0]));
    num %= map[i][0];
    console.log(map[i][0]);
    i--;
  }
  return res;
};

// console.log(intToRoman(402)); // CDII
// console.log(intToRoman(3000)); // MMM
// console.log(intToRoman(93)); // XCIII
// console.log(intToRoman(4)); // IV

/**
 * @param {number} num
 * @return {string}
 */
 var intToRoman1 = function(num) {
  var str = [
    ['I', 'V'], // 1s
    ['X', 'L'], // 10s
    ['C', 'D'], // 100s
    ['M'] // 1000s
  ];
  var res = '';
  var i = 0;
  var digit = 0;
  for ( let i = 0 ; num > 0; i++) {
    digit = num % 10;
    if (digit === 9) {
      res = str[i][0] + str[i + 1][0] + res; // IX + res
    } else if (digit >= 5) {
      res = str[i][1] + str[i][0].repeat(digit - 5) + res;
    } else if (digit === 4) {
      res = str[i][0] + str[i][1] + res; // IV + res
    } else { // 0, 1, 2, 3
      res = str[i][0].repeat(digit) + res;
    }
    num = Math.floor(num / 10);
    // i++;
  }
  return res;
};

// console.log(intToRoman1(402)); // CDII
// console.log(intToRoman1(3000)); // MMM
// console.log(intToRoman1(93)); // XCIII
// console.log(intToRoman1(48)); // XLVIII
// console.log(intToRoman1(4)); // IV
// console.log(intToRoman1(900)); // CMXCIX



============
// convert a number to linked lint in reverse
f = n => n ? { val: n % 10, next: f(n / 10 | 0) } : null;

// console.log( f(465) ); // { val: 5, next: { val: 6, next: { val: 4, next: null } } }
============
function ReverseListNodeToArray(listNode) {
        let returnedArray = []; // Initialise an array to return
        if (listNode.next != null) { // ListNode has level?
            // returnedArray = returnedArray.concat( // Merge with the node result
            //     ReverseListNodeToArray(listNode.next)
            // );
          returnedArray = [...returnedArray, ...ReverseListNodeToArray(listNode.next)];
        }
        returnedArray.push(listNode.val); // Add current node's value
        return returnedArray;
    }

// console.log( ReverseListNodeToArray(f(465) ));
============