Leetcode done by mimanjh

/* 
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

EX)
Input: nums = [3,2,4], target = 6
Output: [1,2]
*/

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
 var twoSum = function(nums, target) {
    if (nums.length == 2) {
        return ([0, 1])
    }
    
    hashTable = {}
    
    for (var i = 0; i < nums.length; i++) {
        var val = target - nums[i]
        
        if (val in hashTable) {
            if (i > hashTable[val]) {
                return ([hashTable[val], i])
            } else {
                return ([i, hashTable[val]])
            }
        }
        
        hashTable[nums[i]] = i
    }
};

# 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.


class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numsMap = {}

        for i, num in enumerate(nums):
            diff = target - num

            if diff in numsMap:
                return [numsMap[diff], i]

            numsMap[num] = i

        return None


print(Solution().twoSum([2, 7, 11, 15], 9))  # [0,1]
print(Solution().twoSum([3, 2, 4], 6))  # [1,2]
print(Solution().twoSum([3, 3], 6))  # [0,1]

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

EX
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
*/


/**
 * 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) {
    // set default variables
    let dummyHead = new ListNode(0);
    let p1 = l1;
    let p2 = l2;
    let current = dummyHead;
    let carry = 0;
    
    while (p1 !== null || p2 !== null) {
        let x = (p1 !== null) ? p1.val : 0;
        let y = (p2 !== null) ? p2.val : 0;
        let sum = x + y + carry;
        
        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;
        
        if (p1 !== null) {
            p1 = p1.next;
        }
        if (p2 !== null) {
            p2 = p2.next;
        }
    }
    if (carry > 0) {
        current.next = new ListNode(1);
    }
    return dummyHead.next;
};

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

 

# Example 1:

# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with the length of 3.
# Example 2:

# Input: s = "bbbbb"
# Output: 1
# Explanation: The answer is "b", with the length of 1.
# Example 3:

# Input: s = "pwwkew"
# Output: 3
# Explanation: The answer is "wke", with the length of 3.
# Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 

# Constraints:

# 0 <= s.length <= 5 * 104
# s consists of English letters, digits, symbols and spaces.
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # use sliding window algorithm
        # use set instead of a list to store the unique substring of character and reduce complexity to O(1) instead of O(n)
        # use two pointer to indicate the start and end of the substring (left and right)
        # use max to store the max length of the substring
        charSet = set()
        left = 0
        result = 0

        for right in range(len(s)):
            while s[right] in charSet:
                charSet.remove(s[left])
                left += 1
            charSet.add(s[right])
            result = max(result, right - left + 1)
        return result
    

        # Other solution from leetcode using sliding window algorithm as well
        # left = 0
        # seen = {}
        # output = 0
        
        # for right, curr in enumerate(s):
        #     if curr in seen:
        #         left = max(left, seen[curr] + 1)
        #     output = max(output, right - left + 1)
        #     seen[curr] = right

        # return output


print(Solution().lengthOfLongestSubstring("abcabcbb")) # 3
print(Solution().lengthOfLongestSubstring("bbbbb")) # 1
print(Solution().lengthOfLongestSubstring("pwwkew")) # 3
print(Solution().lengthOfLongestSubstring("")) # 0
print(Solution().lengthOfLongestSubstring(" ")) # 1
print(Solution().lengthOfLongestSubstring("aab")) # 2
print(Solution().lengthOfLongestSubstring("cdd")) # 2

# Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

# The overall run time complexity should be O(log (m+n)).

# Example 1:

# Input: nums1 = [1,3], nums2 = [2]
# Output: 2.00000
# Explanation: merged array = [1,2,3] and median is 2.
# Example 2:

# Input: nums1 = [1,2], nums2 = [3,4]
# Output: 2.50000
# Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.


# Constraints:

# nums1.length == m
# nums2.length == n
# 0 <= m <= 1000
# 0 <= n <= 1000
# 1 <= m + n <= 2000
# -106 <= nums1[i], nums2[i] <= 106


class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        # Merge the two lists
        merged = sorted(nums1 + nums2)

        # Find the median
        length = len(merged)
        if length % 2 == 0:
            return (merged[length // 2 - 1] + merged[length // 2]) / 2.0
        else:
            return merged[length // 2]


print(Solution().findMedianSortedArrays([1, 3], [2]))  # 2.00000
print(Solution().findMedianSortedArrays([1, 2], [3, 4]))  # 2.50000

# Given a string s, return the longest 
# palindromic
 
# substring
#  in s.

 

# Example 1:

# Input: s = "babad"
# Output: "bab"
# Explanation: "aba" is also a valid answer.
# Example 2:

# Input: s = "cbbd"
# Output: "bb"
 

# Constraints:

# 1 <= s.length <= 1000
# s consist of only digits and English letters.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        result = ""
        # go through each character in the string
        # for each character, check if it is the middle of the palindrome
        # if it is, then check if the left and right are the same
        # use max to store the longest palindrome
        for i in range(len(s)):
            result = max(result, self.helper(s, i, i), self.helper(s, i, i+1), key=len)
        return result
        
    def helper(self, s, i, j):
        # i and j are the middle index of the substring
        # palindrome logic: if the left and right are the same, then it is a palindrome
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return s[i+1:j]
        

print(Solution().longestPalindrome("babad")) # "bab"
print(Solution().longestPalindrome("cbbd")) # "bb"
print(Solution().longestPalindrome("a")) # "a"
print(Solution().longestPalindrome("ac")) # "a"
print(Solution().longestPalindrome("ccc")) # "ccc"
print(Solution().longestPalindrome("aacabdkacaa")) # "aca"

# 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
 

# Constraints:

# -231 <= x <= 231 - 1

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        # # using string manipulation
        # # convert the number to a string and reverse it, then convert back to an integer
        # # if the number is negative, we'll need to add the negative sign back in
        # reversedX = int(str(abs(x))[::-1])
        # if reversedX.bit_length() < 32:
        #     return reversedX if x >= 0 else -reversedX
        # return 0

        # using integer division and modulo
        # dealing with negative numbers is a bit tricky, so we'll convert to positive
        # and then add the sign back in at the end
        # we'll use the modulo operator to get the last digit of the number
        # and then we'll multiply the current value by 10 and add the last digit
        # ex) 123 % 10 = 3, 0 * 10 + 3 = 3
        # ex) 12 % 10 = 2, 3 * 10 + 2 = 32
        # ex) 1 % 10 = 1, 32 * 10 + 1 = 321
        reversedX = 0
        sign = 1
        if x < 0:
            sign = -1
            x = -x
        while x:
            lastDigit = x % 10
            reversedX = reversedX * 10 + lastDigit
            x //= 10
        # since this is a 32-bit integer, we need to check its boundaries
        return 0 if reversedX.bit_length() > 31 else reversedX * sign
        

print(Solution().reverse(123)) # 321
print(Solution().reverse(-123)) # -321
print(Solution().reverse(120)) # 21
print(Solution().reverse(1534236469)) # 0
print(Solution().reverse(1563847412)) # 0

# Given an integer x, return true if x is a palindrome, and false otherwise.

# Example 1:

# Input: x = 121
# Output: true
# Explanation: 121 reads as 121 from left to right and from right to left.
# 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.
 

# Constraints:
# -231 <= x <= 231 - 1

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0 or (x != 0 and x%10 == 0):
            return False
        
        return str(x) == str(x)[::-1]
        
print(Solution().isPalindrome(121)) #true
print(Solution().isPalindrome(-121)) #false
print(Solution().isPalindrome(120011)) #false

# 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 an integer, convert it to a roman numeral.

# Example 1:

# Input: num = 3
# Output: "III"
# Explanation: 3 is represented as 3 ones.
# Example 2:

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

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

# 1 <= num <= 3999

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
            
        roman = ''
        roman_dict = {
            1000: 'M',
            900: 'CM',
            500: 'D',
            400: 'CD', 
            100: 'C',
            90: 'XC',
            50: 'L',
            40: 'XL', 
            10: 'X',
            9: 'IX',
            5: 'V',
            4: 'IV', 
            1: 'I'
        }
        
        for key in roman_dict:
            while num >= key:
                roman += roman_dict[key]
                num -= key
        
        return roman
        

print(Solution().intToRoman(3)) # "III"
print(Solution().intToRoman(58)) # "LVIII"
print(Solution().intToRoman(1994)) # "MCMXCIV"

# 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 ones 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
# Explanation: III = 3.
# Example 2:

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

# 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].

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        # create a variable to hold the total
        total = 0;
        # for every character in the string s, add an equivalent integer to the total
        for i in range(len(s)):
            if s[i] == 'I':
                total += 1;
            elif s[i] == 'V':
                total += 5;
            elif s[i] == 'X':
                total += 10;
            elif s[i] == 'L':
                total += 50;
            elif s[i] == 'C':
                total += 100;
            elif s[i] == 'D':
                total += 500;
            elif s[i] == 'M':
                total += 1000;
        # if the string contains IV, IX, XL, XC, CD, or CM, subtract the value of the first character from the total
        if 'IV' in s:
            total -= 2;
        if 'IX' in s:
            total -= 2;
        if 'XL' in s:
            total -= 20;
        if 'XC' in s:
            total -= 20;
        if 'CD' in s:
            total -= 200;
        if 'CM' in s:
            total -= 200;
        
        return total;

print(Solution().romanToInt("III")); # 3
print(Solution().romanToInt("LVIII")); # 58
print(Solution().romanToInt("MCMXCIV")); # 1994

# 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 lowercase English letters.

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if not len(strs):
            return ''
        
        l = list(zip(*strs))
        prefix = ""
        for i in l:
            if len(set(i))==1:
                prefix += i[0]
            else:
                break
        return prefix

print(Solution().longestCommonPrefix(["flower","flow","flight"])); # "fl"
print(Solution().longestCommonPrefix(["dog","racecar","car"])); # ""
print(Solution().longestCommonPrefix(["ab","a"])); # "a"

# Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

# Notice that the solution set must not contain duplicate triplets.
# Example 1:

# Input: nums = [-1,0,1,2,-1,-4]
# Output: [[-1,-1,2],[-1,0,1]]
# Explanation: 
# nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
# nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
# nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
# The distinct triplets are [-1,0,1] and [-1,-1,2].
# Notice that the order of the output and the order of the triplets does not matter.
# Example 2:

# Input: nums = [0,1,1]
# Output: []
# Explanation: The only possible triplet does not sum up to 0.
# Example 3:

# Input: nums = [0,0,0]
# Output: [[0,0,0]]
# Explanation: The only possible triplet sums up to 0.
 
# Constraints:

# 3 <= nums.length <= 3000
# -105 <= nums[i] <= 105
from itertools import combinations


class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = set()
        # Split nums into three lists: negative numbers, positive numbers, and zeros
        negative, positive, zero = [], [], []
        for num in nums:
            if num > 0:
                positive.append(num)
            elif num < 0: 
                negative.append(num)
            else:
                zero.append(num)

        # Create a separate set for negatives and positives for O(1) look-up times
        N, P = set(negative), set(positive)

        # If there are at least 3 zeros in the list then also include (0, 0, 0) = 0
        if zero:
            for num in P:
                if -1*num in N:
                    res.add((-1*num, 0, num))
            if len(zero) >= 3:
                res.add(tuple([0, 0, 0]))

        # For all pairs of negative numbers (-3, -1), check to see if their complement (4) exists in the positive number set
        for x, y in combinations(negative, 2):
            target = -1 * (x + y)
            if target in P:
                res.add(tuple(sorted([x, y, target])))
        # For all pairs of positive numbers (1, 1), check to see if their complement (-2) exists in the negative number set
        for x, y in combinations(positive, 2):
            target = -1 * (x + y)
            if target in N:
                res.add(tuple(sorted([x, y, target])))

        return [list(x) for x in res]

        

print(Solution().threeSum([-1,0,1,2,-1,-4])) # [[-1,-1,2],[-1,0,1]]
print(Solution().threeSum([0,1,1])) # []
print(Solution().threeSum([0,0,0])) # [[0,0,0]]

# Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

# A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

# Example 1:

# Input: digits = "23"
# Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
# Example 2:

# Input: digits = ""
# Output: []
# Example 3:

# Input: digits = "2"
# Output: ["a","b","c"]
 
# Constraints:

# 0 <= digits.length <= 4
# digits[i] is a digit in the range ['2', '9'].

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        # backtracking
        letters = {
            '2': ['a','b','c'],
            '3': ['d','e','f'],
            '4': ['g','h','i'],
            '5': ['j','k','l'],
            '6': ['m','n','o'],
            '7': ['p','q','r','s'],
            '8': ['t','u','v'],
            '9': ['w','x','y','z'],
        }
        result = [''] if digits else []

        # go through each digits and append each of the letters to the result
        for digit in digits:
            result = [a + b for a in result for b in letters[digit]]
        return result
    
    # a different method using recursion
    # # dictionary of letters
    #     letters = {
    #         '2': ['a','b','c'],
    #         '3': ['d','e','f'],
    #         '4': ['g','h','i'],
    #         '5': ['j','k','l'],
    #         '6': ['m','n','o'],
    #         '7': ['p','q','r','s'],
    #         '8': ['t','u','v'],
    #         '9': ['w','x','y','z'],
    #     }
    #     result = []
    #     # if digits is empty, return empty list
    #     if not digits:
    #         return []
    #     # if digits is one digit, return the letter combinations of that digit
    #     if len(digits) == 1:
    #         return letters[digits]
    #     # otherwise, go through each digit and call the function combine to append each of the letters
    #     for digit in digits:
    #         result = self.combine(result, letters[digit])
    #     return result
    
    # def combine(self, result, letters):
    #     """
    #     :type result: List[str]
    #     :type letters: List[str]
    #     :rtype: List[str]
    #     """
    #     # if result is empty, return letters
    #     if not result:
    #         return letters
    #     # otherwise, go through each letter in letters and append it to each of the strings in result
    #     new_result = []
    #     for letter in letters:
    #         for string in result:
    #             new_result.append(string + letter)
    #     return new_result
        

print(Solution().letterCombinations("23")) # ["ad","ae","af","bd","be","bf","cd","ce","cf"]
print(Solution().letterCombinations("")) # []
print(Solution().letterCombinations("2")) # ["a","b","c"]
print(Solution().letterCombinations("7")) # ["p","q","r","s"]
print(Solution().letterCombinations("234")) # ["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]

# 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.
# Every close bracket has a corresponding open bracket of the same type.
 

# Example 1:

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

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

# Input: s = "(]"
# Output: false
 

# Constraints:

# 1 <= s.length <= 104
# s consists of parentheses only '()[]{}'.
        
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        # check if the length of the string is odd
        # if so, return false
        if len(s) % 2 != 0 or len(s) == 0:
            return False
        
        # create a mapping of parentheses
        bracketMapping = {'(': ')', '[': ']', '{': '}'}
        resultString = ""

        # iterate through the string 
        for char in s:
            # if the character is an open bracket, add the corresponding closing bracket to the resultString
            if char in bracketMapping:
                resultString += bracketMapping[char]
            # if the character is a closing bracket, and the resultString is empty or the last character in the resultString is not the same as the current character, return false
            elif len(resultString) == 0 or resultString[-1] != char:
                return False
            # else, remove the last character from the resultString
            else:
                resultString = resultString[:-1]
        
        # if the resultString is empty, return true
        if len(resultString) == 0:
            return True
        
        # else, return false
        return False

print(Solution().isValid("()")); # true 
print(Solution().isValid("()[]{}")); # true
print(Solution().isValid("(]")); # false
print(Solution().isValid("([)]")); # false
print(Solution().isValid("{[]}")); # true

# You are given the heads of two sorted linked lists list1 and list2.

# Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

# Return the head of the merged linked list.

 

# Example 1:


# Input: list1 = [1,2,4], list2 = [1,3,4]
# Output: [1,1,2,3,4,4]
# Example 2:

# Input: list1 = [], list2 = []
# Output: []
# Example 3:

# Input: list1 = [], list2 = [0]
# Output: [0]
 

# Constraints:

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

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        # iterative solution
        dummy = cur = ListNode(0)
        # loop through both lists, comparing the elements of each list one by one until one reaches the end
        # add the smaller element to cur
        while list1 != None and list2 != None:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            # move cur to the next node
            cur = cur.next
        # add the rest of whichever list is not None to cur
        cur.next = list1 or list2
        return dummy.next

        # # loop through recursively, comparing the first elements of each list
        # # running recursively here is not a good idea, because it will take up too much memory
        # if not list1 or not list2:
        #     return list1 or list2
        # if list1.val < list2.val:
        #     list1.next = self.mergeTwoLists(list1.next, list2)
        #     return list1
        # else:
        #     list2.next = self.mergeTwoLists(list1, list2.next)
        #     return list2

lst1 = ListNode(1)
lst1.next = ListNode(2)
lst1.next.next = ListNode(4)
lst2 = ListNode(1)
lst2.next = ListNode(3)
lst2.next.next = ListNode(4)
merged_list = Solution().mergeTwoLists(lst1, lst2)
while merged_list:
    print(str(merged_list.val), end = ' -> ')
    merged_list = merged_list.next
print(merged_list) # [1,1,2,3,4,4]

# Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

# Example 1:

# Input: n = 3
# Output: ["((()))","(()())","(())()","()(())","()()()"]
# Example 2:

# Input: n = 1
# Output: ["()"]
 
# Constraints:

# 1 <= n <= 8

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        # Depth First Search
        result = []
        self.dfs(result, '', 0, 0, n)
        return result
    
    def dfs(self, result, current, open, close, max):
        # base case
        if len(current) == max * 2:
            result.append(current)
            return
        # recursive case
        if open < max:
            self.dfs(result, current + '(', open + 1, close, max)
        if close < open:
            self.dfs(result, current + ')', open, close + 1, max)
        

print(Solution().generateParenthesis(3)) # ["((()))","(()())","(())()","()(())","()()()"]
print(Solution().generateParenthesis(1)) # ["()"]
print(Solution().generateParenthesis(0)) # []
print(Solution().generateParenthesis(4)) # ["(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"]

# Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

# Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

# Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
# Return k.
# Custom Judge:

# The judge will test your solution with the following code:

# int[] nums = [...]; // Input array
# int[] expectedNums = [...]; // The expected answer with correct length

# int k = removeDuplicates(nums); // Calls your implementation

# assert k == expectedNums.length;
# for (int i = 0; i < k; i++) {
#     assert nums[i] == expectedNums[i];
# }
# If all assertions pass, then your solution will be accepted.

 

# Example 1:

# Input: nums = [1,1,2]
# Output: 2, nums = [1,2,_]
# Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
# It does not matter what you leave beyond the returned k (hence they are underscores).
# 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 k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
# It does not matter what you leave beyond the returned k (hence they are underscores).
 

# Constraints:

# 1 <= nums.length <= 3 * 104
# -100 <= nums[i] <= 100
# nums is sorted in non-decreasing order.

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # for every value in nums, loop through each from the back 
        # and check if the one before
        # each value is the same as the current value
        # if it is, remove it and continue
        # return the length of nums

        # for i in range(len(nums)-1, 0, -1):
        #     if nums[i] == nums[i-1]:
        #         nums.pop(i)

        # solution with better memory consumption with similar runtime
        nums[:] = sorted(set(nums))

        return len(nums)
    
print(Solution().removeDuplicates([1,1,2])) # 2
print(Solution().removeDuplicates([0,0,1,1,1,2,2,3,3,4])) # 5
        

# Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

# Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

# Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
# Return k.
# Custom Judge:

# The judge will test your solution with the following code:

# int[] nums = [...]; // Input array
# int val = ...; // Value to remove
# int[] expectedNums = [...]; // The expected answer with correct length.
#                             // It is sorted with no values equaling val.

# int k = removeElement(nums, val); // Calls your implementation

# assert k == expectedNums.length;
# sort(nums, 0, k); // Sort the first k elements of nums
# for (int i = 0; i < actualLength; i++) {
#     assert nums[i] == expectedNums[i];
# }
# If all assertions pass, then your solution will be accepted.

 

# Example 1:

# Input: nums = [3,2,2,3], val = 3
# Output: 2, nums = [2,2,_,_]
# Explanation: Your function should return k = 2, with the first two elements of nums being 2.
# It does not matter what you leave beyond the returned k (hence they are underscores).
# 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 k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
# Note that the five elements can be returned in any order.
# It does not matter what you leave beyond the returned k (hence they are underscores).
 

# Constraints:

# 0 <= nums.length <= 100
# 0 <= nums[i] <= 50
# 0 <= val <= 100

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        # since it's in-place, we can't use extra space or new array
        # if we can use extra space, len([x for x in nums if x != val]) would be a quick short solution
        # we'll go through the array from the end, and pop the element if it's equal to val
        for i in reversed(range(len(nums))):
            if nums[i] == val:
                nums.pop(i)
        return len(nums);


print(Solution().removeElement([3,2,2,3], 3)) # 2
print(Solution().removeElement([0,1,2,2,3,0,4,2], 2)) # 5

# Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

# Example 1:

# Input: haystack = "sadbutsad", needle = "sad"
# Output: 0
# Explanation: "sad" occurs at index 0 and 6.
# The first occurrence is at index 0, so we return 0.
# Example 2:

# Input: haystack = "leetcode", needle = "leeto"
# Output: -1
# Explanation: "leeto" did not occur in "leetcode", so we return -1.
 

# Constraints:

# 1 <= haystack.length, needle.length <= 104
# haystack and needle consist of only lowercase English characters.

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not needle:
            return 0 
        if needle in haystack:
            return haystack.index(needle)
        else:
            return -1
            
print(Solution().strStr("sadbutsad", "sad")); # 0
print(Solution().strStr("leetcode", "leeto")); # -1
print(Solution().strStr("hello", "ll")); # 2

# Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

# The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

# Return the quotient after dividing dividend by divisor.

# Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

# Example 1:

# Input: dividend = 10, divisor = 3
# Output: 3
# Explanation: 10/3 = 3.33333.. which is truncated to 3.
# Example 2:

# Input: dividend = 7, divisor = -3
# Output: -2
# Explanation: 7/-3 = -2.33333.. which is truncated to -2.
 
# Constraints:

# -2^31 <= dividend, divisor <= 2^31 - 1
# divisor != 0

class Solution(object):
    def divide(self, dividend, divisor):
        """
        :type dividend: int
        :type divisor: int
        :rtype: int
        """
        # set the sign of the result
        sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1
        # remove the sign of the dividend and divisor
        dividend, divisor = abs(dividend), abs(divisor)
        # initialize the quotient
        quotient = 0
        # loop until the dividend is greater than the divisor
        while dividend >= divisor:
            # initialize the temp_divisor variable
            temp_divisor = divisor
            # initialize the multiplier
            multiplier = 1
            # loop until the temp_divisor is less than the dividend
            while temp_divisor <= dividend:
                # update the dividend
                dividend -= temp_divisor
                # update the quotient
                quotient += multiplier
                # update the temp_divisor
                temp_divisor += temp_divisor
                # update the multiplier
                multiplier += multiplier
        # return the result and constrain it to the 32-bit signed integer range
        return min(max(-2**31, sign * quotient), 2**31 - 1)
        

print(Solution().divide(10, 3)) # 3
print(Solution().divide(7, -3)) # -2
print(Solution().divide(0, 1)) # 0
print(Solution().divide(3968492, 6)) # 661415

# Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

# Each row must contain the digits 1-9 without repetition.
# Each column must contain the digits 1-9 without repetition.
# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
# Note:
# A Sudoku board (partially filled) could be valid but is not necessarily solvable.
# Only the filled cells need to be validated according to the mentioned rules.

# Example 1:


# Input: board =
# [["5","3",".",".","7",".",".",".","."]
# ,["6",".",".","1","9","5",".",".","."]
# ,[".","9","8",".",".",".",".","6","."]
# ,["8",".",".",".","6",".",".",".","3"]
# ,["4",".",".","8",".","3",".",".","1"]
# ,["7",".",".",".","2",".",".",".","6"]
# ,[".","6",".",".",".",".","2","8","."]
# ,[".",".",".","4","1","9",".",".","5"]
# ,[".",".",".",".","8",".",".","7","9"]]
# Output: true
# Example 2:

# Input: board =
# [["8","3",".",".","7",".",".",".","."]
# ,["6",".",".","1","9","5",".",".","."]
# ,[".","9","8",".",".",".",".","6","."]
# ,["8",".",".",".","6",".",".",".","3"]
# ,["4",".",".","8",".","3",".",".","1"]
# ,["7",".",".",".","2",".",".",".","6"]
# ,[".","6",".",".",".",".","2","8","."]
# ,[".",".",".","4","1","9",".",".","5"]
# ,[".",".",".",".","8",".",".","7","9"]]
# Output: false
# Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.


# Constraints:

# board.length == 9
# board[i].length == 9
# board[i][j] is a digit 1-9 or '.'.


class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """

        # check if rows are valid
        for row in board:
            if not self.isValid(row):
                return False
        # check if columns are valid
        for col in zip(*board):
            if not self.isValid(col):
                return False
        # check if sub-boxes are valid
        for i in range(0, 9, 3):
            for j in range(0, 9, 3):
                sub_box = [
                    board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)
                ]
                if not self.isValid(sub_box):
                    return False
        return True

    def isValid(self, nums):
        # check if nums is consisted of 1-9 and has repetition
        nums = [x for x in nums if x != "."]
        return len(nums) == len(set(nums))


print(
    Solution().isValidSudoku(
        [
            ["5", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
        ]
    )
)  # True
print(
    Solution().isValidSudoku(
        [
            ["8", "3", ".", ".", "7", ".", ".", ".", "."],
            ["6", ".", ".", "1", "9", "5", ".", ".", "."],
            [".", "9", "8", ".", ".", ".", ".", "6", "."],
            ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
            ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
            ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
            [".", "6", ".", ".", ".", ".", "2", "8", "."],
            [".", ".", ".", "4", "1", "9", ".", ".", "5"],
            [".", ".", ".", ".", "8", ".", ".", "7", "9"],
        ]
    )
)  # False

# You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

# You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

# Example 1:

# Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
# Output: [[7,4,1],[8,5,2],[9,6,3]]
# Example 2:

# Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
# Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 

# Constraints:

# n == matrix.length == matrix[i].length
# 1 <= n <= 20
# -1000 <= matrix[i][j] <= 1000
class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        
        # transpose the matrix and then reverse each row
        n = len(matrix)
        for i in range(n):
            for j in range(i,n):
                matrix[j][i],matrix[i][j] = matrix[i][j],matrix[j][i]
        for i in range(n):
            matrix[i].reverse()
        return matrix

print(Solution().rotate([[1,2,3],[4,5,6],[7,8,9]])) #[[7,4,1],[8,5,2],[9,6,3]]
print(Solution().rotate([[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]])) #[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

# Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

# Example 1:

# Input: x = 2.00000, n = 10
# Output: 1024.00000
# Example 2:

# Input: x = 2.10000, n = 3
# Output: 9.26100
# Example 3:

# Input: x = 2.00000, n = -2
# Output: 0.25000
# Explanation: 2-2 = 1/22 = 1/4 = 0.25
 

# Constraints:

# -100.0 < x < 100.0
# -231 <= n <= 231-1
# n is an integer.
# Either x is not zero or n > 0.
# -104 <= xn <= 104

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        # exponentiation algorithm using divide and conquer approach
        if not n:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        if n % 2:
            return x * self.myPow(x, n - 1)
        return self.myPow(x * x, n / 2)
    
print(Solution().myPow(2.00000, 10)) # 1024.00000
print(Solution().myPow(2.10000, 3)) # 9.26100
print(Solution().myPow(2.00000, -2)) # 0.25000

# Given a string s consisting of words and spaces, return the length of the last word in the string.

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

# Example 1:

# Input: s = "Hello World"
# Output: 5
# Explanation: The last word is "World" with length 5.
# Example 2:

# Input: s = "   fly me   to   the moon  "
# Output: 4
# Explanation: The last word is "moon" with length 4.
# Example 3:

# Input: s = "luffy is still joyboy"
# Output: 6
# Explanation: The last word is "joyboy" with length 6.
 
# Constraints:

# 1 <= s.length <= 104
# s consists of only English letters and spaces ' '.
# There will be at least one word in s.

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        # Split the string by space
        # Get the last word
        # Return the length of the last word
        return len(s.split()[-1])
        
        
        

print(Solution().lengthOfLastWord("Hello World")); # 5
print(Solution().lengthOfLastWord("   fly me   to   the moon  ")); # 4
print(Solution().lengthOfLastWord("luffy is still joyboy")); # 6

# You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

# Increment the large integer by one and return the resulting array of digits.

# Example 1:

# Input: digits = [1,2,3]
# Output: [1,2,4]
# Explanation: The array represents the integer 123.
# Incrementing by one gives 123 + 1 = 124.
# Thus, the result should be [1,2,4].
# Example 2:

# Input: digits = [4,3,2,1]
# Output: [4,3,2,2]
# Explanation: The array represents the integer 4321.
# Incrementing by one gives 4321 + 1 = 4322.
# Thus, the result should be [4,3,2,2].
# Example 3:

# Input: digits = [9]
# Output: [1,0]
# Explanation: The array represents the integer 9.
# Incrementing by one gives 9 + 1 = 10.
# Thus, the result should be [1,0].


# Constraints:


# 1 <= digits.length <= 100
# 0 <= digits[i] <= 9
# digits does not contain any leading 0's.


class Solution(object):
    def plusOne(self, digits):
        """
        :type digits: List[int]
        :rtype: List[int]
        """
        # join each value in the list and convert to int and add 1
        int_val = int("".join(map(str, digits))) + 1
        # splilt each value in the int and store in a list and return it
        return [int(x) for x in str(int_val)]


print(Solution().plusOne([1, 2, 3]))  # [1,2,4]
print(Solution().plusOne([4, 3, 2, 1]))  # [4,3,2,2]
print(Solution().plusOne([9]))  # [1,0]

# 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.

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        # binary addition rule: 0+0=0, 0+1=1, 1+1=0 carry 1
        # go from right to left of each string
        # add the digits and keep track of carry
        # append the sum%2 to result
        # append carry to result
        # reverse the result and return it
        result = ""
        carry = 0
        i = len(a)-1
        j = len(b)-1
        while i >= 0 or j >= 0 or carry:
            if i >= 0:
                carry += int(a[i])
                i -= 1

            if j >= 0:
                carry += int(b[j])
                j -= 1

            result += str(carry%2)
            carry //= 2

        return result[::-1]

        

print(Solution().addBinary("11", "1")) # "100"
print(Solution().addBinary("1010", "1011")) # "10101"

# Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

# You must not use any built-in exponent function or operator.

# For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
 

# Example 1:

# Input: x = 4
# Output: 2
# Explanation: The square root of 4 is 2, so we return 2.
# Example 2:

# Input: x = 8
# Output: 2
# Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
 

# Constraints:

# 0 <= x <= 231 - 1

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if (x == 0):
            return 0
        res = x
        while not res * res - x < 1:
            res = (res + x / res) / 2
        return int(res)
        

    #     # use binary search using recursion
    #     left, right = 1, x
    #     return self.binarySearch(x, left, right)
    # def binarySearch(self, x, left, right):
    #     if (left <= right):
    #         mid = (left + right) // 2
    #         if (mid * mid <= x < (mid + 1) * (mid + 1)):
    #             return mid
    #         elif (mid * mid < x):
    #             return self.binarySearch(x, mid + 1, right)
    #         else:
    #             return self.binarySearch(x, left, mid - 1)
    #     else:
    #         return right


        # left = 1
        # right = x
        # while (left <= right):
        #     mid = (left + right) // 2
        #     if (mid * mid == x):
        #         return mid
        #     elif (mid * mid < x):
        #         left = mid + 1
        #     else:
        #         right = mid - 1



print(Solution().mySqrt(4)) # 2
print(Solution().mySqrt(8)) # 2
print(Solution().mySqrt(9)) # 3