[LeetCode] 15. 3Sum

Problem : https://leetcode.com/problems/3sum/

Sort the input number array first. Then iterate the number array to pick up the number 'a'.  After that use 2 pointers algorithm to locate the number 'b' and 'c' which meet the equation  b + c = 0 - a

Time Complexity :   O ( len(nums) * len(nums) /  2) 

Space Complexity:   O ( len(nums) ) 

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        # sort input numbers
        nums.sort()
        
        L = len(nums)
        result = []
        
        for i in range(L - 2):
            # skip duplicate number 'a'
            if i > 0 and nums[i] == nums[i-1]:
                continue
            
            target = 0 - nums[i]
            
            left, right = i + 1, L - 1
            
            while left < right:
                if nums[left] + nums[right] == target:
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # skip duplicate number 'b'
                    j = left + 1
                    while j < right and nums[j] == nums[left]:
                        j += 1
                    
                    left = j
                    
                    # skip duplicate number 'c'
                    k = right - 1
                    while  k > left and nums[k] == nums[right]:
                        k -= 1
                        
                    right = k
                    
                    # continue to search next combination
                    continue
                    
                if nums[left] + nums[right] < target:
                    left += 1
                else:
                    right -= 1
        
        return result

[LeetCode] 14. Longest Common Prefix

Problem : https://leetcode.com/problems/longest-common-prefix/

Iterate all strings to find the common prefix.

Time Complexity :  O ( min ( length of all strings ) )

Space Complexity:  O ( len( common-prefix ) )

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        result = ""
        
        # handle edge condition for empty string array
        if not strs:
            return result
        
        # caculate the minimum length of strings
        L = min([len(s) for s in strs])
    
        for i in range(L):
            tmp = strs[0][i]
            for s in strs:
                if s[i] != tmp:
                    # break the loop when reach to the first non-common character
                    return result
            else:
                result += tmp
            
        return result

[LeetCode] 13. Roman to Integer

Problem : https://leetcode.com/problems/roman-to-integer/

Time Complexity = O(len(s))

Space Complexity = O(1)

 
class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """

        symbols = {'I': 1, 'IV': 4, 'V': 5, 'IX': 9, 'X': 10, \
                   'XL': 40, 'L': 50, 'XC': 90, 'C': 100, \
                   'CD': 400, 'D': 500, 'CM': 900, 'M': 1000}

        i = 0
        num = 0
        while i < len(s):
            if i + 1 < len(s) and s[i] + s[i+1] in symbols:
                num += symbols[s[i]+s[i+1]]
                i += 2
            else:
                num += symbols[s[i]]
                i += 1

        return num
 

[LeetCode] 12. Integer to Roman

Problem : https://leetcode.com/problems/integer-to-roman/

Create mapper array to map number to symbol

Time Complexity : O (log(num))

Space Complexity: O(log(num))

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        
        romans = [(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')]
        
        result = ""

        for base, symbol in romans:
            if num >= base:
                result += symbol * (num // base)
                num = num % base

        return result

[LeetCode] 11. Container With Most Water

Problem : https://leetcode.com/problems/container-with-most-water/

This is a typical two pointers problem. Start from the front and rare of the given height array. Since the distance between the 2 vertical lines is decreasing, we need to keep the higher vertical line to get possible larger area.

Time Complexity : O(len(height))

Space Complexity: O(1)

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        result = 0
        
        left, right = 0, len(height) - 1
        
        while left < right:
            result = max(result, min(height[left], height[right]) * (right - left))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
                
        return result

[LeetCode] 10. Regular Expression Matching

Problem : https://leetcode.com/problems/regular-expression-matching/

Time Complexity = O( len(s) * len(p)  )

Space Complexity = O( len(s) * len(p) )

 
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        
        @lru_cache(maxsize = None)
        def helper(i, j):
            if j >= len(p): return i >= len(s)
            
            isMatched = i < len(s) and (s[i] == p[j] or p[j] == '.')
            
            if isMatched and helper(i+1, j+1):
                return True
            
            if j + 1 < len(p) and p[j+1] == '*':
                
                # use '.*' or 'x*' to match nothing
                if helper(i, j+2):
                    return True
                
                # use '.*' or 'x*' to match current char and keep using it to match following chars
                if isMatched and helper(i+1, j):
                    return True
            
            return False
        
        return helper(0, 0)
 

[LeetCode] 9. Palindrome Number

Problem https://leetcode.com/problems/palindrome-number/

Simulate the process to check if the first and last digit are the same.

Recursive solution:

Time Complexity : O (log(x))
Space Complexity: O (1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False

        def helper(x, radix):
            if radix == 0 or x == 0:
                return True

            firstDigit = x // (10 ** radix)
            lastDigit = x % 10

            if firstDigit != lastDigit:
                return False

            return helper((x - firstDigit * (10 ** radix) - lastDigit) // 10, radix - 2)

        radix = 0
        while 10 ** (radix + 1) <= x:
            radix += 1

        return helper(x, radix)

Iterative solution:

Time Complexity : O(log(x))
Space Complexity: O(1)

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """

        if x < 0:
            return False

        left = 0
        while 10 ** (left+1) <= x:
            left += 1

        right = 0

        leftx = x
        rightx = x
        while left >= right:
            l = leftx // (10 ** left)
            r = rightx % 10

            if l != r:
                return False

            rightx = rightx // 10
            right += 1

            leftx = leftx - l * (10 ** left)
            left -= 1

            if rightx != 0 and leftx == 0:
                return False

            if rightx == 0 and leftx != 0:
                return False

        return True

