Array

Merge two sorted arrays

• Merge two arrays to one (from the end)

Intersection of two arrays

• HashSet: O(m+n) time, O(m+n) space
• Merge two sorted arrays: O(mlgm + nlgn) time, O(1) space
• Binary Search: O(mlgm + nlgn) time, O(1) space

Find the Kth largest number

• Quick Select Template

  public int partition(int[] nums, int l, int r) 
    int left = l, right = r;
    int pivotIndex = (l+r)/2; //(int)(Math.random() * (j-i)) + i;
    swap(nums, left, pivotIndex);
    int pivot = nums[left];
  
    while (left < right) {
        while (left < right && nums[right] >= pivot) {
            right--;
        }
        nums[left] = nums[right];
        while (left < right && nums[left] <= pivot) {
            left++;
        }
        nums[right] = nums[left];
    }
  
    nums[left] = pivot;
    return left;
  }
  

  public int kthLargestElement(int k, int[] nums) {
    if (nums == null || nums.length < k) {
        return 0;
    }
  
    int start = 0;
    int end = nums.length-1;
    int index = nums.length-k;
    while(start < end) {
        int pivot = partition(nums, start, end);
        if (pivot < index) {
            start = pivot+1;
        } else if (pivot > index) {
            end = pivot-1;
        } else {
            return nums[pivot];
        }
    }
    return nums[start];
  }
  

Median of two sorted arrays

• The nature of binary search: reduce half
• Compare the item on the position of k/2
• Cut the k/2 items in the array which the k/2 item is smaller
• If one of the arrays is less than k/2, then cut the one which has more items
• change the start index and modify k
• stop: one of the arrays is empty or k equals 1

Prefix Sum

prefixSum[i] = sum(A[0]~A[i]) convert prefix sum to subarray sum：subarray[i, j] = prefixSum[j] - prefixSum[i - 1]

Two Pointers

Scan: scan from the left and right side of the line

Two pointers: start-end pointers, two forward pointers

Partition Array