1.EASY_LEETCODE

/*
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
APRIL 26th 2021 Monday: 
TWO SUM LEETCODE #1: 
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/
let nums = [2,4,7,15];
let target = 9;
var twoSum = function (nums, target) {
  for (let i=0; i<nums.length; i++){
    for(let j = i + 1; j<nums.length; j++) {
      if(nums[i] + nums[j] === target){
        return [i, j]
      }
    }
  }
}
twoSum(nums, target);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
APRIL 27th 2021 Tuesday: 
7. Reverse Integer
Difficulty Easy:
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
Return: 0000000001111001
Example 4:
Input: x = 0
Output: 0

Constraints:

-2 31 <= x <= 2 31 - 1

Our Plan: 
1.Convert Number Into String
2. Convert into Array using split
3. Reverse the Array
4. Join the Array Into a String Again
5. Use Parse Float (to account for decimals as well) and to Convert String into Number Again
5. Use Math.sign to get the sign from the original number and multiple the reversed number 
to keep the sign consistent 
6. Define a 32 bit number 
7. Use an if statement to return the reverse number only if it meets the 
Constraints of the 32 bit number 
8. Else Return 0 

*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/
       
var reverse = function(x) {
  let numToString = parseFloat(x.toString().split('').reverse().join('')) *  Math.sign(x);
  let z = Math.pow(2, 31);
  if (numToString < z && numToString > -z){
   return numToString
 } 
 else{
   return 0
   }
};

let input16Bit = 65536;  //2^16 Binary Number:10000000000000000
let input16BitNeg = -65536;
let inputFloat16 = 6.5536;
let input31Bit = 2147483648; //2^31 Binary Number:10000000000000000000000000000000
let input32Bit = 2147483647; //2^32 Binary Number:1111111111111111111111111111111
let input64Bit = 18446744073709551616; //2^64 

console.log(reverse(input64Bit))
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
9. Palindrome Number

Difficulty: Easy 
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

OUR PLAN: 
1. Convert Integer to String 
2. Split into Array 
3. Reverse Array
4. Join to String
5. Wrap All that in A Parse Float to Convert String back into an Integer
Compare that to Original Integer to see if it is a Palidrome if it's negative it will
automatically be false. And if it's a decimal that is taken care of by the Parse Float 
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var isPalindrome = function(x) {
    if (x === parseFloat(x.toString().split('').reverse().join(''))) {
      return true 
    }
   else{
     return false
   }   
};
console.log(isPalindrome(12.21));
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
APRIL 28 2020 WEDNESDAY

13. Roman to Integer
Difficulty: Easy

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. 
X can be placed before L (50) and C (100) to make 40 and 90. 
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.


Example 1:

Input: s = "III"
Output: 3
Example 2:

Input: s = "IV"
Output: 4
Example 3:

Input: s = "IX"
Output: 9
Example 4:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.
Example 5:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
 
Constraints:

1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
It is guaranteed that s is a valid roman numeral in the range [1, 3999]. 
Our Plan: 
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var romanToInt = function (s) {
  let symbols = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };

  let result = 0;
  for (let i = 0; i < s.length; i++) {
    if (symbols[s[i]] < symbols[s[i + 1]]) {
      result += symbols[s[i + 1]] - symbols[s[i]];
      i++;
    } else {
      result += symbols[s[i]];
    }
  }
   return result;
};
romanToInt('IV');
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*APRIL 28th THURSDAY
14. Longest Common Prefix
Difficulty Easy
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:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lower-case English letters.
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var longestCommonPrefix = function(strs) {
  let prefix = strs[0];
  console.log(strs[1][3]);
   for(i =1; i < strs.length; i++){
     for (j = 0; j < prefix.length; j++) {
       if (strs[i][j] !== prefix[j]) {
         prefix = strs[i].slice(0,j)
       }
     }
    }
   return prefix
};

let arrayOfStrings =  ["flower","flow","flight"];
longestCommonPrefix(arrayOfStrings);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
29 APRIL 2021 FRIDAY
20. Valid Parentheses
Difficulty Easy

Share
Given a string s 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.
 
Example 1:

Input: s = "()"
Output: true
Example 2:

Input: s = "()[]{}"
Output: true
Example 3:

Input: s = "(]"
Output: false
Example 4:

Input: s = "([)]"
Output: false
Example 5:

Input: s = "{[]}"
Output: true
 

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

}

*/

   /*hasOwnProperty returns a boolean value indicating whether the object on which you are calling it has a property(keys) with the name of the argument.here we are checking for the opening brackets so the keys in the object
    */
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

