Problem Number 1300

Crossing the 1300 mark with a problem for which I was stuck in 2020. I was trying it before using sorted native data structures but it was too slow. This time I switched to my own Priority Queue implementation, and it barely worked. Code is down below, cheers, ACC.

K-th Smallest Prime Fraction - LeetCode

786. K-th Smallest Prime Fraction

Medium

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

 

Example 1:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

Example 2:

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

 

Constraints:

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * 104
• 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(n2) complexity?

Accepted

36,993

Submissions

70,597

public class Solution {
    public class PQueuePrimeFraction
    {
        public int num = 0;
        public int den = 0;

        public PQueuePrimeFraction(int num, int den)
        {
            this.num = num;
            this.den = den;
        }
    }

    public int[] KthSmallestPrimeFraction(int[] arr, int k)
    {
        PriorityQueue pQueue = new PriorityQueue(true);

        for (int i = 0; i < arr.Length; i++)
        {
            for (int j = i + 1; j < arr.Length; j++)
            {
                double w = (1.0 * arr[i]) / arr[j];
                pQueue.Enqueue(new PQueuePrimeFraction(arr[i], arr[j]), w);
            }
        }

        while (pQueue.Count > 0)
        {
            double w = 0;
            PQueuePrimeFraction current = (PQueuePrimeFraction)pQueue.Dequeue(out w);

            k--;
            if (k == 0)
            {
                return new int[] { current.num, current.den };
            }
        }

        return new int[] { -1, -1 };
    }
}

public class PriorityQueue
{
    public struct HeapEntry
    {
        private object item;
        private double priority;
        public HeapEntry(object item, double priority)
        {
            this.item = item;
            this.priority = priority;
        }
        public object Item
        {
            get
            {
                return item;
            }
        }
        public double Priority
        {
            get
            {
                return priority;
            }
        }
    }

    private bool ascend;
    private int count;
    private int capacity;
    private HeapEntry[] heap;

    public int Count
    {
        get
        {
            return this.count;
        }
    }

    public PriorityQueue(bool ascend, int cap = -1)
    {
        capacity = 10000000;
        if (cap > 0) capacity = cap;
        heap = new HeapEntry[capacity];
        this.ascend = ascend;
    }

    public object Dequeue(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        count--;
        trickleDown(0, heap[count]);
        return result;
    }
    public object Peak(out double priority)
    {
        priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public object Peak(/*out double priority*/)
    {
        //priority = heap[0].Priority;
        object result = heap[0].Item;
        return result;
    }

    public void Enqueue(object item, double priority)
    {
        count++;
        bubbleUp(count - 1, new HeapEntry(item, priority));
    }

    private void bubbleUp(int index, HeapEntry he)
    {
        int parent = (index - 1) / 2;
        // note: (index > 0) means there is a parent
        if (this.ascend)
        {
            while ((index > 0) && (heap[parent].Priority > he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
        else
        {
            while ((index > 0) && (heap[parent].Priority < he.Priority))
            {
                heap[index] = heap[parent];
                index = parent;
                parent = (index - 1) / 2;
            }
            heap[index] = he;
        }
    }

    private void trickleDown(int index, HeapEntry he)
    {
        int child = (index * 2) + 1;
        while (child < count)
        {
            if (this.ascend)
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority > heap[child + 1].Priority))
                {
                    child++;
                }
            }
            else
            {
                if (((child + 1) < count) &&
                    (heap[child].Priority < heap[child + 1].Priority))
                {
                    child++;
                }
            }
            heap[index] = heap[child];
            index = child;
            child = (index * 2) + 1;
        }
        bubbleUp(index, he);
    }
}