Forem: Abhishek Chaudhary

Canvas API

Abhishek Chaudhary — Thu, 21 Mar 2024 03:09:14 +0000

This is a submission for DEV Challenge v24.03.20, One Byte Explainer: Browser API or Feature.

Explainer

The Canvas API provides a drawing surface for creating visually engaging graphics and images using JavaScript to dynamically render shapes, paths, text, and images, enabling the creation of interactive charts, animations, and games on the web.

Serialize and Deserialize BST

Abhishek Chaudhary — Sun, 19 Jun 2022 04:00:48 +0000

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
0 <= Node.val <= 104
The input tree is guaranteed to be a binary search tree.

SOLUTION:

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

class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        tree = {}
        paths = [(root, 0)]
        while len(paths) > 0:
            curr, i = paths.pop()
            if curr:
                tree[i] = curr.val
                paths.append((curr.left, 2 * i + 1))
                paths.append((curr.right, 2 * i + 2))
        return ";".join(["{}={}".format(k, v) for k, v in tree.items()])

    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(";")
        tree = {}
        for v in vals:
            if len(v) > 0:
                key, value = v.split("=")
                tree[int(key)] = int(value)
        if len(tree) == 0:
            return None
        root = TreeNode()
        paths = [(root, 0)]
        while len(paths) > 0:
            curr, i = paths.pop()
            curr.val = tree[i]
            if (2 * i + 1) in tree:
                curr.left = TreeNode()
                paths.append((curr.left, 2 * i + 1))
            if (2 * i + 2) in tree:
                curr.right = TreeNode()
                paths.append((curr.right, 2 * i + 2))
        return root

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans

Valid Palindrome

Abhishek Chaudhary — Sun, 19 Jun 2022 03:30:36 +0000

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105
s consists only of printable ASCII characters.

SOLUTION:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = "".join([c.lower() for c in s if c.isalnum()])
        return s == s[::-1]

Average Salary Excluding the Minimum and Maximum Salary

Abhishek Chaudhary — Sun, 19 Jun 2022 03:00:41 +0000

You are given an array of unique integers salary where salary[i] is the salary of the ith employee.

Return the average salary of employees excluding the minimum and maximum salary. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: salary = [4000,3000,1000,2000]
Output: 2500.00000
Explanation: Minimum salary and maximum salary are 1000 and 4000 respectively.
Average salary excluding minimum and maximum salary is (2000+3000) / 2 = 2500

Example 2:

Input: salary = [1000,2000,3000]
Output: 2000.00000
Explanation: Minimum salary and maximum salary are 1000 and 3000 respectively.
Average salary excluding minimum and maximum salary is (2000) / 1 = 2000

Constraints:

3 <= salary.length <= 100
1000 <= salary[i] <= 106
All the integers of salary are unique.

SOLUTION:

class Solution:
    def average(self, salary: List[int]) -> float:
        n = len(salary)
        total = 0
        currmin = float('inf')
        currmax = float('-inf')
        for i in range(n):
            currmin = min(currmin, salary[i])
            currmax = max(currmax, salary[i])
            total += salary[i]
        return (total - currmin - currmax) / (n - 2)

Backspace String Compare

Abhishek Chaudhary — Sun, 19 Jun 2022 02:30:40 +0000

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

SOLUTION:

class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        ss = ""
        tt = ""
        for c in s:
            if c == "#":
                ss = ss[:-1]
            else:
                ss += c
        for c in t:
            if c == "#":
                tt = tt[:-1]
            else:
                tt += c
        return ss == tt

Maximum Erasure Value

Abhishek Chaudhary — Sun, 19 Jun 2022 02:00:46 +0000

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 104

SOLUTION:

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        msum = 0
        p = [0]
        for el in nums:
            p.append(p[-1] + el)
        prev = {}
        i = 0
        for j in range(n):
            if nums[j] in prev:
                i = max(i, prev[nums[j]] + 1)
            msum = max(msum, p[j + 1] - p[i])
            prev[nums[j]] = j
        return msum

Balance a Binary Search Tree

Abhishek Chaudhary — Sun, 19 Jun 2022 01:30:42 +0000

Given the root of a binary search tree, return a balanced binary search tree with the same node values. If there is more than one answer, return any of them.

