[LeetCode] 2825. Make String a Subsequence Using Cyclic Increments

Problem : https://leetcode.com/problems/make-string-a-subsequence-using-cyclic-increments/

There are 2 important rules:

We only need to increase cyclically the character of str1 to match with a character of str2.

We only need to check if str2 is one of subsequences of str1. So we can use 2 pointers to compare the charaters of str1 and str2. When str1[i] == str2[j], we can move the 2 pointers forward. Otherwise, we just move forward the pointer i.

class Solution {

    public boolean canMakeSubsequence(String str1, String str2) {
        int M = str1.length(), N = str2.length();             
        int i = 0, j = 0;
        
        while (i < M && j < N) {
            int a = str1.charAt(i) - 'a', b = str2.charAt(j) - 'a';
            
            if (a == b || (a + 1) % 26 == b) {
                i += 1;
                j += 1;
            } else {
                i += 1;
            }
        }
        
        // Check if all characters of str2 have been matched
        return j == N;
    }
}

[LeetCode] 1861. Rotating the Box

 Problem : https://leetcode.com/problems/rotating-the-box/

This problem is similar to removing zeros from the input array.

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        
        ROW = len(box)
        COLUMN = len(box[0])
        
        for y in range(ROW):
            i = COLUMN - 1
            for x in reversed(range(COLUMN)):
                if box[y][x] == '#':
                    box[y][i] = box[y][x]
                    i -= 1
                elif box[y][x] == '*':
                
                	# set positions between the last empty and the obstacle as empty spaces.
                    while i > x:
                        box[y][i] = '.'
                        i -= 1
                    
                    while i >= 0 and box[y][i] == '*':
                        i -= 1
            
            # set the rest positions as empty spaces
            while i >= 0:
                box[y][i] = '.'
                i -= 1
        
        # rotate the board 90 degrees clockwise
        result = [[''] * ROW for _ in range(COLUMN)]
        
        for y in range(ROW):
            for x in range(COLUMN):
                result[x][ROW-y-1]= box[y][x]
        
        return result

[LeetCode] 388. Longest Absolute File Path

 Problem : https://leetcode.com/problems/longest-absolute-file-path/

Use two pointers approach to parse directory / file name.

Use stack to maintain the paths to current files. We need to pop directory from stack is depth of current file is less than the directory on the top of the stack.

Time Complexity = O ( N ).   N = len(input).  As the code only visit each character in the input once.

class Solution:
    def lengthLongestPath(self, input: str) -> int:
        if not input: return 0 
        
        result = 0
        
        # Stack<[fileName, depth]>
        stack = []
            
        left = right  = 0
        depth = 0
        
        while right < len(input):
            if input[right] == '\n' or right == len(input) - 1:
                # pop back to the depth of current file
                while stack and stack[-1][1] >= depth:
                    stack.pop()
                
                # find current file name
                file = input[left:right] if input[right] == '\n' else input[left:right+1]
                stack.append([file, depth])
                
                # calculate the full path to a file
                if '.' in input[left:right]:
                    paths = '/'.join([a for a, _ in stack])
                    result = max(result, len(paths))
                
                # calculate next depth
                right += 1
                left = right
                depth = 0
                
                while right < len(input) and input[right] == '\t':
                    depth += 1
                    right += 1
                
                left = right
            else:
                right += 1
        
        return result

[LeetCode] 350. Intersection of Two Arrays II

Problem : https://leetcode.com/problems/intersection-of-two-arrays-ii/

2 pointers solution:  

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                result.append(nums1[i])
                i += 1
                j += 1
        
        return result

When elements are stored on disk, use external sort algorithm to sort items first. Then use this 2 pointers approach to find the intersection.

Hash table based solutin:

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        counter1 = Counter(nums1)
        counter2 = Counter(nums2)
        
        result = []
        
        for k, v1 in counter1.items():
            v2 = counter2.get(k, 0)
            
            if min(v1, v2):
                result += [k] * min(v1, v2)
        
        return result

Edited on 09/17/2021. Update a simpler hash table based solution.

[LeetCode] 349. Intersection of Two Arrays

 Problem : https://leetcode.com/problems/intersection-of-two-arrays/

Binary search solution: 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        
        def bsearch(nums, target):
            left, right = 0, len(nums)
            
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] == target:
                    return True
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return False
        
        result = []
        
        if len(nums1) > len(nums2) : nums1, nums2 = nums2, nums1
        
        nums1.sort()
        nums2.sort()
        
        for i, n in enumerate(nums1):
            if i - 1 >= 0 and nums1[i] == nums1[i-1]:
                continue
            
            if bsearch(nums2, n):
                result.append(n)
            
        
        return result

2 pointers solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        result = []
        
        i = j = 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                if not result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
        
        return result

Hash table based solution:

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        seen = defaultdict(lambda : [0, 0])
        
        for n in nums1:
            seen[n][0] += 1
        
        for n in nums2:
            seen[n][1] += 1
            
        
        return filter(lambda n : seen[n][0] >= 1 and seen[n][1] >= 1, seen.keys())

