LeetCode

My solutions to different problems and what not.

Usually I pay less attention to the time/space complexity part and focus more on just solving the problem.

Problems

1. Two Sum

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.

Solution

1_two_sum.py

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, ival in enumerate(nums):
            for j, jval in enumerate(nums):
                if ival + jval == target and i != j:
                    return [i, j]

9. Palindrome Number

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

Solution

9_palindrome_number.py

class Solution:
    def isPalindrome(self, x: int) -> bool:
        counter = 0
        xstr = str(x)  
        for idx, c in enumerate(xstr):
            if c == xstr[len(xstr) - 1 - idx]:
                counter = counter + 1
        return counter == len(xstr)

13. Roman to Integer

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.

Solution

13_roman_to_integer.py

class Solution:
    def romanToInt(self, s: str) -> int:
        d = {
        "I": 1,
        "V": 5,
        "X": 10,
        "L": 50,
        "C": 100,
        "D": 500,
        "M": 1000,
        "IV": 4,
        "IX": 9,
        "XL": 40,
        "XC": 90,
        "CD": 400,
        "CM": 900
    }

        result = 0
        idx = 0
        nxt = ""
        while idx < len(s):
            c = s[idx]     
            if idx < len(s) - 1:
                nxt = s[idx + 1]
            if c + nxt in d.keys():
                result = result + d[c + nxt]
                idx = idx + 1
            else:
                result = result + d[c]
            idx = idx + 1
        return result

14. Longest Common Prefix

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

Solution

14_longest_common_prefix.py

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        first = strs[0]
        res = ""
        for i, c in enumerate(first):
            if all(i < len(s) and s[i] == c for s in strs[1:]):
                res = res + c
            else:
                return res
        return res

20. Valid Parentheses

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

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.

2. Open brackets must be closed in the correct order.

3. Every close bracket has a corresponding open bracket of the same type.

Solution

20_valid_parentheses.py

class Solution:
    from collections import deque

    def isValid(self, s: str) -> bool:
        stack = deque()
        for c in s:
            if len(stack) > 0 and stack[-1] == "(" and c == ")":
                stack.pop()
            elif len(stack) > 0 and stack[-1] == "[" and c == "]":
                stack.pop()
            elif len(stack) > 0 and stack[-1] == "{" and c == "}":
                stack.pop()
            else:
                stack.append(c)        
        return len(stack) == 0

28. Find the Index of the First Occurrence in a String

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.

Solution

28_find_the_index_of_the_first_occurrence_in_a_string.py

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

118. Pascal's Triangle

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:

Solution with the use of math.comb()

118_pascals_triangle.py

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for n in range(numRows):
            row = []
            for k in range(n + 1):
                row.append(comb(n, k))
            res.append(row)
        return res

Solution without the use of math.comb()

118_pascals_triangle.py

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        i = 0
        while i < numRows:
            l = []
            if i == 0:
                l = [1]
            elif i == 1:
                l = [1,1]
            else:
                row = res[i - 1]
                l = []
                for idx, v in enumerate(row):
                    if idx < len(row) - 1:
                        l.append(row[idx] + row[idx + 1])
                l = [1] + l + [1]   
            res.append(l) 
            i = i + 1
        return res

119. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Solution

119_pascals_triangle_ii.py

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        return [math.comb(rowIndex, k) for k in range(rowIndex + 1)]

136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Solution

136_single_number.py

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        u = set()
        for elem in nums:
            if elem in u:
                u.discard(elem)
            else:
                u.add(elem)     
        return u.pop()

1046. Last Stone Weight

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

• If x == y, both stones are destroyed, and

• If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Solution

1046_last_stone_weight.py

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        while len(stones) > 1:
            largest = stones.pop(stones.index(max(stones)))
            snd_largest = stones.pop(stones.index(max(stones)))
            if largest != snd_largest:
                stones.append(largest - snd_largest)
        if stones == []:
            return 0
        return stones[0]