A binary search tree is balanced if the depth of the two subtrees of every node never differs by more than 1.

Example 1:

Input: root = [1,null,2,null,3,null,4,null,null]
Output: [2,1,3,null,null,null,4]
Explanation: This is not the only correct answer, [3,1,4,null,2] is also correct.

Example 2:

Input: root = [2,1,3]
Output: [2,1,3]

Constraints:

The number of nodes in the tree is in the range [1, 104].
1 <= Node.val <= 105

SOLUTION:

# 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 inorder(self, root):
        if root:
            self.inorder(root.left)
            self.tree.append(root.val)
            self.inorder(root.right)

    def arrToTree(self, arr, i, j):
        if i <= j - 1:
            root = TreeNode()
            mid = (i + j) // 2
            root.val = arr[mid]
            root.left = self.arrToTree(arr, i, mid)
            root.right = self.arrToTree(arr, mid + 1, j)
            return root
        return None

    def balanceBST(self, root: TreeNode) -> TreeNode:
        self.tree = []
        self.inorder(root)
        return self.arrToTree(self.tree, 0, len(self.tree))

Smallest String With Swaps

Abhishek Chaudhary — Sun, 19 Jun 2022 01:00:46 +0000

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

Example 1:

Input: s = "dcab", pairs = [[0,3],[1,2]]
Output: "bacd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[1] and s[2], s = "bacd"

Example 2:

Input: s = "dcab", pairs = [[0,3],[1,2],[0,2]]
Output: "abcd"
Explaination:
Swap s[0] and s[3], s = "bcad"
Swap s[0] and s[2], s = "acbd"
Swap s[1] and s[2], s = "abcd"

Example 3:

Input: s = "cba", pairs = [[0,1],[1,2]]
Output: "abc"
Explaination:
Swap s[0] and s[1], s = "bca"
Swap s[1] and s[2], s = "bac"
Swap s[0] and s[1], s = "abc"

Constraints:

1 <= s.length <= 10^5
0 <= pairs.length <= 10^5
0 <= pairs[i][0], pairs[i][1] < s.length
s only contains lower case English letters.

SOLUTION:

from collections import defaultdict

class Solution:
    def dfs(self, graph, node, visited):
        for j in graph[node]:
            if j not in visited:
                visited.add(j)
                self.dfs(graph, j, visited)

    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        op = list(s)
        graph = defaultdict(list)
        for a, b in pairs:
            graph[a].append(b)
            graph[b].append(a)
        globalvisited = set()
        for x in graph:
            if x not in globalvisited:
                currvisited = {x}
                self.dfs(graph, x, currvisited)
                indexes = sorted(currvisited)
                indexes_asc = sorted(currvisited, key = lambda p: s[p])
                n = len(indexes)
                for i in range(n):
                    op[indexes[i]] = s[indexes_asc[i]]
                globalvisited.update(currvisited)
        return "".join(op)

Crawler Log Folder

Abhishek Chaudhary — Sun, 19 Jun 2022 00:30:36 +0000

The Leetcode file system keeps a log each time some user performs a change folder operation.

The operations are described below:

"../" : Move to the parent folder of the current folder. (If you are already in the main folder, remain in the same folder).
"./" : Remain in the same folder.
"x/" : Move to the child folder named x (This folder is guaranteed to always exist).

You are given a list of strings logs where logs[i] is the operation performed by the user at the ith step.

The file system starts in the main folder, then the operations in logs are performed.

Return the minimum number of operations needed to go back to the main folder after the change folder operations.

Example 1:

Input: logs = ["d1/","d2/","../","d21/","./"]
Output: 2
Explanation: Use this change folder operation "../" 2 times and go back to the main folder.

Example 2:

Input: logs = ["d1/","d2/","./","d3/","../","d31/"]
Output: 3

Example 3:

Input: logs = ["d1/","../","../","../"]
Output: 0

Constraints:

1 <= logs.length <= 103
2 <= logs[i].length <= 10
logs[i] contains lowercase English letters, digits, '.', and '/'.
logs[i] follows the format described in the statement.
Folder names consist of lowercase English letters and digits.

SOLUTION:

