Leetcode problems I did in February 2021

absolute-to-canonical-paths.py

# Link: https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3629/
# Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

# In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

# The canonical path should have the following format:

# The path starts with a single slash '/'.
# Any two directories are separated by a single slash '/'.
# The path does not end with a trailing '/'.
# The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')
# Return the simplified canonical path.


# Example 1:

# Input: path = "/home/"
# Output: "/home"
# Explanation: Note that there is no trailing slash after the last directory name.
# Example 2:

# Input: path = "/../"
# Output: "/"
# Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
# Example 3:

# Input: path = "/home//foo/"
# Output: "/home/foo"
# Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
# Example 4:

# Input: path = "/a/./b/../../c/"
# Output: "/c"


# Constraints:

# 1 <= path.length <= 3000
# path consists of English letters, digits, period '.', slash '/' or '_'.
# path is a valid absolute Unix path.


class Solution:
    def simplifyPath(self, path: str) -> str:
        if not (1 <= len(path) <= 3000):
            raise ValueError('Given path is not within size parameters.')
        path = path.split(sep='/')  # Split into list
        path = [i for i in path if i != '']  # Delete empty strings
        canonical_path = []
        for i in path:
            if i == '.':
                continue
            if i == '..':
                if not canonical_path:
                    continue  # no-op
                else:
                    canonical_path.pop()  # Go back one level
                    continue
            else:
                canonical_path.append(i)
        canonical_path = '/'.join(canonical_path)  # Create string
        canonical_path = '/' + canonical_path  # Prepend leading /
        return canonical_path


if __name__ == '__main__':
    print(Solution().simplifyPath("/a/./b/../../c/"))
    print(Solution().simplifyPath("/home//foo/"))
    print(Solution().simplifyPath("/../"))
    print(Solution().simplifyPath("/home/"))
    print(Solution().simplifyPath("/home//foo/aj"))
    print(Solution().simplifyPath(("/opt/Google Chrome/exec.exe")))

binary_tree_right_side_view.py

# Link: https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3630/
# Given a binary tree, imagine yourself standing on the right side of it,
# return the values of the nodes you can see ordered from top to bottom.

# Example:

# Input: [1,2,3,null,5,null,4]
# Output: [1, 3, 4]
# Explanation:

#    1            <---
#  /   \
# 2     3         <---
#  \     \
#   5     4       <---

from typing import List


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        right_nodes = []
        if not root:
            return []
        nodes = [root]
        while (n := len(nodes)):
            for i in range(1, n + 1):
                temp = nodes.pop(0)
                if i == n:
                    right_nodes.append(temp.val)
                if temp.left is not None:
                    nodes.append(temp.left)
                if temp.right is not None:
                    nodes.append(temp.right)
        return right_nodes

linked_list_cycle_detection.py

# https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3627/
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __eq__(self, o: object) -> bool:
        if self.val == o.val and self.next == o.next:
            return True
        else:
            return False


class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        fast, slow = head, head
        while(fast and fast.next):
            if fast.next.next is slow:  # Found the cycle
                return True
            fast = fast.next.next
            slow = slow.next
        return False

longest_harmonius_subsequence.py

# https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3628/
# A subsequence of array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

# Example 1:

# Input: nums = [1,3,2,2,5,2,3,7]
# Output: 5
# Explanation: The longest harmonious subsequence is [3,2,2,2,3].
# Example 2:

# Input: nums = [1,2,3,4]
# Output: 2
# Example 3:

# Input: nums = [1,1,1,1]
# Output: 0

# Constraints:

#       1 <= nums.length <= 2 * 104
#       -109 <= nums[i] <= 109

from typing import List
from collections import Counter


class Solution:
    def findLHS(self, nums: List[int]) -> int:
        hash = Counter(nums)  # Need dictionary of frequencies for each item
        sequence_length = 0
        for h in hash.keys():
            if h+1 in hash:  # check if next consecutive integer is available
                # sum frequencies of every pair of consecutive integers
                sequence_length = max(sequence_length, (hash[h] + hash[h+1]))
        return sequence_length


