Kth Smallest in Sorted Matrix

🎯

Kth Smallest in Sorted Matrix

mediumBINARY_SEARCHAmazonGoogleFacebook

Imagine you have a large spreadsheet where each row and column is sorted, and you want to quickly find the kth smallest number without scanning the entire sheet.

💡 This problem is a classic example of applying binary search not on indices but on the range of possible values (answer space). Beginners often struggle because the matrix is sorted both row-wise and column-wise, which complicates direct indexing or simple binary search on indices.

📋

Problem Statement

Given an n x n matrix where each of the rows and columns is sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Input: matrix (List[List[int]]), k (int) Output: int (the kth smallest element)

n == matrix.length == matrix[i].length1 ≤ n ≤ 300-10^9 ≤ matrix[i][j] ≤ 10^91 ≤ k ≤ n^2

💡

Example

Input"matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8"

Output13

The sorted order is [1,5,9,10,11,12,13,13,15], the 8th smallest is 13.

• k = 1 → smallest element in the matrix
• k = n*n → largest element in the matrix
• matrix with all identical elements → kth smallest is that element
• matrix with negative and positive values → ensure counting works correctly

⚠️

Common Mistakes

Using binary search on indices instead of value range

Incorrect or inefficient solution because indices do not correspond to sorted order

✅ Binary search must be on the value range between smallest and largest elements

Incorrect counting of elements ≤ mid (e.g., scanning entire matrix)

Time complexity becomes O(n^2 log(max-min)) which is too slow

✅ Use the efficient O(n) counting method starting from bottom-left corner

Off-by-one errors in binary search boundaries

Infinite loops or wrong kth element returned

✅ Use while(low < high) and adjust low = mid + 1 or high = mid carefully

Not handling duplicate elements correctly

Incorrect kth smallest when duplicates exist

✅ Counting method counts all elements ≤ mid including duplicates, so duplicates are naturally handled

Heap approach pushing too many elements (e.g., all elements)

Heap grows too large, causing memory/time issues

✅ Only push next element in the same row after popping an element

🧠

Brute Force (Flatten and Sort)

💡 This approach exists to build intuition by treating the matrix as a simple list and sorting it. It’s straightforward but inefficient for large inputs, highlighting the need for better methods.

Intuition

Flatten the matrix into a single list, sort it, and then pick the kth element. This uses the fact that sorting gives a direct way to find the kth smallest.

Algorithm

1. Step 1: Flatten the 2D matrix into a 1D list.
2. Step 2: Sort the 1D list.
3. Step 3: Return the element at index k-1.

💡 The algorithm is simple but hides the inefficiency in sorting a potentially large list, which is easy to overlook initially.

</>

Code

from typing import List

def kthSmallest(matrix: List[List[int]], k: int) -> int:
    flat = []
    for row in matrix:
        flat.extend(row)
    flat.sort()
    return flat[k-1]

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

flat = []Initialize a list to hold all elements from the matrix.

for row in matrix:Iterate over each row to access all elements.

flat.extend(row)Add all elements of the current row to the flat list.

flat.sort()Sort the entire list to arrange elements in ascending order.

return flat[k-1]Return the kth smallest element (0-based index).

import java.util.*;

