LeetCode

.leetcode

LeetCode solved problems:

   1. Two Sum
   7. Reverse Integer
   9. Palindrome Number
  13. Roman to Integer
  14. Longest Common Prefix
  20. Valid Parentheses
  26. Remove Duplicates from Sorted Array
  27. Remove Element
  28. Implement strStr()
  35. Search Insert Position
  38. Count and Say
  54. Spiral Matrix
  58. Length of Last Word
  59. Spiral Matrix II
  67. Add Binary
  69. Sqrt(x)
 125. Valid Palindrome
 136. Single Number
 202. Happy Number
 463. Island Perimeter
 566. Reshape the Matrix
 766. Toeplitz Matrix
 832. Flipping an Image
 861. Score After Flipping Matrix
 883. Projection Area of 3D Shapes
 999. Available Captures for Rook
1030. Matrix Cells in Distance Order
1221. Split a String in Balanced Strings
1266. Minimum Time Visiting All Points
1295. Find Numbers with Even Number of Digits
1299. Replace Elements with Greatest Element on Right Side
1337. The K Weakest Rows in a Matrix
1351. Count Negative Numbers in a Sorted Matrix
1365. How Many Numbers Are Smaller Than the Current Number
1380. Lucky Numbers in a Matrix
1476. Subrectangle Queries
1572. Matrix Diagonal Sum
1582. Special Positions in a Binary Matrix
1672. Richest Customer Wealth

0001.py

# 1. Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n_dict = {}
        for i in range(len(nums)):
            f_num = target - nums[i]
            if n_dict.get(f_num) != None:
                return [n_dict[f_num], i]
            n_dict[nums[i]] = i
        return []

0007.py

# 7. Reverse Integer

class Solution:
    def reverse(self, x: int) -> int:
        res = int(str(abs(x))[::-1])
        if res > 2 ** 31 - 1:
            return 0
        if x < 0:
            return -res
        return res

0009.py

# 9. Palindrome Number

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if (x < 0) | ((x % 10 == 0) & (x != 0)):
            return False
        rx = 0
        while rx < x:
            rx = rx * 10 + x % 10
            x //= 10
        return (x == rx) | (x == rx // 10)

0013.py

# 13. Roman to Integer

class Solution:
    def romanToInt(self, s: str) -> int:
        sym_val = { 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000 }
        res = 0
        prev = 0
        for sym in s:
            cur = sym_val[sym]
            mult = 1
            if cur > prev:
                mult = -1
            res += prev * mult
            prev = cur
        return res + prev

0014.py

# 14. Longest Common Prefix

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        if len(strs) == 0:
            return res
        for ltr in strs[0]:
            for wrd in strs[1::]:
                if wrd.find(res + ltr) != 0:
                    return res
            res += ltr
        return res

0020.py

# 20. Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        brackets = {'(': ')', '[': ']', '{': '}'}
        stack = []
        for char in s:
            if char in brackets:
                stack.append(char)
            else:
                if not stack or brackets[stack[-1]] != char:
                    return False
                stack.pop()
        return not stack

0026.py

# 26. Remove Duplicates from Sorted Array

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        i = 0
        for j in range(1, len(nums)):
            if nums[j] != nums[i]:
                i += 1
                nums[i] = nums[j]
        return i + 1

0027.py

# 27. Remove Element

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i

0028.py

# 28. Implement strStr()

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle or haystack == needle:
            return 0
        lh = len(haystack)
        ln = len(needle)
        for i in range(lh - ln + 1):
            if haystack[i] == needle[0] and haystack[i:i+ln] == needle:
                return i
        return -1

0035.py

# 35. Search Insert Position
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums) - 1
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                high = mid - 1
            else:
                low = mid + 1
        return low

0038.py

# 38. Count and Say

class Solution:
    def countAndSay(self, n: int) -> str:
        if n <= 1:
            return '1'
        else:
            term = self.countAndSay(n - 1)
            res, cnt, say = '', 1, term[0]
            for i in range(1, len(term)):
                if term[i] != say:
                    res += f'{cnt}{say}'
                    cnt, say = 1, term[i]
                else:
                    cnt += 1
            return f'{res}{cnt}{say}'

0054.py

# 54. Spiral Matrix

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        cur = {'i': 0, 'j': 0}
        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dir_steps = [m, n]
        res, dir_num, step = [], 0, 0
        for _ in range(m * n):
            step += 1
            res.append(matrix[cur['i']][cur['j']])
            if step == dir_steps[(dir_num + 1) % 2]:
                dir_steps[dir_num % 2] -= 1
                step = 0
                dir_num += 1
            cur['i'] += dirs[dir_num % 4][0]
            cur['j'] += dirs[dir_num % 4][1]
        return res