[LeetCode] 345. Reverse Vowels of a String

 Problem : https://leetcode.com/problems/reverse-vowels-of-a-string/

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set(['a', 'A', 'e', 'E', 'i', 'I', 'o', 'O', 'u', 'U'])
        result = [w for w in s]
        
        i, j = 0, len(s)-1
        
        while i <= j:
            if result[i] not in vowels:
                i += 1
            elif result[j] not in vowels:
                j -= 1
            else:
                result[i], result[j] = s[j], s[i]
                i += 1
                j -= 1
           
        return "".join(result)

[LeetCode] 344. Reverse String

 Problem : https://leetcode.com/problems/reverse-string/

An uncommon 2 pointers approach.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        N = len(s)
        for i in range(N//2):
            j = N - i - 1
            s[i], s[j] = s[j], s[i]

[LeetCode] 283. Move Zeroes

 Problem : https://leetcode.com/problems/move-zeroes/

Use 2 pointers approach.  The slow pointer moves only when num != 0. The fast pointer moves every time. 

Time Complexity = O ( N )

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        i = j = 0
        
        while j < len(nums):
            if nums[j] != 0:
                nums[i] = nums[j]
                i += 1
            
            j += 1
            
        while i < len(nums):
            nums[i] = 0
            i += 1

Another solution similar to bubble-sort. Time Complexity = O ( N ** 2 )

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        i = 0
        N = len(nums)
        
        while i < N:
            if nums[i] != 0:
                i += 1
                continue

            j = i
            while j + 1 < N:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                j += 1
            
            N -= 1

[LeetCode] 209. Minimum Size Subarray Sum

 Problem : https://leetcode.com/problems/minimum-size-subarray-sum/

Sliding-window approach.

Time Complexity = O ( N )

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        MAX_INT = 2 ** 31 - 1
        result = MAX_INT
        right = 0
        sums = 0
        
        for left in range(len(nums)):
            while right < len(nums) and sums < s:
                sums += nums[right]
                right += 1
            
            if sums >= s:
                result = min(result, right - left)
            
            sums -= nums[left]
        
        return result if result != MAX_INT else 0

[LeetCode] 167. Two Sum II - Input array is sorted

Problem : https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Time Complexity = O ( Log N )

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        
        while left < right:
            tmp = numbers[left] + numbers[right]
            
            if tmp < target:
                left += 1
            elif tmp > target:
                right -= 1
            else:
                return [left+1, right+1]

[LeetCode] 125. Valid Palindrome

Problem : https://leetcode.com/problems/valid-palindrome/

Use two pointers to compare letters from head and tail. And ignore none-alpha-num letter.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
                
            while i < j and not s[j].isalnum():
                j -= 1
                
            if i < j and s[i].lower() != s[j].lower():
                break
            
            i += 1
            j -= 1
       
        return i >= j

[LeetCode] 88. Merge Sorted Array

Problem : https://leetcode.com/problems/merge-sorted-array/

Since nums1 has enough space left to save nums2, which means  len(nums1) > m + n.

We may use the spare spaces from the rare of nums1 to do merging.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        
        i, j = m - 1, n - 1
        p = len(nums1) - 1
        
        while i >= 0 and j >= 0:
            # select the larger number to add to the rear of nums1
            if nums1[i] > nums2[j]:
                nums1[p] = nums1[i]
                i -= 1
            else:
                nums1[p] = nums2[j]
                j -= 1
            
            p -= 1
        
        # add rest number of nums1
        while i >= 0:
            nums1[p] = nums1[i]
            p -= 1
            i -= 1
        
        # add rest number of nums2
        while j >= 0:
            nums1[p] = nums2[j]
            p -= 1
            j -= 1
        
        # move the merged list to the head of nums1
        p += 1
        i = 0
        while i < m + n:
            nums1[i] = nums1[p]
            i += 1
            p += 1
        
        # fill the rest spaces with 0
        while i < len(nums1):
            nums1[i] = 0
            i += 1

[LeetCode] 80. Remove Duplicates from Sorted Array II

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

Uses 2 pointers approach. Pointer j moves 1 step per time. Pointer 'i' moves only when encounter valid character.

Time Complexity : O ( N )

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i, j = 1, 1
        count = 1
        
        while j < len(nums):
            if nums[j] == nums[j-1]:
                count += 1
                
                if count <= 2:
                    # keep 2 duplicate  in maximum
                    nums[i] = nums[j]
                    i += 1
                    j += 1
                else:
                    # skip nums[j] as there are already two duplicated numbers
                    j += 1
            else:
                count = 1
                nums[i] = nums[j]
                i += 1
                j += 1
        
        return i

A much simpler solution of overwritting unwanted letters.

Because it is a sorted array, we only need to compare if current letter is same to letter on last 2nd postion of the wanted array.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = j = 2
        
        while j < len(nums):
            if nums[i-2] == nums[j]:
                j += 1
            else:
                nums[i] = nums[j]
                i += 1
                j += 1
        
        return i

[LeetCode] 75. Sort Colors

Problem : https://leetcode.com/problems/sort-colors/

Counting sort based solution.

Time Complexity : O ( 2N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        colors = [0] * 3
        
        for i in nums:
            colors[i] += 1
        
        j = 0
        for color, count in enumerate(colors):
            for i in range(count):
                nums[j + i] = color
                
            j += count

Two pointers based solution.

Have 'red' pointer moves forward from the first number and 'blue' pointer moves backward from the last number. Iterate from the first number.  If number[i] == 0, swap with red. When number[i] == 2, swap with blue.

Time Complexity : O ( N )

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        def swap(i, j):
            nums[i], nums[j] = nums[j], nums[i]
        
        red, blue = 0, len(nums) - 1
        i = 0
        
        while i <= blue:
            color = nums[i]
            if color == 0:
                swap(i, red)
                red += 1
                i += 1
            elif color == 2:
                swap(i, blue)
                blue -= 1
                # do not increase i
                # need to check the swapped color is red or not
            else:
            	# no need to swap for white color
                i += 1

[LeetCode] 30. Substring with Concatenation of All Words

Problem : https://leetcode.com/problems/substring-with-concatenation-of-all-words/

Because all the words are with same length.  Assume word length is N, the code pickup every substring of length N to check if the substring is in the words array.

Time Complexity : O ( Len(s) *  Len(words) )

Space Complexity:  O ( N )

from collections import defaultdict

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        
        result = []
        
        if not s or not words:
            return result
        
        L = len(words)
        N = len(words[0])
        
        wordCnt = defaultdict(int)
        for w in words:
            wordCnt[w] += 1
            
       
        for i in range(len(s) - N*L + 1):
            # counter of a valid word in range [i : i+N*L+1]
            strCnt = defaultdict(int)
            
            for j in range(L):
                substr = s[i+j*N: i+j*N+N]
                
                if wordCnt[substr] == 0:
                    break
                    
                strCnt[substr] += 1
                
                if strCnt[substr] > wordCnt[substr]:
                    break
            else:
                result.append(i)
                
        return result

[LeetCode] 28. Implement strStr()

Problem : https://leetcode.com/problems/implement-strstr/

This is a pretty naive approach.

Time Complexity :  O (len(haystack) * len(needle) )

Space Complexity:  O ( 1 )

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        
        if not needle:
            return 0
        
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i+j] != needle[j]:
                    break
            else:
                # for-loop completed without break
                return i
        
        return -1

[LeetCode] 27. Remove Element

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

Use 2 pointers approach.

Time Complexity :  O ( N )

Space Complexity : O ( 1 )

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        
        p1, p2 = 0, 0
        
        while p2 < len(nums):
            if nums[p2] != val:
                nums[p1] = nums[p2]
                p1 += 1
            
            p2 += 1
            
        return p1

[LeetCode] 26. Remove Duplicates from Sorted Array

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

Use 2 pointers to traverse the sorted array. p2 moves forward 1 number each time. p1 moves forward only when find unique number.

Time Complexity :  O ( len(nums) )

Space Complexity:  O ( 1 ),   remove duplicated number in space.

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if not nums:
            return 0
        
        p1, p2 = 1, 1
        last = nums[0]
        
        while p2 < len(nums):
            if nums[p2] != last:
                nums[p1] = nums[p2]
                last = nums[p2]
                p1 += 1
            
            p2 += 1
        
        return p1

[LeetCode] 19. Remove Nth Node From End of List

Problem : https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Use 2 pointers to iterate the linked list. The second pointer is n steps behind the first pointer.

Time Complexity :  O ( N )

Space Complexity : O ( 1 )

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        
        # use dummy head node to handle the case that needs to remove the first node.
        dummy = ListNode(0)
        dummy.next = head
        
        p1, p2 = dummy, dummy
        
        while p2 and n >= 0:
            p2 = p2.next
            n -= 1
            
        while p2 and p1:
            p2 = p2.next
            p1 = p1.next
            
        if p1 and p1.next:
            p1.next = p1.next.next
    
        
        return dummy.next

[LeetCode] 18. 4Sum

Problem : https://leetcode.com/problems/4sum/

Similar to 3Sum.

Time Complexity : O ( len(nums) *len(nums) * len(nums)/2 )

Space Complexity: O (len(nums)*len(nums)*len(nums)*len(nums))

 
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        
        nums.sort()
        L = len(nums)
        
        result = []
        
        for i in range(L-3):
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            for j in range(i+1, L-2):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue
                    
                left, right = j + 1, L - 1
                
                while left < right:
                    # early termination
                    if nums[i] + nums[j] + nums[left] + nums[left] > target:
                        break
                        
                    tmp = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if tmp < target:
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                    elif tmp > target:
                         l = right - 1
                         while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                         right = l
                    else:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        
                        k = left + 1
                        while k < right and nums[k] == nums[left]:
                            k += 1
                            continue
                            
                        left = k
                        
                        l = right - 1
                        while l > left and nums[l] == nums[right]:
                            l -= 1
                            continue
                        
                        right = l
                        
        return result