Coding

Sorting

Bubble Sort

Write a function that takes a list of numbers and sorts them in ascending order.

sort.py


numbers = [50, 10, 20, 40, 30]
 
def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
 
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)  # Output: [10, 20, 30, 40, 50]

LeetCode

Remove Element

https://leetcode.com/problems/remove-element/description/


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

Remove Duplicates from Sorted Array

https://leetcode.com/problems/remove-duplicates-from-sorted-array


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

Concatenation of Array

https://leetcode.com/problems/concatenation-of-array


from typing import List
 
# Solution 1
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        ans = []
        for i in range(2):
            for n in nums:
                ans.append(n)
        return ans
 
# Solution 2
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        # copy values, otherwise both ans and nums will have same memory address (cause infinite loops)
        ans = nums.copy()
        for num in nums:
            ans.append(num)
        return ans
 
# Solution 3
class Solution:
    def getConcatenation(self, nums: List[int]) -> List[int]:
        size = len(nums)
        for i in range(size):
            nums.append(nums[i])
        return nums

Valid Parentheses

https://leetcode.com/problems/valid-parentheses


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

Min Stack

https://leetcode.com/problems/min-stack


class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []
 
    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(val, self.min_stack[-1] if self.min_stack else val))
 
    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()
 
    def top(self) -> int:
        return self.stack[-1]
 
    def getMin(self) -> int:
        return self.min_stack[-1]