0058.py

# 58. Length of Last Word

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        cnt = 0
        for i in reversed(range(len(s.rstrip()))):
            if s[i] != ' ':
                cnt += 1
            else:
                break
        return cnt

0059.py

# 59. Spiral Matrix II

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        mat = [[0] * n for _ in range(n)]
        cur = {'i': 0, 'j': 0}
        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        dir_steps, dir_num, step = [n, n], 0, 0
        for i in range(1, n * n + 1):
            mat[cur['i']][cur['j']] = i
            if i - step == dir_steps[(dir_num + 1) % 2]:
                dir_steps[dir_num % 2] -= 1
                step = i
                dir_num += 1
            cur['i'] += dirs[dir_num % 4][0]
            cur['j'] += dirs[dir_num % 4][1]
        return mat

0067.py

# 67. Add Binary

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a) > len(b):
            b = b.zfill(len(a))
        elif len(a) < len(b):
            a = a.zfill(len(b))
        mem, res = 0, ''
        for i in reversed(range(len(a))):
            dsum = int(a[i]) + int(b[i]) + mem
            res += str(dsum % 2)
            mem = dsum // 2
        if mem:
            res += str(mem)
        return res[::-1]

0069.py

# 69. Sqrt(x)

class Solution:
    def mySqrt(self, x: int) -> int:
        low = 0
        high = x
        while low <= high:
            mid = (low + high) // 2
            test = mid * mid
            if test == x:
                return mid
            if test > x:
                high = mid - 1
            else:
                low = mid + 1
        return high

0125.py

