Let’s crunch some Leet

Working on mock algos from https://leetcode.com/problemset/algorithms/.
leetcode
Author

David Dobrinskiy

Published

March 16, 2021

longest-substring-without-repeating-characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

def test(input_, want):
    got = Solution().foo(input_)

    if got != want:
        msg = f"got='{got}', want='{want}'"
        raise AssertionError(msg)
class Solution:
    def foo(self, s: str) -> int:
        max_len = 0
        for idx_start in range(len(s)):
            sub = set()
            for i in range(idx_start, len(s)):
                #                 print(idx_start, i, s[i], sub)
                if s[i] in sub:
                    #                     print(len(sub))
                    max_len = max(max_len, len(sub))
                    break
                else:
                    sub |= set(s[i])
            max_len = max(max_len, len(sub))

        return max_len
test("pwwkew", 3)
test(" ", 1)
test("wwww", 1)
test("abcabcbb", 3)
test("", 0)
test("abcdexfbdgcbb", 7)
# one-pass sliding window
class Solution:
    def foo(self, s: str) -> int:
        n = len(s)
        ans = 0

        mp = {}  # store max index
        i = 0
        for j in range(n):
            if s[j] in mp:
                i = max(mp[s[j]], i)

            ans = max(ans, j - i + 1)
            mp[s[j]] = j + 1

        return ans


# Time complexity : O(n). Index j will iterate n times.
# Memory: O(min(m, n)) We need O(k) space for the sliding window, where kk is the size of the Set. The size of the Set is upper bounded by the size of the string nn and the size of the charset/alphabet mm.
test("abcdexfbdgcbb", 7)
test("pwwkew", 3)
test(" ", 1)
test("wwww", 1)
test("abcabcbb", 3)
test("", 0)

7. Reverse Integer

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 \([-2^{31}, 2^{31} - 1]\), then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

class Solution:
    def foo(self, x: int) -> int:
        MAX_INT = (2**31) - 1

        if x >= 0:
            sign = 1
        else:
            sign = -1
        nums = list()

        x = abs(x)
        while True:
            nums.append(x % 10)
            x = x // 10
            if x == 0:
                #                 print(nums)
                break

        dec = 1
        ans = 0
        for n in nums[::-1]:
            # since we use 32bit, we should return 0 if (ans+tail) > MAX_INT
            # if we rearrange parts of the eqation, we can avoid overflowing while
            # still checking  (ans+tail) for overflow
            if (ans / MAX_INT + n * (dec / MAX_INT)) > 1:
                return 0

            ans += n * dec
            dec *= 10
        return ans * sign
class Solution:
    def foo(self, x: int) -> int:
        MAX_INT = (2**31) - 1

        if x >= 0:
            sign = 1
        else:
            sign = -1
        nums = list()

        x = abs(x)
        while True:
            nums.append(x % 10)
            x = x // 10
            if x == 0:
                print(nums)
                break

        dec = 1
        ans = 0
        for n in nums[::-1]:
            # since we use 32bit, we should return 0 if (ans+tail) > MAX_INT
            # if we rearrange parts of the eqation, we can avoid overflowing while
            # still checking  (ans+tail) for overflow
            if (ans / MAX_INT + n * (dec / MAX_INT)) > 1:
                return 0

            ans += n * dec
            dec *= 10
        return ans * sign
test(1534236469, 0)
test(123, 321)
test(-123, -321)
test(0, 0)
test(120, 21)
2**32 - 1
2147483651 >= 2**31
x = 321
x = 120
x = -321

5. Longest Palindromic Substring