var isValid = function (s) {
  let parenthesesObj = {
    "(": ")",
    "{": "}",
    "[": "]",
  }
  const stack = [];
  for (const item of s) {
 //checking for opening brackets
    if (parenthesesObj.hasOwnProperty(item)) {
      stack.push(item)
    } else {
      let openBracket = stack.pop();
      //ex -> parenthesesObj[{]=}
      if (item !== parenthesesObj[openBracket]) {
        return false;
      }
    }
  }
  return stack.length === 0;
};
isValid("([)]");
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
1832. Check if the Sentence Is Pangram
Difficulty Easy
A pangram is a sentence where every letter of the English alphabet appears at least once.
Given a string sentence containing only lowercase English letters, return true if sentence is a pangram, or false otherwise.
Example 1:
Input: sentence = "thequickbrownfoxjumpsoverthelazydog"
Output: true
Explanation: sentence contains at least one of every letter of the English alphabet.
Example 2:

Input: sentence = "leetcode"
Output: false
 

Constraints:

1 <= sentence.length <= 1000
sentence consists of lowercase English letters.
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var checkIfPangram = function (sentence) {
  let alphabet = 'abcdefghijklmnopqrstuvwxyz';
  for (const letter in alphabet) {
   if (sentence.indexOf(alphabet[letter]) < 0) {
     return false;
    }
  }
  return true
};
checkIfPangram("thequickbrownfoxjumpsoverthelazydog");
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/    
/*
1480. Running Sum of 1d Array
Difficulty Easy

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i])
Return the running sum of nums.

Example 1:
Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:
Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:
Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]
 
Constraints:
1 <= nums.length <= 1000
-10^6 <= nums[i] <= 10^6

*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var runningSum = function(nums) {
let sum = 0;
let runSum = [];
for(const x in nums){
sum+=parseFloat(nums[x]);
runSum.push(sum);
}
return runSum;
};
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
1108. Defanging an IP Address
Difficulty Easy
Given a valid (IPv4) IP address, return a defanged version of that IP address.
A defanged IP address replaces every period "." with "[.]".
Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"
Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"
}
Constraints: The given address is a valid IPv4 address.
*/

*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var defangIPaddr = function (address) {
  return address.replace(/\./g, "[.]");
};
defangIPaddr("255.100.50.0");
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*21. Merge Two Sorted Lists
Easy

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


Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:

Input: l1 = [], l2 = []
Output: []
Example 3:

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

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both l1 and l2 are sorted in non-decreasing order.

Seen this question in a real interview before?*/


/*********OUR ANSWER *******DIDNT WORK*/
var mergeTwoLists = function(l1, l2){
let l3 = [...l1, ...l2];
l3.sort();
return l3
};
mergeTwoLists([1,5,4], [1,3,4] );


/**********FUCKED UP REAL ANSWER ********/
function ListNode(val) {
      this.val = val;
       this.next = null;
}

var mergeTwoLists = function(l1, l2) {
    let dummyHead = new ListNode(0);
    let currentNode = dummyHead; 

    while(l1 !== null && l2 !== null){

        if(l1.val < l2.val){
            currentNode.next = l1;
            l1 = l1.next
        } else {
            currentNode.next = l2
            l2 = l2.next
        }

        currentNode = currentNode.next
    }

    if(l1 !== null) {
        currentNode.next = l1;
    } else if (l2 !== null) {
        currentNode.next = l2
    }

    return dummyHead.next
}
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

/*
26. Remove Duplicates from Sorted Array
Difficulty : Easy

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.
*/
*/
/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
/******THIS QUESTION IS STUPID DONT DO IT */
var removeDuplicates = function(nums) {
  var len = nums.length;
  var last = NaN;
  var count = 0;
  for (var i = 0; i < len; i++) {
    if (nums[i] !== last) {
      nums[count] = nums[i];
      last = nums[i];
      count++;
    }
  }
  return count;
};
removeDuplicates([1, 1, 2]);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/