# 125. Valid Palindrome

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join([i.lower() for i in s if i.isalnum()])
        if len(s) <= 1:
            return True
        for i in range(len(s) // 2):
            if s[i] != s[-1 - i]:
                return False
        return True

0136.py

# 136. Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n_dict = {}
        for i in nums:
            if n_dict.get(i):
                n_dict.pop(i)
            else:
                n_dict[i] = '#'
        return next(iter(n_dict)) if n_dict else 0

0202.py

# 202. Happy Number

class Solution:
    def isHappy(self, n: int) -> bool:
        if n < 0:
            return False
        n_dict = {n: '#'}
        while n != 1:
            n = sum(int(i) ** 2 for i in str(n))
            if n_dict.get(n):
                return False
            n_dict[n] = '#'
        return True

0463.py

# 463. Island Perimeter

class Solution:
    def islandPerimeter(self, grid: List[List[int]]) -> int:
        p = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    p += 4
                    if i > 0 and grid[i - 1][j] == 1:
                        p -= 2
                    if j > 0 and grid[i][j - 1] == 1:
                        p -= 2
        return p

0566.py

# 566. Reshape the Matrix

class Solution:
    def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        if m * n != r * c:
            return mat
        res = [[0] * c for _ in range(r)]
        for i in range(r * c):
            res[i // c][i % c] = mat[i // n][i % n]
        return res

0766.py

# 766. Toeplitz Matrix

class Solution:
    def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
        m = len(matrix)
        n = len(matrix[0])
        
        for i in range(m):
            for j in range(n):
                if i < m-1 and j < n-1 and matrix[i][j] != matrix[i+1][j+1]:
                    return False
        
        return True

0832.py

# 832. Flipping an Image

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for row in image:
            for i in range((len(row) + 1) // 2):
                if row[i] == row[~i]:
                    row[i] = row[~i] = row[i] ^ 1
        return image

0861.py

# 861. Score After Flipping Matrix

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = (1 << n - 1) * m
        for j in range(1, n):
            col_sum = sum(row[j] == row[0] for row in grid)
            res += max(col_sum, m - col_sum) * (1 << n - 1 - j)
        return res

0883.py

# 883. Projection Area of 3D Shapes

class Solution:
    def projectionArea(self, grid: List[List[int]]) -> int:
        rows = []
        cols = []
        tows = 0
        n = len(grid)
        for i in range(n):
            rows.append([])
            cols.append([])
            for j in range(n):
                rows[i].append(grid[i][j])
                cols[i].append(grid[j][i])
                if grid[i][j] != 0:
                    tows += 1
        return sum([max(i) for i in rows]) + sum([max(i) for i in cols]) + tows

0999.py

# 999. Available Captures for Rook

class Solution:
    def numRookCaptures(self, board: List[List[str]]) -> int:
        n = len(board)
        pos = []
        for r in range(n):
            for c in range(n):
                if board[r][c] == 'R':
                    rc_str = ''.join(board[r] + [' '] + [board[i][c] for i in range(n)]).replace('.', '')
                    return rc_str.count('pR') + rc_str.count('Rp')
        return 0

1030.py

# 1030. Matrix Cells in Distance Order

class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        coord = []
        for i in range(rows):
            for j in range(cols):
                coord.append([i, j])
        return sorted(coord, key=lambda v: abs(rCenter - v[0]) + abs(cCenter - v[1]))

1221.py

# 1221. Split a String in Balanced Strings

class Solution:
    def balancedStringSplit(self, s: str) -> int:
        bal = res = 0
        dct = {"L": -1, "R": 1}
        for ltr in s:
            bal += dct[ltr]
            if bal == 0:
                res += 1
        return res

1266.py

# 1266. Minimum Time Visiting All Points

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        counter = 0
        for i in range(len(points) - 1):
            x_diff = abs(points[i][0] - points[i+1][0])
            y_diff = abs(points[i][1] - points[i+1][1])
            counter += max(x_diff, y_diff)
        return counter

1295.py

# 1295. Find Numbers with Even Number of Digits

class Solution:
    def findNumbers(self, nums: List[int]) -> int:
        counter = 0
        for i in nums:
            if len(str(i)) % 2 == 0:
                counter += 1
        return counter

1299.py

# 1299. Replace Elements with Greatest Element on Right Side

class Solution:
    def replaceElements(self, arr: List[int]) -> List[int]:
        maxval = -1
        for i in range(len(arr) - 1, -1, -1):
            arr[i], maxval = maxval, max(maxval, arr[i])
        return arr

1337.py

# 1337. The K Weakest Rows in a Matrix

class Solution:
    def rowSolNum(self, row: List[int]) -> int:
        l = 0
        r = len(row) - 1
        while l <= r:
            m = (l + r) // 2
            if row[m - 1] > row[m]:
                return m
            if row[m] == 0:
                r = m - 1
            else:
                l = m + 1
        return l
    
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        sol = [self.rowSolNum(row) for row in mat]
        return sorted(range(len(mat)), key=lambda i: sol[i])[:k]

1351.py

# 1351. Count Negative Numbers in a Sorted Matrix

class Solution:
    def countNegatives(self, grid: List[List[int]]) -> int:
        counter = 0
        m = len(grid)
        n = len(grid[0])
        for i in range(m):
            for j in range(n):
                if grid[i][j] < 0:
                    counter += (m - i) * (n - j)
                    n = j
                    break
        return counter

1365.py

# 1365. How Many Numbers Are Smaller Than the Current Number

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        nums_orig = nums.copy()
        nums.sort()
        return [nums.index(i) for i in nums_orig]

1380.py

# 1380. Lucky Numbers in a Matrix

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        min_row = [min(row) for row in matrix]
        max_col = [max([matrix[i][j] for i in range(len(matrix))]) for j in range(len(matrix[0]))]
        return list(set(min_row) & set(max_col))

1476.py

# 1476. Subrectangle Queries

class SubrectangleQueries:

    def __init__(self, rectangle: List[List[int]]):
        self.rect = rectangle

    def updateSubrectangle(self, row1: int, col1: int, row2: int, col2: int, newValue: int) -> None:
        for i in range(row1, row2 + 1):
            for j in range(col1, col2 + 1):
                self.rect[i][j] = newValue

    def getValue(self, row: int, col: int) -> int:
        return self.rect[row][col]

1572.py

# 1572. Matrix Diagonal Sum

class Solution:
    def diagonalSum(self, mat: List[List[int]]) -> int:
        s = 0
        l = len(mat)
        c = l // 2

        for i in range(c):
            s += mat[i][i] + mat[i][~i] + mat[~i][i] + mat[~i][~i]

        if l % 2 == 1:
            s += mat[c][c]

        return s

1582.py

# 1582. Special Positions in a Binary Matrix

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        m = len(mat)
        n = len(mat[0])
        
        row_sums = [0] * m
        col_sums = [0] * n
        
        one_pos = []
        special_pos_num = 0
        
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    row_sums[i] += 1
                    col_sums[j] += 1
                    one_pos.append([i, j])
        
        for pos in one_pos:
            if row_sums[pos[0]] == col_sums[pos[1]] == 1:
                special_pos_num += 1
        
        return special_pos_num

1672.py

# 1672. Richest Customer Wealth

class Solution:
    def maximumWealth(self, accounts: List[List[int]]) -> int:
        return max(sum(i) for i in accounts)