# quadratic solution (too slow)
class Solution:
    def foo(self, s):
        n = len(s)

        while n:
            for i in range(len(s) - n + 1):
                candidate = s[i : i + n]
                #                 print(n,i,candidate)
                if self.is_palindrome(candidate):
                    return candidate
            n -= 1

        return ""

    def is_palindrome(self, x: str) -> bool:
        n = len(x)
        for i in range(n // 2):
            if x[i] != x[n - i - 1]:
                return False
        return True
class Solution:
    def foo(self, s: str) -> str:
        m = ""  # Memory to remember a palindrome
        for i in range(len(s)):  # i = start, O = n
            for j in range(len(s), i, -1):  # j = end, O = n^2
                if len(m) >= j - i:  # To reduce time
                    break
                elif s[i:j] == s[i:j][::-1]:
                    m = s[i:j]
                    break
        return m
class Solution:
    def foo(self, s: str) -> str:
        m = ""  # Memory to remember a palindrome
        for i in range(len(s)):  # i = start, O = n
            for j in range(len(s), i, -1):  # j = end, O = n^2
                if len(m) >= j - i:  # To reduce time
                    break
                elif s[i:j] == s[i:j][::-1]:
                    m = s[i:j]
                    break
        return m
list(range(5, 2, -1))
test("babad", "bab")

test("cbbd", "bb")

test("a", "a")

test("", "")
def generate(cur, open, closed, n):
    if len(cur) == 2 * n:
        if open == closed:
            print(cur)
        return

    generate(cur + "(", open + 1, closed, n)

    if open > closed:
        generate(cur + ")", open, closed + 1, n)
generate("", 0, 0, 1)
generate("", 0, 0, 2)
generate("", 0, 0, 3)

21. Merge Two Sorted Lists

Runtime: 40 ms, faster than 49.45% of Python3 online submissions for Merge Two Sorted Lists.
Memory Usage: 14.3 MB, less than 33.73% of Python3 online submissions for Merge Two Sorted Lists.
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        return f"{self.val} -> {self.next}"


class Solution:
    def _merge(self, l1, l2):
        l1 = self.list_to_ListNode(l1)
        l2 = self.list_to_ListNode(l2)

        return self.mergeTwoLists(l1, l2)

    def list_to_ListNode(self, lst):
        lst = iter(lst)
        root = ListNode(val=next(lst))
        node = root
        for newval in lst:
            node.next = ListNode(val=newval)
            node = node.next
        return root

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # DON'T FORGET TO DROP FIRST NODE
        answer_root = ListNode(val=None)
        answer = answer_root

        while True:
            if (l1 is None) and (l2 is not None):
                answer.next = ListNode(l2.val)
                l2 = l2.next
            elif (l1 is not None) and (l2 is None):
                answer.next = ListNode(l1.val)
                l1 = l1.next
            elif (l1 is None) and (l2 is None):
                return answer_root.next  # remember to drop fake zero-node
            #     print(answer_root.next)
            elif l1.val <= l2.val:
                answer.next = ListNode(l1.val)
                l1 = l1.next
            elif l1.val > l2.val:
                answer.next = ListNode(l2.val)
                l2 = l2.next
            else:
                raise Exception

            answer = answer.next
convert = Solution().list_to_ListNode
l1 = [1, 2, 4, 5]
l2 = [2, 3, 4]

# print(Solution().list_to_ListNode(l1))
# print(Solution().list_to_ListNode(l2))

l1, l2 = convert(l1), convert(l2)
print(l1)
print(l2)
# DON'T FORGET TO DROP FIRST NODE
answer_root = ListNode(val=None)

answer = answer_root

if (l1 is None) and (l2 is not None):
    answer.next = ListNode(l2.val)
    l2 = l2.next
elif (l1 is not None) and (l2 is None):
    answer.next = ListNode(l1.val)
    l1 = l1.next
elif (l1 is None) and (l2 is None):
    return answer_root.next  # remember to drop fake zero-node
#     print(answer_root.next)
elif l1.val <= l2.val:
    answer.next = ListNode(l1.val)
    l1 = l1.next
elif l1.val > l2.val:
    answer.next = ListNode(l2.val)
    l2 = l2.next
else:
    raise Exception

answer = answer.next

print(answer_root)
print("l1:", l1)
print("l2:", l2)

4. Median of Two Sorted Arrays

Success 

Runtime: 104 ms, faster than 28.31% of Python3 online submissions for Median of Two Sorted Arrays.
Memory Usage: 14.6 MB, less than 58.71% of Python3 online submissions for Median of Two Sorted Arrays.

median if n is is_odd = \(X_{i}\), i = n//2 + 1 median if n is even = \(\frac{X_i+X_j}{2}\), i = n/2, j=n/2+1

def next_or_none(itr):
    try:
        return next(itr)
    except StopIteration:
        return None


class Solution:
    def findMedianSortedArrays(self, numsA: List[int], numsB: List[int]) -> float:
        n = len(numsA) + len(numsB)

        numsA = iter(numsA)
        numsB = iter(numsB)

        n_is_odd = bool(n % 2)
        n_is_even = not n_is_odd

        if n_is_odd:
            idx_1 = n // 2
            idx_2 = None
        else:
            idx_1 = n / 2 - 1
            idx_2 = n / 2

        a, b = next_or_none(numsA), next_or_none(numsB)

        current_idx = -1
        current_value = None

        # while True:
        for _ in range(n):
            current_idx += 1
            prev_value = current_value

            if (a is None) and (b is not None):
                current_value = b
                b = next_or_none(numsB)
            elif (a is not None) and (b is None):
                current_value = a
                a = next_or_none(numsA)
            elif a <= b:
                current_value = a
                a = next_or_none(numsA)
            elif a > b:
                current_value = b
                b = next_or_none(numsB)

            if (current_idx == idx_1) and n_is_odd:
                return current_value

            if (current_idx == idx_2) and n_is_even:
                return (prev_value + current_value) / 2

6. ZigZag Conversion

matrix = [["-"] * 7] * 3

matrix
[['-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', '-']]
class Point:
    def __init__(self):
        self.x = 0
        self.y = 0

    def write(self, char):
        matrix[self.y][self.x] = char

    def __repr__(self):
        char = matrix[self.y][self.x]
        return f"{[self.x, self.y]} -> {char}"


p = Point()
p.write("x")
p
[0, 0] -> x
matrix
[['x', '-', '-', '-', '-', '-', '-'],
 ['x', '-', '-', '-', '-', '-', '-'],
 ['x', '-', '-', '-', '-', '-', '-']]
import numpy as np
numpy
matrix[]
print("\n".join(["".join(row) for row in matrix]))
-------
-------
-------