Merge Sort

Summary

In this post, I will introduce some problems using the merge sort technique.

These problems often ask, for an element at index i, how many j are there which satisfies a formula.

OJ

 TrickDifficulty
LC 1395 Enumerate the middle element + Count #elements larger or smaller
6 points
LC 327 Prefix sum + Keep diff in range6-7 points
LC 493 Count #elements larger or smaller6 points
LC 315 Count #elements larger or smaller6 points

Details

The Master Theorem

    \[T(n) = a\times(T(\frac{n}{b})) + f(n)\]

If f(n) is of complexity O(n^{log_b^a}), then T(n) is of complexity O(n^{log_b^a}\times logn)

So in these problems, a key point is to keep the merge part of complexity O(n) by leveraging the sorted property.

Keep Difference in Range

I want to talk about the merge part of LC 327 in this section. Given two sorted array nums[left:mid] and nums[mid+1:right], the problem is to count how many \{i,\ j\} are there, such that

    \[lower <= nums[j] - nums[i] <= upper, i \in [left:mid]\ and\ j \in [mid+1:right]\]

Usually, we will enumerate the left part (or the right part) by i. We use two cursors start and end to store the boundary in the right part to satisfy the above formula.

int mid = left + (right - left) / 2;
int result = merge_sort(left, mid, nums) + merge_sort(mid + 1, right, nums);
int start = mid + 1, end = mid + 1;
for (int i = left; i < mid + 1; ++i) {
    while (start < right + 1 && (long)nums[start] - nums[i] < lower) {
        start++;
    }
    while (end < right + 1 && (long)nums[end] - nums[i] <= upper) {
        end++;
    }
    result += (end - start);
}
inplace_merge(nums.begin() + left, nums.begin() + mid + 1, nums.begin() + right + 1);
return result;

Leave a Reply

Your email address will not be published. Required fields are marked *