/*819. Most Common Word

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

Example 1:
Input: paragraph = "Bob hit a ball, the hit BALL flew far after it was hit.", banned = ["hit"]
Output: "ball"

Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Example 2:
Input: paragraph = "a.", banned = []
Output: "a"
 
Constraints: 1 <= paragraph.length <= 1000
paragraph consists of English letters, space ' ', or one of the symbols: "!?',;.".
0 <= banned.length <= 100
1 <= banned[i].length <= 10
banned[i] consists of only lowercase English letters.
*/

/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

var mostCommonWord = function (paragraph, banned) {
  let obj = {};
  let mostCommon;
 let wordArr = paragraph.toLowerCase().replace(/(~|`|!|@|#|$|%|^|&|\*|\(|\)|{|}|\[|\]|;|:|\"|'|<|,|\.|>|\?|\/|\\|\||-|_|\+|=)/g," ").split(" ");
  let bannedSet = new Set();
  banned.forEach((e) => bannedSet.add(e));
  let result = wordArr.filter(Boolean).filter((x) => !bannedSet.has(x));
  let counter = (key) => (obj[key] = ++obj[key] || 1);
  result.forEach(counter);
  let topWordLength = Math.max(...Object.values(obj));
  let findMatch = (key) => obj[key] === topWordLength ? (mostCommon = key) : false;
  result.forEach(findMatch);
  return mostCommon
};
mostCommonWord("Bob hit a ball, the hit BALL ball flew far after it was hit.", ['hit']);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

1800. Maximum Ascending Subarray Sum

Given an array of positive integers nums, return the maximum possible sum of an ascending subarray in nums.

A subarray is defined as a contiguous sequence of numbers in an array.

A subarray [numsl, numsl+1, ..., numsr-1, numsr] is ascending if for all i where l <= i < r, numsi < numsi+1. Note that a subarray of size 1 is ascending.

Example 1:

Input: nums = [10,20,30,5,10,50]
Output: 65
Explanation: [5,10,50] is the ascending subarray with the maximum sum of 65.
Example 2:

Input: nums = [10,20,30,40,50]
Output: 150
Explanation: [10,20,30,40,50] is the ascending subarray with the maximum sum of 150.
Example 3:

Input: nums = [12,17,15,13,10,11,12]
Output: 33
Explanation: [10,11,12] is the ascending subarray with the maximum sum of 33.
Example 4:

Input: nums = [100,10,1]
Output: 100
 

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100
*/

/**************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var maxAscendingSum = function (nums) {
  let sum = 0;
  let count = [];
  for (let item = 0; item < nums.length; item++) {
    if (nums[item] < nums[item + 1] && sum >= nums[item] && nums[item] > nums[item - 1]) {
      sum += nums[item];
    } else if (nums[item] <= nums[item - 1] ||(nums[item] < nums[item + 1] && sum >= nums[item])
    ) {
      sum = nums[item];
    } else {
      sum += nums[item];
      count.push(sum);
    }
  }
  return Math.max(...count);
};

maxAscendingSum([12,17,15,13,10,11,12])

/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
1700. Number of Students Unable to Eat Lunch
Easy

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue's end.
This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i​​​​​​th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j​​​​​​th student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.


Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0 
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.
Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3
 

Constraints:

1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.
*/

/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var countStudents = function (students, sandwiches) {
  let shift = students.length * sandwiches.length;
  for (i = 0; i < shift; i++) {
    if (students[0] != sandwiches[0]) {
      students.push(students.splice(0, 1)[0]);
    } else {
      sandwiches.splice(0, 1);
      students.splice(0, 1);
    }
  }
  return students.length;
};
countStudents([0,0,0,1,1,1,1,0,0,0], [1,0,1,0,0,1,1,0,0,0]);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
1200. 
Difficulty: EASY
Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. 

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows
a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr
 

Example 1:
Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

Example 2:
Input: arr = [1,3,6,10,15]
Output: [[1,3]]

Example 3:
Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
 
Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6
*/
*/

/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

takes too long 
var minimumAbsDifference = function(arr) {
  let diff;
  let obj={};
  let pairs;
  arr.sort(function(a, b){return a-b}); 
for(let i=0; i<arr.length; i++){
  for(let j=i+1; j<arr.length; j++){
   diff=Math.abs(arr[i]-(arr[j]));
   obj[[arr[i], arr[j]]]=diff;
   if(i===0 && j===1){
     curr=diff
   }
    if(diff<curr){
      curr=diff
      }
}
}
    Object.keys(obj).forEach((key)=> obj[key]!=curr ? delete obj[key] : false);
   pairs = Array.from((Object.keys(obj)), e => e.split(','));
     let pairsNums = pairs.map((x) => x.map((y) => +y));
     return pairsNums
};

//minimumAbsDifference([1,3,6,10,15])
minimumAbsDifference([3,8,-10,23,19,-4,-14,27])
//minimumAbsDifference([4,2,1,3])

//actual answervar minimumAbsDifference = function (arr) {
  let diff;
  let curr;
  let newArr = [];
  arr.sort(function (a, b) {
    return a - b;
  });
  for (let i = 0; i < arr.length; i++) {
    diff = Math.abs(arr[i] - arr[i + 1]);
    if (i === 0) {
      curr = diff;
    }
    if (diff < curr) {
      curr = diff;
      newArr = [[arr[i], arr[i + 1]]];
    } else if (diff === curr) {
      newArr.push([arr[i], arr[i + 1]]);
    }
  }
  return newArr;
};

minimumAbsDifference([3,8,-10,23,19,-4,-14,27])

/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

/*28. Implement strStr()
Difficulty:Easy

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

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().

Example 1:
Input: haystack = "hello", needle = "ll" [he, o]
Output: 2

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

Example 3:
Input: haystack = "", needle = ""
Output: 0
 
Constraints: 0 <= haystack.length, needle.length <= 5 * 104
haystack and needle consist of only lower-case English characters.
*/


/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

var strStr = function(haystack, needle) {
    if(needle===''){return 0}
    if(!haystack.includes(needle)) return -1
    return haystack.split(needle)[0].length;
};
strStr("hello", 'll');
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
35. Search Insert Position
Easy
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0
Example 5:

Input: nums = [1], target = 0
Output: 0
 

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104
*/

/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var searchInsert = function (nums, target) {
  if (nums.includes(target)) {
    return nums.indexOf(target);
  } else {
    let bigger = nums.find((item) => item > target);
    if (bigger) {
      return nums.indexOf(bigger);
    } else {
      return nums.length;
    }
  }
};

searchInsert([1, 2, 5, 6], 3);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/*******************************************************************************/
53. Maximum Subarray

Difficulty: Easy
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:
Input: nums = [1]
Output: 1
Example 3:

Input: nums = [5,4,-1,7,8]

Output: 23
 
Constraints: 1 <= nums.length <= 3 * 104 -105 <= nums[i] <= 105
*/
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 


var maxSubArray = function(nums) {
    let maxSoFar = nums[0];
    let max = nums[0];
    
    for(let i = 1; i < nums.length; i++){
        let current = nums[i];
        maxSoFar = Math.max(0, current + maxSoFar);
        max = Math.max(max, maxSoFar);
    }
    return max;
};


var maxSubArray = function(nums) {
    let max = Number.MIN_SAFE_INTEGER;
    let sum = 0; 
    for(let i = 0; i <nums.length; i++){
       sum += nums[i];
       max = Math.max(max,sum);
       sum = sum < 0 ? 0 : sum;
    }
    return max;
};
maxSubArray([8,-19,5,-4,20]);/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

709. To Lower Case
EASY

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Example 1:
Input: "Hello"
Output: "hello"

Example 2:
Input: "here"
Output: "here"
Example 3:

Input: "LOVELY"
Output: "lovely"
*/
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var toLowerCase = function(str) {
   return str.toLowerCase();
};
toLowerCase("Hello");

/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
58. Length of Last Word
Easy
Given a string s consists of some words separated by spaces, return the length of the last word in the string. If the last word does not exist, return 0.

A word is a maximal substring consisting of non-space characters only.


Example 1:
Input: s = "Hello World"
Output: 5
Example 2:

Input: s = " "
Output: 0
 

Constraints:
1 <= s.length <= 104
s consists of only English letters and spaces ' '.*/

var lengthOfLastWord = function(s) {
    return s.trim().split(" ").pop().length;
};
lengthOfLastWord("hello world  ")
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*66. Plus One
Easy
Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer.
The digits are stored such that the most significant digit is at the head of the list, and each element in the array contains a single digit.
You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:
Input: digits = [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:
Input: digits = [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Example 3:
Input: digits = [0]
Output: [1]
 
Constraints: 1 <= digits.length <= 100 0 <= digits[i] <= 9*/

*/
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 


var plusOne = function (digits) {
    for (let i = digits.length - 1; i >= 0; i--) {
      switch (true) {
        case digits[i] != 9: digits[i]=digits[i] + 1; return digits;
        case i === 0:digits[i] = 1; digits.push(0);break;
        default:digits[i] = 0;
      }
    }
  return digits;
};
plusOne( [1,2,3]);

/* 
var plusOne = function (digits) {
  let isSafe = () => {
    digits = Array.from(String(+digits.join(“”) + 1), Number).map((x) => (x % 10 === 0 ? (“” + x).split(“”) : x)).flat().map((y) => +y);
  };
  let notSafe = () => {
    for (let i = digits.length - 1; i >= 0; i--) {
      switch (true) {
        case digits[i] != 9: digits[i]=digits[i] + 1; return;
        case i === 0:digits[i] = 1; digits.push(0);break;
        default:digits[i] = 0;
      }
    }
  };
  Number.isSafeInteger(+digits.join(“”)) ? isSafe() : notSafe();
  return digits;
};
plusOne([6,1,4,5,3,9,0,1,9,5,1,8,6,7,0,5,5,4,3]);

*/
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

/*
27. Remove Element
Easy
Given an array nums and a value val, remove all instances of that value in-place and return 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.The order of elements can be changed. It doesn't matter what you leave beyond the new length.

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 = removeElement(nums, val);

// 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 = [3,2,2,3], val = 3
Output: 2, nums = [2,2]
Explanation: Your function should return length = 2, with the first two elements of nums being 2.
It doesn't matter what you leave beyond the returned length. For example if you return 2 with nums = [2,2,3,3] or nums = [2,2,0,0], your answer will be accepted.
Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3]
Explanation: Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4. Note that the order of those five elements can be arbitrary. It doesn't matter what values are set beyond the returned length.
 
Constraints: 0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100
*/

*/
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var removeElement = function(nums, val) {
for(i=0; i<nums.length; i++){
  if(nums[i]===val){
    nums.splice(i, 1)
    i--;
}
}
return nums.length
};
removeElement([3,2,2,3], 2);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*1848. Minimum Distance to the Target Element
Easy
Given an integer array nums (0-indexed) and two integers target and start, find an index i such that nums[i] == target and abs(i - start) is minimized. Note that abs(x) is the absolute value of x.
Return abs(i - start).

It is guaranteed that target exists in nums.
Example 1:
Input: nums = [1,2,3,4,5], target = 5, start = 3
Output: 1
Explanation: nums[4] = 5 is the only value equal to target, so the answer is abs(4 - 3) = 1.

Example 2:
Input: nums = [1], target = 1, start = 0
Output: 0
Explanation: nums[0] = 1 is the only value equal to target, so the answer is abs(0 - 0) = 0.

Example 3:
Input: nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
Output: 0
Explanation: Every value of nums is 1, but nums[0] minimizes abs(i - start), which is abs(0 - 0) = 0.
 

Constraints: 1 <= nums.length <= 1000 1 <= nums[i] <= 104 0 <= start < nums.length
target is in nums.
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
*/
var getMinDistance = function(nums, target, start) {
  let mySet = new Set();
  nums.forEach((x)=> x===start | x===target ? mySet.add(x): false);
  console.log(mySet)
};
getMinDistance([1,2,3,4,5], 5, 3)
//x===target mySet.add(x)
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
67. Add Binary
Easy
Given two binary strings a and b, return their sum as a binary string.

Example 1:
Input: a = "11", b = "1"
Output: "100"

Example 2:
Input: a = "1010", b = "1011"
Output: "10101"

Constraints: 1 <= a.length, b.length <= 104
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.*/
//1100100

/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var addBinary = function(a, b) {
  const aBin = `0b${a}`;
  const bBin = `0b${b}`;
  const sum = BigInt(aBin) + BigInt(bBin)
  return sum.toString(2)
};

addBinary('11', '1')
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/* 
69. Sqrt(x)
Given a non-negative integer x, compute and return the square root of x.
Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.


Example 1:
Input: x = 4
Output: 2

Example 2:
Input: x = 8
Output: 2

Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.


Constraints: 0 <= x <= 231 - 1
    */
    
var mySqrt = function(x) {
  let sqrt = Math.sqrt(x);
  let whole = Math.floor(sqrt)
  return whole
};

mySqrt(4)



var mySqrt2 = function(x) {
  return Math.floor(x ** 0.5);
};
mySqrt2(6)
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

70. Climbing Stairs
Easy
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways t

o climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
 
Constraints: 1 <= n <= 45 */


/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
var climbStairs = function(n) {
if (n === 1) return 1
if (n === 0) return 0

    let one =1;
    let two=2;
    let add;
    
    for (let i = 3; i <= n; i++) {
      add = one + two;
      one = two;
      two = add;
    }

    return two
};


climbStairs(0);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/

/*

83. Remove Duplicates from Sorted List
Easy
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Example 1:
Input: head = [1,1,2]
Output: [1,2]

Example 2:
Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:
The number of nodes in the list is in the range [0, 300].
-100 <= Node.val <= 100
The list is guaranteed to be sorted in ascending order. */

/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

/****ANSWER THAT ONLY WORKS ON REPL??? ***/
var deleteDuplicates = function(head) {
for(i=0; i<head.length; i++){
  if(head[i]===head[i+1]){
    head.splice(i, 1)
    i--;
}
}
return head
};
deleteDuplicates( [1,1,2,3,3]);
/****ANSWER THAT ONLY WORKS ON LEETCODE?? */
var deleteDuplicates = function(head) {
  if(!head || !head.next) return head;
  head.next = deleteDuplicates(head.next);
  return head.val == head.next.val ? head.next : head;
};
deleteDuplicates( [1,1,2,3,3]);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*
/*88. Merge Sorted Array
Easy

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.


/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1] 
*/

const merge = (nums1, m, nums2, n) => {
  for (let i = nums2.length - 1; i >= 0; i--) {
    nums1.unshift(nums2[i])
    nums1.pop()
  }

  nums1.sort((a, b) => a - b)
  return nums1
}
//merge([1,2,3,0,0,0], 3, [2,5,6], 3)
//merge([1], 1, [], 0);

merge([0], 0, [1], 1);
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*94. Binary Tree Inorder Traversal
Easy
Given the root of a binary tree, return the inorder traversal of its nodes' values.

Example 1:
Input: root = [1,null,2,3]
Output: [1,3,2]
Example 2:

Input: root = []
Output: []
Example 3:

Input: root = [1]
Output: [1] */
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 
const inorderTraversal = root => {
  if (!root) {
    return []
  }

  const values = []

  const traverse = (node) => {
    if (node !== null) {
      traverse(node.left)
      values.push(node.val)
      traverse(node.right)
    }
  }

  traverse(root)

  return values
}
inorderTraversal([1,null,2,3])
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/
/*118. Pascal's Triangle
Easy

Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:
Input: numRows = 1
Output: [[1]]
 

Constraints: 1 <= numRows <= 30 */
/*let triangle = [[1], [1,1],[1, 2,1], [1, 3, 3,1], [1, 4, 6, 4,1], [1, 5, 10,10, 5, 1] ];*/
/*************************************************************************************/
/************************************ANSWER********************************************/
/***********************************************************************************/ 

var generate = function(numRows) {
  let pascal = [];
  for (let i = 0; i < numRows; i++) {
  pascal[i] = [];
  pascal[i][0] = 1;
  pascal[i][pascal.length-1] = 1;

  for (let j = 1; j < i; j++) {
    pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j];
  }
}
  return pascal 
};
/**************************************************************************************/
/*************************************QUESTION********************************************/
/***********************************************************************************/