General

Replace and remove

Given a char array, replace 'a' to 2 'd', Remove 'b', size is the size of character array

• Forward and backward iteration

public static int replaceAndRemove(int size, char[] s) {
  int countA = 0, writeIndex = 0;
  // Forward iteration: remove 'b', count the number of 'a'
  for (int i = 0; i < size; i++){
    if (s[i] != 'b'){
      s[writeIndex++] = s[i];
    }
    if (s[i] == 'a'){
      countA++;
    }
  }

  writeIndex -= 1;
  int currentIndex = writeIndex;
  writeIndex += countA;
  int finalSize = writeIndex + 1;

    // Backward: repalce 'a' with 2 'd's
  while(currentIndex >= 0){
    if (s[currentIndex] == 'a'){
      s[writeIndex--] = 'd';
      s[writeIndex--] = 'd';
    }else{
      s[writeIndex--] = s[currentIndex];
    }
    currentIndex--;
  }
  return finalSize;
}

Rotated Array

Increasing Sorted Array with break point

• O(1) space, O(n) time

• 三步翻轉

  

for (int i = 1; i < nums.size(); i++){
    if (nums.get(i-1) > nums.get(i)){
        Collections.reverse(nums.subList(0, i));
        Collections.reverse(nums.subList(i, nums.size()));
        Collections.reverse(nums);
        break;
    }
}

4. Median of 2 Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays.

Example Given A=[1,2,3,4,5,6] and B=[2,3,4,5], the median is 3.5.

Given A=[1,2,3] and B=[4,5], the median is 3

1. k = (m+n)/2, 想法：找到合併後從小到大第k個element

2. 遞回比較兩個arrays中第k/2個ele, 其中一個array前進k/2 idx

3. k=1時就是答案