public class KthSmallest {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int[] flat = new int[n * n];
        int idx = 0;
        for (int[] row : matrix) {
            for (int num : row) {
                flat[idx++] = num;
            }
        }
        Arrays.sort(flat);
        return flat[k - 1];
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

int n = matrix.length;Get the size of the matrix to allocate array.

int[] flat = new int[n * n];Create a 1D array to hold all matrix elements.

for (int[] row : matrix)Iterate over each row of the matrix.

flat[idx++] = num;Copy each element into the flat array sequentially.

Arrays.sort(flat);Sort the array to get elements in ascending order.

return flat[k - 1];Return the kth smallest element using zero-based indexing.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    vector<int> flat;
    for (auto& row : matrix) {
        for (int num : row) {
            flat.push_back(num);
        }
    }
    sort(flat.begin(), flat.end());
    return flat[k - 1];
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

int n = matrix.size();Get the size of the matrix for reference.

vector<int> flat;Create a vector to hold all elements from the matrix.

for (auto& row : matrix)Iterate over each row by reference for efficiency.

flat.push_back(num);Append each element to the flat vector.

sort(flat.begin(), flat.end());Sort the vector to order elements ascendingly.

return flat[k - 1];Return the kth smallest element using zero-based indexing.

function kthSmallest(matrix, k) {
    const flat = [];
    for (const row of matrix) {
        flat.push(...row);
    }
    flat.sort((a, b) => a - b);
    return flat[k - 1];
}

// Driver code
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

const flat = [];Initialize an empty array to hold all matrix elements.

for (const row of matrix)Loop through each row in the matrix.

flat.push(...row);Spread and append all elements of the current row into flat.

flat.sort((a, b) => a - b);Sort the array numerically in ascending order.

return flat[k - 1];Return the kth smallest element (0-based index).

⏱

Complexity

TimeO(n^2 log(n^2)) = O(n^2 log n)

SpaceO(n^2)

Flattening takes O(n^2), sorting takes O(n^2 log n^2), which dominates. Space is O(n^2) for the flattened list.

💡 For n=300, this means sorting 90,000 elements, which is expensive and slow for interviews.

Interview Verdict: Accepted but inefficient

This approach works but is too slow for large inputs, so it’s mainly useful to demonstrate understanding before optimizing.

🧠

Binary Search on Value Range with Count Function

💡 This approach introduces the key insight: binary search on the answer space (value range) rather than indices. It leverages the sorted property of rows and columns to count how many elements are ≤ mid efficiently.

Intuition

We know the smallest and largest elements in the matrix define the search range. We guess a mid value and count how many elements are ≤ mid. If count < k, we move the low bound up; else, we move the high bound down.

Algorithm

1. Step 1: Initialize low as the smallest element and high as the largest element in the matrix.
2. Step 2: While low < high, compute mid = (low + high) // 2.
3. Step 3: Count how many elements in the matrix are ≤ mid using a row-wise efficient method.
4. Step 4: If count < k, set low = mid + 1; else set high = mid.
5. Step 5: Return low as the kth smallest element.

💡 The counting step is the trickiest; it uses the sorted rows and columns to count in O(n) time per iteration.

</>

Code

from typing import List

def countLessEqual(matrix: List[List[int]], mid: int) -> int:
    n = len(matrix)
    count = 0
    row, col = n - 1, 0
    while row >= 0 and col < n:
        if matrix[row][col] <= mid:
            count += row + 1
            col += 1
        else:
            row -= 1
    return count

def kthSmallest(matrix: List[List[int]], k: int) -> int:
    n = len(matrix)
    low, high = matrix[0][0], matrix[-1][-1]
    while low < high:
        mid = (low + high) // 2
        if countLessEqual(matrix, mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

def countLessEqual(matrix: List[List[int]], mid: int) -> int:Helper to count elements ≤ mid efficiently.

n = len(matrix)Get matrix size for iteration limits.

count = 0Initialize count of elements ≤ mid.

row, col = n - 1, 0Start from bottom-left corner to count efficiently.

while row >= 0 and col < n:Traverse matrix within bounds.

if matrix[row][col] <= mid:If current element ≤ mid, all elements above in this column are also ≤ mid.

count += row + 1Add all elements in this column up to current row.

col += 1Move right to next column.

else:Otherwise, decrease high bound.

row -= 1Move up one row.

while low < high:Binary search loop on value range.

mid = (low + high) // 2Guess mid value.

if countLessEqual(matrix, mid) < k:If fewer than k elements ≤ mid, increase low.

low = mid + 1Adjust low bound.

high = midAdjust high bound.

return lowLow converges to kth smallest.

public class KthSmallest {
    private static int countLessEqual(int[][] matrix, int mid) {
        int n = matrix.length;
        int count = 0, row = n - 1, col = 0;
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }

    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int low = matrix[0][0], high = matrix[n - 1][n - 1];
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (countLessEqual(matrix, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

private static int countLessEqual(int[][] matrix, int mid)Helper counts elements ≤ mid efficiently.

int n = matrix.length;Get matrix size for iteration limits.

int count = 0, row = n - 1, col = 0;Initialize count and start from bottom-left corner.

while (row >= 0 && col < n)Traverse matrix within bounds.

if (matrix[row][col] <= mid)If element ≤ mid, all above are also ≤ mid.

count += row + 1;Add all elements in this column up to current row.

col++;Move right to next column.

elseOtherwise, decrease high.

row--;Move up one row.

while (low < high)Binary search on value range.

int mid = low + (high - low) / 2;Calculate mid to avoid overflow.

if (countLessEqual(matrix, mid) < k)If count less than k, increase low.

low = mid + 1;Adjust low bound.

high = mid;Adjust high bound.

return low;Return kth smallest element.

#include <iostream>
#include <vector>
using namespace std;

int countLessEqual(const vector<vector<int>>& matrix, int mid) {
    int n = matrix.size();
    int count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) {
            count += row + 1;
            col++;
        } else {
            row--;
        }
    }
    return count;
}

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    int low = matrix[0][0], high = matrix[n - 1][n - 1];
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (countLessEqual(matrix, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

int countLessEqual(const vector<vector<int>>& matrix, int mid)Helper counts elements ≤ mid efficiently.

int n = matrix.size();Get matrix size for iteration limits.

int count = 0, row = n - 1, col = 0;Initialize count and start from bottom-left corner.

while (row >= 0 && col < n)Traverse matrix within bounds.

if (matrix[row][col] <= mid)If element ≤ mid, all above are also ≤ mid.

count += row + 1;Add all elements in this column up to current row.

col++;Move right to next column.

elseOtherwise, decrease high.

row--;Move up one row.

while (low < high)Binary search on value range.

int mid = low + (high - low) / 2;Calculate mid to avoid overflow.

if (countLessEqual(matrix, mid) < k)If count less than k, increase low.

low = mid + 1;Adjust low bound.

high = mid;Adjust high bound.

return low;Return kth smallest element.

function countLessEqual(matrix, mid) {
    const n = matrix.length;
    let count = 0, row = n - 1, col = 0;
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= mid) {
            count += row + 1;
            col++;
        } else {
            row--;
        }
    }
    return count;
}

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let low = matrix[0][0], high = matrix[n - 1][n - 1];
    while (low < high) {
        const mid = Math.floor((low + high) / 2);
        if (countLessEqual(matrix, mid) < k) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

// Driver code
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

function countLessEqual(matrix, mid)Helper counts elements ≤ mid efficiently.

const n = matrix.length;Get matrix size for iteration limits.

let count = 0, row = n - 1, col = 0;Initialize count and start from bottom-left corner.

while (row >= 0 && col < n)Traverse matrix within bounds.

if (matrix[row][col] <= mid)If element ≤ mid, all above are also ≤ mid.

count += row + 1;Add all elements in this column up to current row.

col++;Move right to next column.

elseOtherwise, decrease high.

row--;Move up one row.

while (low < high)Binary search on value range.

const mid = Math.floor((low + high) / 2);Calculate mid value.

if (countLessEqual(matrix, mid) < k)If count less than k, increase low.

low = mid + 1;Adjust low bound.

high = mid;Adjust high bound.

return low;Return kth smallest element.

⏱

Complexity

TimeO(n log(max - min))

SpaceO(1)

Each binary search iteration takes O(n) to count elements, and binary search runs O(log(max - min)) times.

💡 For n=300 and value range ~10^9, this is efficient enough for interviews.

Interview Verdict: Accepted and efficient

This is the standard optimal approach for this problem, balancing clarity and performance.

🧠

Min-Heap Based Approach (Priority Queue)

💡 This approach uses a min-heap to simulate merging sorted rows, similar to merging k sorted lists. It’s intuitive but less efficient than binary search on value range for large matrices.

Intuition

Push the first element of each row into a min-heap. Pop the smallest element and push the next element from the same row. Repeat k times to get the kth smallest.

Algorithm

1. Step 1: Initialize a min-heap and push the first element of each row with its coordinates.
2. Step 2: Pop the smallest element from the heap.
3. Step 3: If there is a next element in the same row, push it into the heap.
4. Step 4: Repeat steps 2-3 k times.
5. Step 5: The last popped element is the kth smallest.

💡 This approach simulates a k-way merge, which is a common technique for sorted arrays.

</>

Code

from typing import List
import heapq

def kthSmallest(matrix: List[List[int]], k: int) -> int:
    n = len(matrix)
    min_heap = []
    for r in range(min(k, n)):
        heapq.heappush(min_heap, (matrix[r][0], r, 0))
    count = 0
    while min_heap:
        val, r, c = heapq.heappop(min_heap)
        count += 1
        if count == k:
            return val
        if c + 1 < n:
            heapq.heappush(min_heap, (matrix[r][c+1], r, c+1))

# Driver code
if __name__ == '__main__':
    matrix = [[1,5,9],[10,11,13],[12,13,15]]
    k = 8
    print(kthSmallest(matrix, k))  # Output: 13

Line Notes

min_heap = []Initialize a min-heap to store elements with their positions.

for r in range(min(k, n))Push first element of each row up to k rows to limit heap size.

heapq.heappush(min_heap, (matrix[r][0], r, 0))Push tuple (value, row, col) into heap.

val, r, c = heapq.heappop(min_heap)Pop smallest element from heap.

count += 1Increment count of popped elements.

if count == k: return valReturn the kth popped element as answer.

if c + 1 < n:If next element in row exists, push it into heap.

heapq.heappush(min_heap, (matrix[r][c+1], r, c+1))Push next element from same row.

import java.util.*;

public class KthSmallest {
    public static int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int r = 0; r < Math.min(k, n); r++) {
            minHeap.offer(new int[]{matrix[r][0], r, 0});
        }
        int count = 0;
        while (!minHeap.isEmpty()) {
            int[] curr = minHeap.poll();
            int val = curr[0], r = curr[1], c = curr[2];
            count++;
            if (count == k) return val;
            if (c + 1 < n) {
                minHeap.offer(new int[]{matrix[r][c + 1], r, c + 1});
            }
        }
        return -1; // Should never reach here
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,5,9},{10,11,13},{12,13,15}};
        int k = 8;
        System.out.println(kthSmallest(matrix, k)); // Output: 13
    }
}

