Sorting and Searching

#intervals-algorithms

Merge Overlapping Intervals

Problem Statement: Merge Overlapping Intervals

Given an integer array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals. For example \([[1,3],[2,6],[8,10],[15,18]] \to [[1,6],[8,10],[15,18]]\) because \([1,3]\) and \([2,6]\) overlap and merge into \([1,6]\).

Solution: Sort by Start Time and then Linear Scan

Like Minimum Size Subarray Sum , contiguity hints at a linear scan being useful. If we sort intervals by start, then it’s a matter of starting at some intervals[i] and expanding until some intervals[j], \(j > i\) is no longer overlapping.

Problem Statement

There are \(L\) possible land rides and \(W\) possible water rides, with \(1 \le L, W \le 5 \times 10^4\). A tourist must experience exactly one ride from each category, in either order. A ride may be started at its opening time or any later moment. Immediately after finishing one ride, the tourist may board the other if it’s already open or wait until it opens. Return the earliest possible time at which the tourist can finish both rides.

The customer can choose any candy to takeaway for free as long as the cost of the chosen candy is less than or equal to the minimum cost of the two candies bought. Find the minimum cost of buying all the candies.

def minimumCost(self, cost: List[int]) -> int:
    cost.sort(reverse=True)
    minCost = 0
    for i in range(len(cost)):
        if i % 3 != 2:
            minCost += cost[i]

    return minCost

Why is sorting in descending order and then skipping every 3rd candy optimal? A proof in two steps:

Problem Description

Given a 1-indexed array of integers that is sorted in non-decreasing order, find two numbers such that they add up to a target number.

Solution: Linear Scan with Binary Search

#binary-search

At its core, the problem is a binary search one. Given \(a\), find \(b = t - a\) in the right side of array. If \(a > \lfloor t / 2 \rfloor\), then there is no possible \(b\) to the right because \(b \ge a\) and \(2a > t\).

Given a sorted integer array, remove some duplicates in-place such that each unique element appears at most twice. Maintain the relative order of the elements. If there are \(k\) elements after removing the duplicates, the first \(k\) elements of the array should hold the final result.

This a two-pointer problem, where we have a tortoise and a hare. Establishing an invariant that must be maintained throughout the array is useful to avoid tripping up on index arithmetic. In this case, let tortoise be the index whose final value needs to be determined in the current iteration. [..., tortoise-1] (inclusive) is the processed range that won’t change. #two-pointer-algorithm

Merge Sorted Arrays In-Place With Buffer

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n representing the number of elements in nums1 and nums2 respectively. nums1 has a length of \(m + n\). Merge nums1 and nums2 into nums1 in non-decreasing order.

We don’t want to use extra \(\mathcal{O}(m + n)\) space. Traversing nums1 and nums2 from left to right creates complications, e.g., given \([4, 6, 8, 0, 0, 0]\) and \([3, 4, 5]\), the intermediate \([3, 6, 8, 0, 0, 0]\) raises questions on where to stash the \(4\). However, starting from \(m - 1\) and \(n - 1\) leads to an elegant solution where we don’t need intermediate stashes.

Given an array of size \(N\), return the element that appears more than \(\lfloor N/2 \rfloor\) times. Solve the problem in \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space.

Solving this in \(\mathcal{O}(N)\) time precludes sorting as that takes \(\mathcal{O}(N\ logN)\) time. Using \(\mathcal{O}(1)\) space precludes having a dictionary of frequencies. What is special about a frequency that is \(> \lfloor N/2 \rfloor\)? What kind of arithmetic would such a value survive?

In a sorted array, a number that appears \(> \lfloor N/2 \rfloor\) times is also the median. How can we compute the median of an unsorted array in \(\mathcal{O}(N)\) time and \(\mathcal{O}(1)\) space? Scratch that, the median is a more general problem as the frequency need not be \(> \lfloor N/2 \rfloor\).

Given an \(N \times N\) matrix, where each of the rows and columns are sorted in ascending order, return the \(k^{th}\) smallest element in the matrix. The memory complexity must be better than \(O(N^2)\).

It’s not guaranteed that matrix[r][c] > matrix[r-1][c], so we can’t compute the row (and similarly, the column) in which the \(k^{th}\) smallest element is in.

Using a priority queue that holds the \(K\) smallest elements does not work because the memory usage is \(O(K)\), where \(K\) can be any value in \([1, N^2]\). Furthermore, that doesn’t take into account that the rows and columns are already sorted.