class Solution:
    def minOperations(self, logs: List[str]) -> int:
        ctr = 0
        for log in logs:
            if log == "../":
                ctr =  max(ctr - 1, 0)
            elif log != "./":
                ctr += 1
        return ctr

Remove Palindromic Subsequences

Abhishek Chaudhary — Sun, 19 Jun 2022 00:00:45 +0000

You are given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string if it is generated by deleting some characters of a given string without changing its order. Note that a subsequence does not necessarily need to be contiguous.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: s is already a palindrome, so its entirety can be removed in a single step.

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "".
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "".
Remove palindromic subsequence "baab" then "b".

Constraints:

1 <= s.length <= 1000
s[i] is either 'a' or 'b'.

SOLUTION:

class Solution:
    def removePalindromeSub(self, s: str) -> int:
        if s == s[::-1]:
            return 1
        return 2

Asteroid Collision

Abhishek Chaudhary — Sat, 18 Jun 2022 23:30:38 +0000

We are given an array asteroids of integers representing asteroids in a row.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Example 1:

Input: asteroids = [5,10,-5]
Output: [5,10]
Explanation: The 10 and -5 collide resulting in 10. The 5 and 10 never collide.

Example 2:

Input: asteroids = [8,-8]
Output: []
Explanation: The 8 and -8 collide exploding each other.

Example 3:

Input: asteroids = [10,2,-5]
Output: [10]
Explanation: The 2 and -5 collide resulting in -5. The 10 and -5 collide resulting in 10.

Constraints:

2 <= asteroids.length <= 104
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

SOLUTION:

class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        n = len(asteroids)
        stack = []
        survivors = set()
        for i in range(n):
            if asteroids[i] > 0:
                stack.append(i)
            else:
                while len(stack) > 0 and abs(asteroids[stack[-1]]) < abs(asteroids[i]):
                    stack.pop()
                if len(stack) > 0:
                    if abs(asteroids[stack[-1]]) <= abs(asteroids[i]):
                        stack.pop()
                else:
                    survivors.add(i)
        for i in stack:
            survivors.add(i)
        return [asteroids[i] for i in range(n) if i in survivors]

Check Whether Two Strings are Almost Equivalent

Abhishek Chaudhary — Sat, 18 Jun 2022 23:00:46 +0000

Two strings word1 and word2 are considered almost equivalent if the differences between the frequencies of each letter from 'a' to 'z' between word1 and word2 is at most 3.

Given two strings word1 and word2, each of length n, return true if word1 and word2 are almost equivalent, or false otherwise.

The frequency of a letter x is the number of times it occurs in the string.

Example 1:

Input: word1 = "aaaa", word2 = "bccb"
Output: false
Explanation: There are 4 'a's in "aaaa" but 0 'a's in "bccb".
The difference is 4, which is more than the allowed 3.

Example 2:

Input: word1 = "abcdeef", word2 = "abaaacc"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:

'a' appears 1 time in word1 and 4 times in word2. The difference is 3.
'b' appears 1 time in word1 and 1 time in word2. The difference is 0.
'c' appears 1 time in word1 and 2 times in word2. The difference is 1.
'd' appears 1 time in word1 and 0 times in word2. The difference is 1.
'e' appears 2 times in word1 and 0 times in word2. The difference is 2.
'f' appears 1 time in word1 and 0 times in word2. The difference is 1.

Example 3:

Input: word1 = "cccddabba", word2 = "babababab"
Output: true
Explanation: The differences between the frequencies of each letter in word1 and word2 are at most 3:

'a' appears 2 times in word1 and 4 times in word2. The difference is 2.
'b' appears 2 times in word1 and 5 times in word2. The difference is 3.
'c' appears 3 times in word1 and 0 times in word2. The difference is 3.
'd' appears 2 times in word1 and 0 times in word2. The difference is 2.

Constraints:

n == word1.length == word2.length
1 <= n <= 100
word1 and word2 consist only of lowercase English letters.

SOLUTION:

from collections import Counter

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        ctr1 = Counter(word1)
        ctr2 = Counter(word2)
        for c in "abcdefghijklmnopqrstuvwxyz":
            if abs(ctr1[c] - ctr2[c]) > 3:
                return False
        return True