Line Notes

PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));Min-heap ordered by element value.

for (int r = 0; r < Math.min(k, n); r++)Push first element of each row up to k rows.

minHeap.offer(new int[]{matrix[r][0], r, 0});Add element with row and column indices.

int[] curr = minHeap.poll();Pop smallest element from heap.

count++;Increment count of popped elements.

if (count == k) return val;Return kth popped element.

if (c + 1 < n)If next element in row exists, push it.

minHeap.offer(new int[]{matrix[r][c + 1], r, c + 1});Push next element from same row.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int kthSmallest(vector<vector<int>>& matrix, int k) {
    int n = matrix.size();
    auto comp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b) {
        return get<0>(a) > get<0>(b);
    };
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(comp)> minHeap(comp);
    for (int r = 0; r < min(k, n); ++r) {
        minHeap.emplace(matrix[r][0], r, 0);
    }
    int count = 0;
    while (!minHeap.empty()) {
        auto [val, r, c] = minHeap.top();
        minHeap.pop();
        count++;
        if (count == k) return val;
        if (c + 1 < n) {
            minHeap.emplace(matrix[r][c + 1], r, c + 1);
        }
    }
    return -1; // Should not reach here
}

int main() {
    vector<vector<int>> matrix = {{1,5,9},{10,11,13},{12,13,15}};
    int k = 8;
    cout << kthSmallest(matrix, k) << endl; // Output: 13
    return 0;
}