[LeetCode] 8. String to Integer (atoi)

Problem : https://leetcode.com/problems/string-to-integer-atoi/

This problem is similar to the #7. Need to always check if overflow when append digit.
Meanwhile, it's better to use state machine to handle plus / minus sign and non-digit characters.

Time complexity =  O( N ),  N = len(s)
Space complexity =  O( N ),  N = number of valid digits 

class Solution:
    def myAtoi(self, s: str) -> int:
        MAX_INT = 2 ** 31 - 1
        MIN_INT = -2 ** 31
        
        sign = 1
        state = 'space'
        num = 0
        
        i = 0
        while i < len(s):
            if state == 'space':
                if s[i] == ' ':
                    i += 1
                else:
                    state = 'sign'
            elif state == 'sign':
                if s[i] == '+':
                    i += 1
                    state = 'digit'
                elif s[i] == '-':
                    sign = -1
                    i += 1
                    state = 'digit'
                elif s[i].isdigit():
                    state = 'digit'
                else:
                    # illegal number
                    break
            elif state == 'digit':
                if s[i].isdigit():
                    remainder = int(s[i]) * sign
                    
                    if num > MAX_INT // 10 or \
                       (num == MAX_INT // 10 and remainder >= MAX_INT % 10):
                        num = MAX_INT
                        break
                    
                    if num < MIN_INT // 10 or \
                       (num == (MIN_INT - (MIN_INT % -10)) // 10 and remainder <= MIN_INT % -10):
                        num = MIN_INT
                        break
                    
                    num = num * 10 + remainder
                    i += 1
                else:
                    # stop parsing when the encountered character is not digit
                    break
            
        return num

[LeetCode] 7. Reverse Integer

Problem : https://leetcode.com/problems/reverse-integer/

Since the valid signed integer number range is  -2 ** 31 to 2 ** 31 -1.
The code should not convert negative number to positive one.
And it should always check overflow before appending digits.

Time Complexity = O(log(x))
Space Complexity = O(1)

 
from math import fmod

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        result = 0

        max_int = 2 ** 31 - 1
        min_int = -2 ** 31

        while x != 0:
            remain = int(fmod(x, 10))
            
            if result > max_int // 10 or \
               (result == max_int // 10 and remain > max_int % 10):
                return 0

            if result < 0:
                min_remain = fmod(min_int, 10)
                if result < (min_int - min_remain) // 10 or \
                   (result == min_int and remain < min_remain):
                    return 0

            result = result * 10 + remain
            
            # Because python always does 'floor division'  
            # - 1 // 10 = -1 
            # Below formula convert it to (-1 - (-1)) // 10 = 0
            x = (x - remain) // 10

        return result

[LeetCode] 6. ZigZag Conversion

Problem : https://leetcode.com/problems/zigzag-conversion/

The solution is just simulating zigzag traversal steps. Be careful that when numRows <= 1, the code should return the original string.

Time Complexity = O(len(s))
Space Complexity = O(len(s))

from operator import add

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        
        if numRows <= 1:
            return s
        
        memo = [""] * numRows
        
        i = 0
        row = 0
        direction = 1
        col = 0
        
        while i < len(s):
            memo[row] += s[i]
            
            row = row + direction
            if row == numRows:
                row = numRows - 2
                direction = - 1
            
            if row < 0:
                row = 1
                direction = 1
            
            i += 1
            
        return reduce(add, memo)