Backspace String Compare

Solution (build string ❌) Time: O(N) Space: O(N) class Solution: def backspaceCompare(self, S: str, T: str) -> bool: res_1 = self.helper(S) res_2 = self.helper(T) return len(res_1) == len(res_2) and res_1 == res_2 def helper(self, s): stack = [] for c in s: if c != "#": stack.append(c) else: if len(stack) > 0: stack.pop() return "".join(stack) s Solution (two pointers 👍🏼) Time: O(N) Space: O(1) from itertools import zip_longest class Solution: def backspaceCompare(self, S: str, T: str) -> bool: return all( a == b for a, b in zip_longest(self.

by lek tin in "algorithm" access_time 1-min read

Flatten 2d Vector

Design and implement an iterator to flatten a 2d vector. It should support the following operations: next and hasNext. Example Vector2D iterator = new Vector2D([[1,2],[3],[4]]); iterator.next(); // return 1 iterator.next(); // return 2 iterator.next(); // return 3 iterator.hasNext(); // return true iterator.hasNext(); // return true iterator.next(); // return 4 iterator.hasNext(); // return false Notes Please remember to RESET your class variables declared in Vector2D, as static/class variables are persisted across multiple test cases.

by lek tin in "algorithm" access_time 2-min read

Interval List Intersections

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b. The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.

by lek tin in "algorithm" access_time 2-min read

String Compression

Given an array of characters, compress it in-place. The length after compression must always be smaller than or equal to the original array. Every element of the array should be a character (not int) of length 1. After you are done modifying the input array in-place, return the new length of the array. Follow up Could you solve it using only O(1) extra space? Example 1 Input: ["a","a","b","b","c","c","c"] Output: Return 6, and the first 6 characters of the input array should be: ["a","2","b","2","c","3"] Explanation: "aa" is replaced by "a2".

by lek tin in "algorithm" access_time 2-min read

Reverse Words in a String Iii

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1 Input: "Let's take LeetCode contest" Output: "s'teL ekat edoCteeL tsetnoc" Note In the string, each word is separated by single space and there will not be any extra space in the string. Solution class Solution: def reverseWords(self, s: str) -> str: N = len(s) start = 0 s = list(s) res = "" while start < N: while start < N and s[start] == " ": start += 1 stop = start while stop < N and s[stop] !

by lek tin in "algorithm" access_time 1-min read

Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original. Example Input: s = "abcdefg", k = 2 Output: "bacdfeg" Restrictions: The string consists of lower English letters only.

by lek tin in "algorithm" access_time 1-min read

Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[]. Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. You may assume all the characters consist of printable ascii characters. Example 1 Input: ["h","e","l","l","o"] Output: ["o","l","l","e","h"] Example 2 Input: ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"] Solution class Solution: def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead.

by lek tin in "algorithm" access_time 1-min read

Optimal Utilization

Given 2 lists a and b. Each element is a pair of integers where the first integer represents the unique id and the second integer represents a value. Your task is to find an element from a and an element form b such that the sum of their values is less or equal to target and as close to target as possible. Return a list of ids of selected elements. If no pair is possible, return an empty list.

by lek tin in "algorithm" access_time 3-min read

Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order. Example 1 Input: [-4,-1,0,3,10] Output: [0,1,9,16,100] Example 2 Input: [-7,-3,2,3,11] Output: [4,9,9,49,121] Note 1 <= A.length <= 10000 -10000 <= A[i] <= 10000 A is sorted in non-decreasing order. Solution class Solution: def sortedSquares(self, A: List[int]) -> List[int]: result = A[:] leftPtr, rightPtr = 0, len(A)-1 i = 0 while leftPtr <= rightPtr: i += 1 if abs(A[leftPtr]) <= abs(A[rightPtr]): result[-i] = A[rightPtr] * A[rightPtr] rightPtr -= 1 else: result[-i] = A[leftPtr] * A[leftPtr] leftPtr += 1 return result

by lek tin in "algorithm" access_time 1-min read

Subarray Product Less Than K

Your are given an array of positive integers nums. Count and print the number of (contiguous) subarrays where the product of all the elements in the subarray is less than k. Example 1 Input: nums = [10, 5, 2, 6], k = 100 Output: 8 Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.

by lek tin in "algorithm" access_time 1-min read