Line Notes

auto comp = [](const tuple<int,int,int>& a, const tuple<int,int,int>& b)Comparator for min-heap based on element value.

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, decltype(comp)> minHeap(comp);Declare min-heap with custom comparator.

for (int r = 0; r < min(k, n); ++r)Push first element of each row up to k rows.

minHeap.emplace(matrix[r][0], r, 0);Add element with row and column indices.

auto [val, r, c] = minHeap.top();Get smallest element from heap.

minHeap.pop();Remove smallest element.

count++;Increment count of popped elements.

if (count == k) return val;Return kth popped element.

if (c + 1 < n)If next element in row exists, push it.

minHeap.emplace(matrix[r][c + 1], r, c + 1);Push next element from same row.

class MinHeap {
    constructor() {
        this.heap = [];
    }
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent][0] <= this.heap[idx][0]) break;
            this.swap(parent, idx);
            idx = parent;
        }
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return top;
    }
    bubbleDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (left < length && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
            if (right < length && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
            if (smallest === idx) break;
            this.swap(idx, smallest);
            idx = smallest;
        }
    }
    size() {
        return this.heap.length;
    }
}

function kthSmallest(matrix, k) {
    const n = matrix.length;
    const minHeap = new MinHeap();
    for (let r = 0; r < Math.min(k, n); r++) {
        minHeap.push([matrix[r][0], r, 0]);
    }
    let count = 0;
    while (minHeap.size() > 0) {
        const [val, r, c] = minHeap.pop();
        count++;
        if (count === k) return val;
        if (c + 1 < n) {
            minHeap.push([matrix[r][c + 1], r, c + 1]);
        }
    }
    return -1; // Should not reach here
}