if __name__ == '__main__':
    print(Solution().findLHS([1, 3, 2, 2, 5, 2, 3, 7]))
    print(Solution().findLHS([1, 2, 3, 4]))
    print(Solution().findLHS([1, 1, 1, 1]))
    print(Solution().findLHS([1, 2, 2, 3, 4, 5, 1, 1, 1, 1]))
    print(Solution().findLHS(list(range(10))))

peeking_iterator.py

# Given an Iterator class interface with methods: next() and hasNext(),
# design and implement a PeekingIterator that support the peek()
# operation -- it essentially peek() at the element that will be
# returned by the next call to next().
# Example:

# Assume that the iterator is initialized to the beginning of the list: [1,2,3].

# Call next() gets you 1, the first element in the list.
# Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.
# You call next() the final time and it returns 3, the last element.
# Calling hasNext() after that should return false.
# Follow up: How would you extend your design to be generic and work with all types, not just integer?

# Hint 1: Think of "looking ahead". You want to cache the next element.
# Hint 2: Is one variable sufficient? Why or why not?
# Hint 3: Test your design with call order of `peek()` before `next()`
#   vs `next()` before `peek()`
# Hint 4: For a clean implementation, check out Google's guava library
#   source code: https://github.com/google/guava/blob/703ef758b8621cfbab16814f01ddcc5324bdea33/guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/Iterators.java#L1125

# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
#     def __init__(self, nums):
#         """
#         Initializes an iterator object to the beginning of a list.
#         :type nums: List[int]
#         """

#     def hasNext(self):
#         """
#         Returns true if the iteration has more elements.
#         :rtype: bool
#         """

#     def next(self):
#         """
#         Returns the next element in the iteration.
#         :rtype: int
#         """


class PeekingIterator:
    def __init__(self, iterator):
        """
        Initialize your data structure here.
        :type iterator: Iterator
        """

    def peek(self):
        """
        Returns the next element in the iteration without advancing the iterator.
        :rtype: int
        """

    def next(self):
        """
        :rtype: int
        """

    def hasNext(self):
        """
        :rtype: bool
        """

# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
#     val = iter.peek()   # Get the next element but not advance the iterator.
#     iter.next()         # Should return the same value as [val].

shortest_distance_to_character.py

# Given a string s and a character c that occurs in s, return an array
# of integers answer where answer.length == s.length and answer[i] is
# the shortest distance from s[i] to the character c in s.

# Example 1:

# Input: s = "loveleetcode", c = "e"
# Output: [3,2,1,0,1,0,0,1,2,2,1,0]
# Example 2:

# Input: s = "aaab", c = "b"
# Output: [3,2,1,0]

# Constraints:

# 1 <= s.length <= 104
# s[i] and c are lowercase English letters.
# c occurs at least once in s.

from typing import List


class Solution:
    def shortestToChar(self, s: str, c: str) -> List[int]:
        c_indexes = [index for index, element in enumerate(s) if element == c]
        answer = []
        for index, element in enumerate(s):
            if element == c:
                answer.append(0)
            else:
                answer.append(
                    min(
                        [abs(index - idx) for idx in c_indexes]
                    )
                )
        return answer

trim_bst.py

# Link to problem: https://leetcode.com/explore/challenge/card/february-leetcoding-challenge-2021/584/week-1-february-1st-february-7th/3626/
# Definition for a binary tree node.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# class Solution:
#     def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
#         if not root:
#             return
#         if root.val >= low and root.val <= high:
#             root.left = self.trimBST(root.left,low,high)
#             root.right = self.trimBST(root.right,low,high)
#             return root
#         elif root.val < low:
#             return self.trimBST(root.right,low,high)
#         elif root.val > high:
#             return self.trimBST(root.left,low,high)


class Solution:
    def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
        if not root:
            return None
        root.left = self.trimBST(root.left, low, high)
        root.right = self.trimBST(root.right, low, high)

        if not (low <= root.val <= high):
            if (root.left is None) and (root.right is None):
                return None
            elif (root.left is not None) and (root.right is None):
                return root.left
            elif (root.left is None) and (root.right is not None):
                return root.right
            else:
                previous = root
                node = root.right
                while node.left is not None:
                    node = node.left
                root.val = node.val
                if node == root.right:
                    previous.right = None
                else:
                    previous.left = None
                return root
        else:
            return root