Sorting and Searching

These problems deal with sorting or searching in a sorted structure.

We recommend First Bad Version as a great introduction to a very important algorithm.

88. Merge Sorted Array

leetcode.com/problems/merge-sorted-array/

Solution

Approach 1 : Merge and sort

Intuition

The naive approach would be to merge both lists into one and then to sort. It's a one line solution (2 lines in Java) with a pretty bad time complexity \mathcal{O}((n + m)\log(n + m)) because here one doesn't profit from the fact that both arrays are already sorted.

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n);
    Arrays.sort(nums1);
  }
}

Implementation

Time complexity : \mathcal{O}((n + m)\log(n + m)).
Space complexity : \mathcal{O}(1).

Approach 2 : Two pointers / Start from the beginning

Intuition

Typically, one could achieve \mathcal{O}(n + m) time complexity in a sorted array(s) with the help of two pointers approach.

The straightforward implementation would be to set get pointer p1 in the beginning of nums1, p2 in the beginning of nums2, and push the smallest value in the output array at each step.

Since nums1 is an array used for output, one has to keep first m elements of nums1 somewhere aside, that means \mathcal{O}(m) space complexity for this approach.

Implementation

Complexity Analysis

Time complexity : \mathcal{O}(n + m).
Space complexity : \mathcal{O}(m).

Approach 3 : Two pointers / Start from the end

Intuition

Approach 2 already demonstrates the best possible time complexity \mathcal{O}(n + m) but still uses an additional space. This is because one has to keep somewhere the elements of array nums1 while overwriting it starting from the beginning.

What if we start to overwrite nums1 from the end, where there is no information yet? Then no additional space is needed.

The set pointer p here is used to track the position of an added element.

Implementation

3 / 6

class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    // Make a copy of nums1.
    int [] nums1_copy = new int[m];
    System.arraycopy(nums1, 0, nums1_copy, 0, m);

    // Two get pointers for nums1_copy and nums2.
    int p1 = 0;
    int p2 = 0;

    // Set pointer for nums1
    int p = 0;

    // Compare elements from nums1_copy and nums2
    // and add the smallest one into nums1.
    while ((p1 < m) && (p2 < n))
      nums1[p++] = (nums1_copy[p1] < nums2[p2]) ? nums1_copy[p1++] : nums2[p2++];

    // if there are still elements to add
    if (p1 < m)
      System.arraycopy(nums1_copy, p1, nums1, p1 + p2, m + n - p1 - p2);
    if (p2 < n)
      System.arraycopy(nums2, p2, nums1, p1 + p2, m + n - p1 - p2);
  }
}

Complexity Analysis

Time complexity : \mathcal{O}(n + m).
Space complexity : \mathcal{O}(1).

278. First Bad Version

leetcode.com/problems/first-bad-version/

Summary

This is a very simple problem. There is a subtle trap that you may fall into if you are not careful. Other than that, it is a direct application of a very famous algorithm.

Solution

Approach #1 (Linear Scan) [Time Limit Exceeded]

The straight forward way is to brute force it by doing a linear scan.

Complexity analysis

Time complexity : O(n). Assume that isBadVersion(version) takes constant time to check if a version is bad. It takes at most n - 1 checks, therefore the overall time complexity is O(n).
Space complexity : O(1).

Approach #2 (Binary Search) [Accepted]

It is not difficult to see that this could be solved using a classic algorithm - Binary search. Let us see how the search space could be halved each time below.

Scenario #1: isBadVersion(mid) => false 1 2 3 4 5 6 7 8 9 G G G G G G B B B G = Good, B = Bad | | | left mid right

Let us look at the first scenario above where isBadVersion(mid) \Rightarrow false. We know that all versions preceding and including mid are all good. So we set left = mid + 1 to indicate that the new search space is the interval [mid + 1, right] (inclusive).

Scenario #2: isBadVersion(mid) => true 1 2 3 4 5 6 7 8 9 G G G B B B B B B G = Good, B = Bad | | | left mid right

The only scenario left is where isBadVersion(mid) \Rightarrow true. This tells us that mid may or may not be the first bad version, but we can tell for sure that all versions after mid can be discarded. Therefore we set right = mid as the new search space of interval [left,mid] (inclusive).

In our case, we indicate left and right as the boundary of our search space (both inclusive). This is why we initialize left = 1 and right = n. How about the terminating condition? We could guess that left and right eventually both meet and it must be the first bad version, but how could you tell for sure?

The formal way is to prove by induction, which you can read up yourself if you are interested. Here is a helpful tip to quickly prove the correctness of your binary search algorithm during an interview. We just need to test an input of size 2. Check if it reduces the search space to a single element (which must be the answer) for both of the scenarios above. If not, your algorithm will never terminate.

If you are setting mid = \frac{left + right}{2}, you have to be very careful. Unless you are using a language that does not overflow such as Python, left + right could overflow. One way to fix this is to use left + \frac{right - left}{2} instead.

If you fall into this subtle overflow bug, you are not alone. Even Jon Bentley's own implementation of binary search had this overflow bug and remained undetected for over twenty years.

public int firstBadVersion(int n) {
    int left = 1;
    int right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

Complexity analysis