// Driver code
const matrix = [[1,5,9],[10,11,13],[12,13,15]];
const k = 8;
console.log(kthSmallest(matrix, k)); // Output: 13

Line Notes

class MinHeapCustom min-heap implementation for priority queue.

push(val)Add new element and maintain heap property.

pop()Remove and return smallest element.

for (let r = 0; r < Math.min(k, n); r++)Push first element of each row up to k rows.

minHeap.push([matrix[r][0], r, 0]);Push element with row and column indices.

const [val, r, c] = minHeap.pop();Pop smallest element from heap.

count++;Increment count of popped elements.

if (count === k) return val;Return kth popped element.

if (c + 1 < n)If next element in row exists, push it.

minHeap.push([matrix[r][c + 1], r, c + 1]);Push next element from same row.

⏱

Complexity

TimeO(k log n)

SpaceO(n)

Heap size is at most n, and we perform k extractions and insertions.

💡 For k close to n^2, this can be slower than binary search approach.

Interview Verdict: Accepted but less optimal

This approach is intuitive and useful if k is small, but binary search on value range is preferred for large inputs.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the binary search on value range approach is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 log n)	O(n^2)	No	N/A	Mention only - never code
2. Binary Search on Value Range	O(n log(max - min))	O(1)	No	N/A	Code this approach
3. Min-Heap Based	O(k log n)	O(n)	No	N/A	Mention as alternative, code if asked

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify problem constraints and input format.Step 2: Describe brute force approach to show understanding.Step 3: Introduce binary search on value range and counting method.Step 4: Optionally mention heap approach as alternative.Step 5: Code the binary search approach with clear comments.Step 6: Test with edge cases and explain time/space complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Ability to recognize binary search on answer space, implement efficient counting, and reason about complexity.

Common Follow-ups

• What if the matrix is not square? → The approach still works with minor adjustments.
• Can you find kth largest instead? → Use similar binary search with reversed conditions.

💡 These follow-ups test flexibility and understanding of the core binary search technique.

🔍

Pattern Recognition

When to Use

1) Matrix or 2D array sorted row-wise and column-wise, 2) Need kth smallest/largest element, 3) Direct sorting is expensive, 4) Counting elements ≤ mid is possible

Signature Phrases

'kth smallest element in a sorted matrix''count how many elements are less than or equal to a value'

NOT This Pattern When

Problems that require searching indices or positions without sorted value ranges, or those that need DP or graph algorithms.

Similar Problems

Find Kth Smallest Element in a Sorted Array - simpler 1D binary searchMedian of Two Sorted Arrays - binary search on answer spaceKth Largest Element in an Array - heap and binary search variants

Practice

1. You are given an array of positions of balls on a number line and a number m. You want to place m balls in these positions such that the minimum distance between any two balls is maximized. Which algorithmic approach guarantees finding the optimal minimum distance efficiently?

easy

A. Binary search on the answer space combined with a greedy feasibility check

B. Greedy placement by always placing balls at the closest possible positions without backtracking

