Leetcode Weekly Digest - June 10th

Preface

Learning and practicing to solve leetcode problems is essential in job interviews for SDE and MLE positions. Since I plan to seek opportunities in the U.S, I will put the log of leetcode problems entirely in English. Hopefully, this process can help me perform better in future interviews.

I am also taking 15513: Introduction to Computer Systems as a summer course at CMU, where I picked up C language learned in CS250: Computer Architecture from Duke Univ. Thus I decided to use C language over Python to leetcode problem solutions.

Thanks to programmer Carl, I am referring to his website for leetcode training. The topics I am working on this week are binary search and remove element.

Binary Search

704. Binary Search

There are mainly two implementations of binary search in this problem, with the difference in can l equal to r.

Close interval [l, r]

In this case, l == r is valid, meaning that l, r, mid points to the same address. Below is the C implementation using close intervals.

int search(int* nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;
    while (l <= r) {
        int mid = l + r >> 1;               // may overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

Open interval [l, r)

In this case, l == r is invalid. There are some nuances compared to the previous scenario.

int search(int* nums, int numsSize, int target) {
    int l = 0, r = numsSize;
    while (l < r) {
        int mid = l + r >> 1;               // int mid = l + (r - l >> 1);
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    return -1;
}

Although the above solutions pass all cases in leetcode, they have one potential problem. int mid = l + r >> 1 assumes that their sum is not overflowed. This assumption may not be true for some obvious cases. Therefore, a substitution for this would look similar to int mid = l + (r - l >> 1);

Related problems

35. Search Insert Position

This similar problem can apply the binary search implementation from last problem.

int searchInsert(int* nums, int numsSize, int target){
    int l = 0, r = numsSize - 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (nums[mid] == target) return mid;
        if (nums[mid] > target) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}

I suggest you work on the binary searching process on draft papers first, and you will discover that the stopping position will be the l index.

Remove Element

27. Remove Element

This category of problems can be easily tackled by Two Pointers.

int removeElement(int* nums, int numsSize, int val){
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; ++fastIndex) {
        if (nums[fastIndex] != val) {
            nums[slowIndex++] = nums[fastIndex];            // usage of slowIndex++
        }
    }
    return slowIndex;
}

The solution is quite simple. A trick in line 5 is slowIndex++, which returns the unchanged value but is already self-incremented. For more details in difference between i++ and ++i, refer to Stackoverflow: What is the difference between i++ and ++i.

Related Problems

Remove Duplicates from Sorted Array

26. Remove Duplicates from Sorted Array

With two pointers, my original solution looks like this:

int removeDuplicates(int* nums, int numsSize){
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; ++fastIndex) {
        if (nums[slowIndex] != nums[fastIndex]) {
            int backtrace = fastIndex - 1;
            while (backtrace > slowIndex) {
                nums[backtrace--] = nums[fastIndex];
            }
            slowIndex = backtrace + 1;
        }
    }
    return slowIndex+1;
}

As you can see, I created an int backtrace and loop backward to replace duplicates. It turned out unnecessary because backtracing can be integrated into the onwards loop. The optimized version looks like this:

int removeDuplicates(int* nums, int numsSize){
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; ++fastIndex) {
        if (nums[slowIndex] != nums[fastIndex]) {
            nums[++slowIndex] = nums[fastIndex];
        }
    }
    return ++slowIndex;
}

Again, ++slowIndex used the trick mentioned above. Definitely check this out if you do not have a clear idea about the difference between i++ and ++i.

Move Zeroes

283. Move Zeroes

Unlike the previous two problems, this asks you to move 0 backward and return the whole array. We still go with two pointer method, but with caution. Normally, our two-pointer solution looks like this:

void moveZeroes(int *nums, int numsSize) {
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; ++fastIndex) {
        if (nums[fastIndex]) {
            nums[slowIndex++] = nums[fastIndex];
            nums[fastIndex] = 0;
        }
    }
}

However, this failed an edge case. Assume the input as the following,

[5]

the output would be [0]. Therefore, we only assign fastIndex to 0 if slowIndex and fastIndex point to different addresses. A fixed solution looks like this:

void moveZeroes(int *nums, int numsSize) {
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; ++fastIndex) {
        if (nums[fastIndex]) {
            nums[slowIndex] = nums[fastIndex];
            if (slowIndex ^ fastIndex) nums[fastIndex] = 0;
            slowIndex++;
        }
    }
}

Summary

All problems above are labeled as easy, but they are a good starting point with programming in C.