Start learning free

LESSON 219 OF 410 · SORTING

Smallest K Integers in O(n log n) Time Complexity using Python

Practice O(n log n) Read the full explanation

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:

For this lesson, your algorithm should run in O(n log n) time and use O(1) extra space besides the returned values, when sorting in place (sorting a copy of nums takes O(n) extra space).
(There are faster solutions which we will discuss in future lessons)


STEP 1 OF 2
    Ctrl + Enter to check

    PYTHON · SORTING

    Smallest K in Python, explained

    Understanding the Problem

    The core challenge of this problem is to find the smallest k integers from an array of positive integers. This problem is significant in various applications such as data analysis, where you might need to find the smallest values in a dataset. A common pitfall is to use a naive approach that might not be optimal in terms of time complexity.

    Approach

    To solve this problem, we can consider the following approaches:

    Naive Solution

    A naive solution would be to sort the array and then return the first k elements. This approach is simple but not optimal in terms of time complexity.

    Optimized Solution

    An optimized solution involves using a sorting algorithm that runs in O(n log n) time complexity. Python's built-in sort function, which uses Timsort, is a good choice for this purpose. After sorting the array, we can simply return the first k elements.

    Algorithm

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

    1. Sort the array using Python's built-in sort function.
    2. Return the first k elements of the sorted array.

    Code Implementation

    def smallest_k_integers(nums, k):
    # Step 1: Sort the array
    nums.sort()
    
    # Step 2: Return the first k elements
    return nums[:k]

# Example usage
nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5]
k = 4
print(smallest_k_integers(nums, k))  # Output: [1, 2, 2, 3]

    Complexity Analysis

    The time complexity of this approach is O(n log n) due to the sorting step. The space complexity is O(1) as we are not using any extra space apart from the input array.

    Edge Cases

    Potential edge cases include:

    • k is greater than the length of the array: In this case, we should return the entire sorted array.
    • k is zero: We should return an empty list.

    Testing

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

    • Simple cases with small arrays.
    • Cases where k is larger than the array length.
    • Cases with duplicate values in the array.

    Thinking and Problem-Solving Tips

    When approaching such problems, it's essential to:

    • Understand the problem requirements and constraints.
    • Consider both naive and optimized solutions.
    • Analyze the time and space complexity of your approach.

    Conclusion

    In this blog post, we discussed how to find the smallest k integers from an array of positive integers using an optimized approach with O(n log n) time complexity. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for coding interviews.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free