def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    n = len(nums1) + len(nums2)
    if n%2:
        return self.findKLargest(nums1, 0, nums2, 0, n//2+1)
    else:
        return (self.findKLargest(nums1, 0, nums2, 0, n//2) + self.findKLargest(nums1, 0, nums2, 0, n//2+1))/2
    
def findKLargest(self, nums1, idx1, nums2, idx2, k):
    if idx1 >= len(nums1):
        return nums2[idx2+k-1]
    if idx2 >= len(nums2):
        return nums1[idx1+k-1]
    if k == 1:
        return min(nums1[idx1], nums2[idx2])
    
    n = k//2
    n1 = nums1[idx1+n-1] if idx1+n-1 < len(nums1) else float('inf')
    n2 = nums2[idx2+n-1] if idx2+n-1 < len(nums2) else float('inf')
    
    if n1 < n2:
        return self.findKLargest(nums1, idx1+n, nums2, idx2, k-n)
    else:
        return self.findKLargest(nums1, idx1, nums2, idx2+n, k-n)

54 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

• Layer by layer

def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
    if not matrix: return []
    ans = []
    
    r1, r2 = 0, len(matrix)-1
    c1, c2 = 0, len(matrix[0])-1
    
    while r1<=r2 and c1<=c2:
        for k in range(c1, c2+1): ans.append(matrix[r1][k])
        for k in range(r1+1, r2+1): ans.append(matrix[k][c2])
        if r1<r2 and c1<c2:
            for k in range(c2-1, c1, -1): ans.append(matrix[r2][k])
            for k in range(r2, r1, -1): ans.append(matrix[k][c1])
            
        r1+=1
        r2-=1
        c1+=1
        c2-=1
    
    return ans

Sort By Matrix Layer

Sort the matrix from out layer to inner layer, and put the array in clockwise

def borderSort(matrix):
    n = len(matrix)
    ans = [[0]*n for _ in range(n)]
    
    def getArray(idx):
        nonlocal matrix, n
        arr = []
        arr.extend(matrix[idx][idx: n-idx])
        arr.extend(matrix[n-1-idx][idx: n-idx])
        for i in range(idx+1, n-idx-1):
            for j in (idx, n-idx-1):
                arr.append(matrix[i][j])
        arr.sort()
        return arr
    
    def helper(ans, idx):
        nonlocal n
        sortArray = getArray(idx)
        
        iter = 0
        for j in range(idx, n): 
            ans[idx][j] = sortArray[iter]
            iter += 1
        for i in range(idx+1, n-idx-1):
            ans[i][idx-1] = sortArray[iter]
            iter +=1
        for j in range(n-1-idx, idx-1, -1):
            ans[n-idx-1][j] = sortArray[iter]
            iter+=1
        for i in range(n-idx-2, idx, -1):
            ans[i][idx] = sortArray[iter]
            iter+=1
            
   # if odd, don't need to consider innest layer
    for i in range(n//2):
        helper(ans, i)
    return ans

test = [[9,7,4],
        [-6,0,-2],
        [-4,-5,1]]

print(borderSort(test))

31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

• From rhs, find the pivot smaller than previous number

• The rhs array is in decreasing order

• Swap pivot with first greater number among reversed number

• Reverse array after pivot

def nextPermutation(self, nums: List[int]) -> None:
    point = -1
    for i in range(len(nums)-2, -1, -1):
        if nums[i] < nums[i+1]:
            point = i
            break
    
    if point != -1:
        for i in range(len(nums)-1, -1, -1):
            if nums[i] > nums[point]:
                self.swap(nums, point, i)
                break
    
    self.reverse(nums, point+1, len(nums)-1)
    
def swap(self, nums, i, j):
    tmp = nums[i]
    nums[i] = nums[j]
    nums[j] = tmp
    
def reverse(self, nums, i, j):
    while i<j:
        self.swap(nums, i, j)
        i+=1
        j-=1

41. First Missing Positive

Including zero and negative number

# 將數字排到正確的index上
# [3, 4, -1, 1, 8] -> [1, -1, 3, 4, 8] => 如果 num[i] != i+1, 代表這個數字缺失 eg: 2
# 
# for loop list, then while loop:
# In place swap, num 不為zero或負數, 也不可能大於n+1, skip => 只要碰到負數 or 大於n的數字就失敗
# while loop: if nums[i] > 0 && nums[i]<=n && nums[nums[i]-1] != nums[i], swap
# https://leetcode.windliang.cc/leetCode-41-First-Missing-Positive.html

def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)
    
    def swap(nums, i, j):
        tmp = nums[i]
        nums[i] = nums[j]
        nums[j] = tmp
        
    
    for i in range(n):
        # 更新當前的數字到正確index上
        while(nums[i] > 0 and nums[i] <= n and nums[nums[i]-1] != nums[i]):
            swap(nums, i, nums[i]-1)
            
    for i in range(n):
        if nums[i] != i+1:
            return i+1
    
    #如果都在正確位置上，則missing n+1
    return n+1

First missing number in consecutive array

Binary search, use array index, O(logN)

def f(arr):
  l, r = 0, len(arr)
  while l < r:
    mid = (l + r) // 2
    if arr[mid] == mid + 2:
      r = mid
    else:
      l = mid + 1
      
  # no missing number
  if l == len(arr): return len(arr) + 1
  return l + 1


print(f([1,2,4,5,6]))
print(f([1,2,3]))
print(f([1]))

1060. Missing Element in Sorted Array

Given a sorted array A of unique numbers, find the K-th missing number starting from the leftmost number of the array.

def missingElement(self, nums: List[int], k: int) -> int:
    pre = nums[0]
    
    for n in nums[1:]:
        dist = n - pre - 1
        if dist >= k:
            return pre + k
        else:
            k -= dist
        pre = n
        
    return nums[-1] + k

128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence

Hash First ensuring the number immediately preceding the current number is not present, after that lookup subsequent number in set and count the sequence length.

• Time Looks like O(n^2), but actually O(n)

• Space O(n)

def longestConsecutive(self, nums: List[int]) -> int:
    if not nums: return 0
    ans = 0  
    s = set(nums)
    
    for n in nums:
        if n-1 not in s:
            cur = n
            count = 1
            while cur+1 in s:
                cur += 1
                count+=1  
            ans = max(ans, count)       
    return ans

565. Array Nesting

A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... }

def arrayNesting(self, nums: List[int]) -> int:
    visit = set()
    res = 0
    for i, n in enumerate(nums):
        if n not in visit:
            visit.add(i)
            count = 1
            idx = n
            while idx not in visit:
                visit.add(idx)
                idx = nums[idx]
                count += 1
            res = max(res, count)
    return res

300 Longest Increasing Subsequence

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.

Example

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3

For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

• State: f[i] = 第i+1根木樁的LIS

• Init: f[0...i] = 1

• function: f[i] = max{f[j]+1}, j<i && num[j]<num[i]

• Ans: max{f[0...i]}

O(n^2)

def lengthOfLIS(self, nums: List[int]) -> int:
    if not nums: return 0
    ans = 1
    dp = [1] * len(nums)
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j]+1)
                
        ans = max(ans, dp[i])
        
    return ans

Greedy + DP: O(nlogn)

建立一個空list, 這個list裡面的數字都要越小越好(increase 的機會越大) 遍歷nums, 只要 n 要append 到 list 最後，update length, 其它則更新到相對應位置上。Array 裡的答案不是正確的排序答案，但長度是對的

[4, 2, 4, 5, 3, 7] => [2, 3, 5, 7]

from bisect import bisect_left
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        
        li = []
        for n in nums:
            pos = bisect_left(li, n)
            if pos == len(li):
                li.append(n)
            else:
                li[pos] = n
        
        return len(li)

611. Triangle Count

Given an array of integers, how many three numbers can be found in the array, so that we can build a triangle whose three edges length is the three numbers that we find?

Example Given [4, 6, 3, 7] Ans [[3,4,6], [4,6,7], [3,6,7]]

def triangleNumber(self, nums: List[int]) -> int:
    nums.sort()
    count = 0
    
    for i in range(2, len(nums)):
        count += self.helper(i, nums)
        
    return count

def helper(self, idx, nums):
    count = 0
    left, right = 0, idx-1
    
    while left < right:
        if nums[left] + nums[right] <= nums[idx]:
            left += 1
        else:
        # left 到 right - 1 中間任一個數選一個跟 right 搭配都滿足條件
            count += right - left
            right -= 1
    return count