Smallest K in JavaScript

Given an array of positive integers nums, return the smallest k values, in any order you want.

Example:

Input: nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4
Output: [1, 2, 2, 3]
Explanation: Smallest number is 1, 2nd smallest is 2, 
            3rd smallest is 2, 4th smallest is 3

The result can be in any order, [2, 1, 3, 2] is also a correct answer.

Note:

Your algorithm should run in O(n) time and use O(log n) extra space.

Understanding the Problem

The core challenge of this problem is to find the smallest k integers from an array in an efficient manner. This problem is significant in scenarios where we need to quickly identify the smallest elements from a large dataset, such as in streaming data or real-time analytics.

Potential pitfalls include misunderstanding the requirement for the algorithm to run in O(n) time and use O(log n) extra space, which rules out simple sorting approaches that would take O(n log n) time.

Approach

To solve this problem efficiently, we can use a min-heap (priority queue). A min-heap allows us to efficiently extract the smallest elements. The steps are as follows:

Build a min-heap from the array.
Extract the smallest element k times from the heap.

While a naive approach would involve sorting the array and then taking the first k elements, this would not meet the O(n) time complexity requirement. Instead, using a min-heap allows us to achieve the desired time complexity.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize a min-heap.
Insert all elements of the array into the min-heap. This operation takes O(n) time.
Extract the smallest element from the heap k times. Each extraction takes O(log n) time, so k extractions take O(k log n) time.

Since k is typically much smaller than n, the overall time complexity is dominated by the O(n) heap construction.

Code Implementation

// Function to find the smallest k integers
function smallestK(nums, k) {
    // Min-heap implementation using a priority queue
    class MinHeap {
        constructor() {
            this.heap = [];
        }

        insert(val) {
            this.heap.push(val);
            this.bubbleUp();
        }

        bubbleUp() {
            let index = this.heap.length - 1;
            while (index > 0) {
                let parentIndex = Math.floor((index - 1) / 2);
                if (this.heap[index] >= this.heap[parentIndex]) break;
                [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
                index = parentIndex;
            }
        }

        extractMin() {
            if (this.heap.length === 1) return this.heap.pop();
            const min = this.heap[0];
            this.heap[0] = this.heap.pop();
            this.bubbleDown();
            return min;
        }

        bubbleDown() {
            let index = 0;
            const length = this.heap.length;
            const element = this.heap[0];
            while (true) {
                let leftChildIndex = 2 * index + 1;
                let rightChildIndex = 2 * index + 2;
                let leftChild, rightChild;
                let swap = null;

                if (leftChildIndex < length) {
                    leftChild = this.heap[leftChildIndex];
                    if (leftChild < element) {
                        swap = leftChildIndex;
                    }
                }

                if (rightChildIndex < length) {
                    rightChild = this.heap[rightChildIndex];
                    if (
                        (swap === null && rightChild < element) ||
                        (swap !== null && rightChild < leftChild)
                    ) {
                        swap = rightChildIndex;
                    }
                }

                if (swap === null) break;
                [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
                index = swap;
            }
        }
    }

    const minHeap = new MinHeap();
    for (let num of nums) {
        minHeap.insert(num);
    }

    const result = [];
    for (let i = 0; i < k; i++) {
        result.push(minHeap.extractMin());
    }

    return result;
}

// Example usage
const nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5];
const k = 4;
console.log(smallestK(nums, k)); // Output: [1, 2, 2, 3]

Complexity Analysis

The time complexity of this approach is O(n) for building the heap and O(k log n) for extracting the k smallest elements. Since k is typically much smaller than n, the overall time complexity is O(n). The space complexity is O(n) for storing the heap.

Edge Cases

Potential edge cases include:

k is 0: The output should be an empty array.
k is greater than the length of the array: The output should be the entire array sorted.
All elements in the array are the same: The output should be k instances of that element.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases with small arrays.
Cases where k is 0 or greater than the array length.
Arrays with duplicate elements.
Large arrays to test performance.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem constraints and requirements thoroughly.
Think about different data structures and their properties.
Break down the problem into smaller, manageable parts.
Consider edge cases and how your solution handles them.

Conclusion

In this blog post, we discussed how to find the smallest k integers from an array efficiently using a min-heap. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

Smallest K Integers III in O(n) Time Complexity using JavaScript