Problems

In sorted array find A[i]=i

Problem Statement: Given a sorted array A[1 ... n], check whether there is an index i for which A[i]=i.

Approach:

Use a modified binary search

1. If A[mid] = mid return mid
2. If A[mid] > mid, search A[:mid-1] and A[A[mid]:]
3. Else search A[mid+1: ] amd A[:A[mid]]

---

Median of 2 lists

Problem Statement: Given 2 sorted lists of size n. Given an algorithm for finding the median element in union of 2 lists

Approach:

1. Find median of L1 and L2. Let the medians be m1 & m2 respectively.
2. If m1 == m2, return m1
3. If m1 > m2, L1 = L1[:m1] amd L2 = L2[m2:]
4. Else L1 = L1[m1:] and L2 = L2[:m2]
5. Repeat until both L1 & L2 len becomes 2
6. Median = ((max(L1[0], L2[0])) + min(L1[1], L2[1])) / 2

---

Nuts and bolts

Problem Statement: Given a set of n nuts and n bolts of different sizes. Match each nut with its corresponding bolt. Assume you can only compare a nut with a bolt, not two nuts or two bolts directly.

Approach:

Use a modified version of quick sort.

---

Max value contiguous subsequence

Problem Statement: Given a list of n numbers. Find a contiguous subsequence for which sum of elements is maximum.

Approach:

1. Compute the solution in the left half
2. Compute the solution in the right half
3. Compute the solution that begins in left half and ends in right half
4. Take the maximum of three

Optimal solution: Kadane's algorithm

---

Closest-Pair of points

Problem Statement: Given n points. Find the pair with the closest distance

Approach:

1. Sort the points on x-coordinate. Divide into 2 halves.
2. Recursively find the closest pair in left and right halves.
3. Combine results from left and right.

data class Point(val x: Int, val y: Int)

fun dis(p1: Point, p2: Point) = sqrt((p1.x - p2.x).pow(2) + (p1.y - p2.y).pow(2))

fun closestPairUtil(pointsX: List<Point>, pointsY: List<Point>): Pair<Double, Pair<Point, Point>> {
    if(pointsX.size <= 3) return bruteForceClosestPair(pointsX)

    val mid = pointsX.size / 2
    val midPoint = pointsX[mid]

    val lX = pointsX.subLost(0, mid)
    val rX = pointsX.subLost(mid, )

    val lY = pointsY.filter{it.x <= midPoint.x}.sortedBy{it.y}
    val rY = pointsY.filter{it.x > midPoint.x}.sortedBy{it.y}

    val (lD, lSol) = closestPairUtil(lx, lY)
    val (rD, rSol) = closestPairUtil(rx, rY)

    var minDis = minOf(lD, rD)
    var closestPair = if(lD < rD) lSol else rSol

    val strip = pointsY.filter { abs(it.x - midPoint.x) < minDis}

    for(i in strip.indices) {
        for(j in i+1 until min(i+7, strip.size)) {
            val dist = dis(strip[i], strip[j])
            if(dist < minDis) {
                minDis = dist
                closestPair = Pair(strip[i], strip[j])
            }
        }
    }
    return Pair(minDis, closestPair)
}

fun closestPair(points: List<Point>): Pair<Point, Point> {
    val sortedX = points.sortedBy {it.x}
    val sortedY = points.sortedBy {it.y}

    return closestPairUtil(sortedX, sortedY)
}