What is the brute force approach and complexity for K-th Smallest Prime Fraction?

List every arr[i]/arr[j] with i < j, sort them by value, and read the k-th with time complexity O(N² log N) and space complexity O(N²).

What is the optimal approach and complexity for K-th Smallest Prime Fraction?

Min-heap with one row per numerator, starting at the largest denominator with optimal time complexity O((N + K) log N) and space complexity O(N).

How do you identify the pattern for K-th Smallest Prime Fraction?

Look for key signals in the prompt: "k-th smallest fraction" indicates Take out k − 1 values in order, then read the top of the heap.; "sorted array with 1 first" indicates Each numerator's row arr[i]/arr[j] is sorted as the bottom index moves, so each row is a sorted list.; "primes" indicates They make every fraction different. The algorithm itself does not need primality..

K-th Smallest Prime Fraction

Q: What is the optimal approach and complexity for K-th Smallest Prime Fraction?

Min-heap with one row per numerator, starting at the largest denominator with optimal time complexity O((N + K) log N) and space complexity O(N).

Q: How do you identify the pattern for K-th Smallest Prime Fraction?

Look for key signals in the prompt: "k-th smallest fraction" indicates Take out k − 1 values in order, then read the top of the heap.; "sorted array with 1 first" indicates Each numerator's row arr[i]/arr[j] is sorted as the bottom index moves, so each row is a sorted list.; "primes" indicates They make every fraction different. The algorithm itself does not need primality..

Medium·LeetCode #786 Pro OnlySlight Variation

LeetCode

Problem Statement

You get a sorted array arr of distinct positive integers. The first value is 1, and every other value is a prime number.

Make a fraction from every pair of positions i < j: the top is arr[i] and the bottom is arr[j]. Return the k-th smallest of these fractions, as the two-element list [numerator, denominator]. Only pairs with i < j count, so every fraction is less than 1.

Input

A sorted integer array arr, and an integer k.

Output

A list [numerator, denominator] for the k-th smallest fraction.

Example 1

Input: arr = [1,2,3,5], k = 3

Output: [2,5]

The fractions in order are 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. The third one is 2/5.

Example 2

Input: arr = [1,7], k = 1

Output: [1,7]

There is only one fraction, 1/7.

Constraints

• 2 ≤ arr.length ≤ 1000
• 1 ≤ arr[i] ≤ 3 · 10^4
• arr[0] == 1
• arr[i] is a prime number for i > 0
• All the numbers of arr are unique and sorted in strictly increasing order
• 1 ≤ k ≤ arr.length · (arr.length − 1) / 2
• Follow-up: Can you solve the problem with better than O(n^2) complexity?

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“k-th smallest fraction”

→ Take out k − 1 values in order, then read the top of the heap.

“sorted array with 1 first”

→ Each numerator's row arr[i]/arr[j] is sorted as the bottom index moves, so each row is a sorted list.

“primes”

→ They make every fraction different. The algorithm itself does not need primality.

Approach Complexity Ladder

Brute Force — every fraction, sort, read position kO(N² log N)O(N²)

List every arr[i]/arr[j] with i < j, sort them by value, and read the k-th

Optimal — one sorted row per numerator, take k − 1 timesO((N + K) log N)O(N)

Min-heap with one row per numerator, starting at the largest denominator

Brute Force Intuition

Make every fraction with i < j, sort them by value, and return the one at position k − 1. Sorting all of them just to read one is wasteful.

Recognition rule for this sub-pattern:

Pop K times from the merged stream; the Kth pop is the answer.

Remember this · K-way Merge

Trigger

K sorted lists/arrays, kth smallest across sorted rows, smallest range covering all lists.

Think

The next smallest item overall must be the front of some list — which one?

Key question

What do I push back into the heap after popping?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like K-way Merge translate into production architectures and low-level memory mechanics.

LLD Architecture