C. Dynamic programming to consider all subsets of positions and their minimum distances

D. Sorting the positions and then using a sliding window to find the maximum minimum distance

Solution

1. Step 1: Understand the problem structure

   The problem asks to maximize the minimum distance between placed balls, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the correct approach

   Binary search on the answer space (possible distances) combined with a greedy feasibility check efficiently finds the maximum minimum distance. Greedy alone or DP are either incorrect or inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search narrows down distance candidates efficiently [OK]

Hint: Maximize minimum distance -> binary search on answer space [OK]

Common Mistakes:

• Thinking greedy alone suffices without binary search
• Using DP which is inefficient here

2. You are given an array of non-negative integers and a number m. You want to split the array into m non-empty continuous subarrays such that the largest sum among these subarrays is minimized. Which algorithmic approach guarantees finding this minimal largest sum efficiently?

easy

A. Dynamic programming with memoization over all possible splits

B. Greedy approach that always splits when the current sum exceeds a fixed threshold

C. Binary search on the answer space combined with a greedy feasibility check

D. Sorting the array and using two pointers to find the minimal largest sum

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing the largest sum among m subarrays, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the approach that efficiently searches the answer space

   Binary search on the possible sums combined with a greedy check to verify feasibility is the standard approach that guarantees optimality and efficiency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on answer space is the canonical pattern for this problem [OK]

Hint: Minimize max sum -> binary search on answer space [OK]

Common Mistakes:

• Assuming greedy splitting always yields optimal solution
• Trying DP without pruning leads to exponential time
• Sorting does not help because order matters

3. Consider the following Python code implementing an integer square root using Newton's method. What is the value of guess after the first iteration of the while loop when x = 8?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize variables for x=8

   Initial guess = 8 // 2 = 4.

2. Step 2: First iteration update

   Check 4*4=16 > 8, so update guess = (4 + 8 // 4) // 2 = (4 + 2) // 2 = 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First guess update correctly computes to 3 [OK]

Hint: Initial guess halves x; update uses integer division [OK]

Common Mistakes:

• Off-by-one in guess update
• Confusing integer division with float
• Miscomputing initial guess

4. What is the time complexity of the optimized binary search solution for placing m balls in n positions to maximize the minimum distance, where d is the maximum distance between the first and last positions?

medium

A. O(n log d)

B. O(n * d)

C. O(d log n)

D. O(n log n)

Solution

1. Step 1: Identify outer loop complexity

   Binary search on answer space runs in O(log d) iterations, where d is max distance.

2. Step 2: Identify inner loop complexity

   Each feasibility check scans positions once, O(n). Total complexity is O(n log d).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search x linear feasibility check = O(n log d) [OK]

Hint: Binary search on distance x linear feasibility check [OK]

Common Mistakes:

• Confusing d with n in complexity
• Assuming linear search over distances (O(n*d))

5. Suppose the problem is modified so that the two input arrays can contain duplicate elements and you want to find the median of the combined multiset where elements can be reused infinitely many times. Which modification to the binary search on value range approach correctly handles this scenario?

hard

A. Modify countLessEqual to count elements less or equal normally, but adjust total length to infinite, then return left directly.

B. Use the same binary search on value range but count elements less or equal considering infinite duplicates as infinite count.

C. Use binary search on value range with countLessEqual unchanged, but adjust the target count to half of the finite combined length ignoring duplicates.

D. Use binary search on value range with countLessEqual unchanged, but since duplicates are infinite, the median is the minimum element.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean total length is infinite, so median is the smallest value with countLessEqual ≥ half of infinite.

2. Step 2: Adjust countLessEqual and target

   Counting elements normally but total length infinite means target is infinite/2 = infinite, so median is left boundary where countLessEqual reaches infinite.

3. Step 3: Return left directly

   Since infinite duplicates, median is the smallest value that satisfies countLessEqual condition, so return left.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite duplicates require adjusting total length and returning left [OK]

Hint: Infinite duplicates make total length infinite, median is smallest qualifying value [OK]

Common Mistakes:

• Counting duplicates as finite
• Ignoring infinite total length
• Returning min element incorrectly