Sort An Array Leetcode Problem 912 [Python Solution]

In this guide, we will solve the Sort An Array problem, which is LeetCode Problem 912. We’ll provide a Python solution for this problem while adhering to specific constraints.

Problem Name: Sort an Array
Difficulty: Medium
Category: Arrays & Hashing
Companies: Amazon

Question Link: Sort an Array on LeetCode

The goal is to sort an array of integers in ascending order, and we have to achieve this without using any built-in sorting functions.

We must also ensure that the algorithm runs in O(nlog(n)) time complexity and with minimal space complexity.

Problem Overview

The problem is straightforward: we are given an array of integers called nums, and we need to sort the array in ascending order and return it.

The challenge is to do this without using any built-in sorting functions and to achieve it with the best possible time and space complexity.

Example 1:

Let’s take a look at an example:

Input:

nums = [5, 2, 3, 1]


Output:

[1, 2, 3, 5]


In this example, after sorting the array, some numbers’ positions remain unchanged (e.g., 2 and 3), while others change positions (e.g., 1 and 5).

Example 2:

Another example:

Input:

nums = [5, 1, 1, 2, 0, 0]


Output:

[0, 0, 1, 1, 2, 5]


This example demonstrates that the values in the array are not necessarily unique.

Constraints:

To solve this problem efficiently, we need to understand the constraints.

The problem statement provides the following constraints:

• The length of the nums array is in the range 1 to 50,000.
• The values in nums are integers ranging from -50,000 to 50,000. Now that we have an overview of the problem, let’s delve into the solution.

Efficient Python Solution

We will use the Merge Sort algorithm to solve this problem efficiently.

Merge Sort is a popular sorting algorithm that follows a divide-and-conquer approach.

It has a time complexity of O(nlog(n)), which meets the problem’s requirements.

Here is a Python solution for this problem:

def sortArray(self, nums: List[int]) -> List[int]:
    def merge(arr, L, M, R):
        left, right = arr[L:M+1], arr[M+1:R+1]
        i, j, k = L, 0, 0
        while j < len(left) and k < len(right):
            if left[j] <= right[k]:
                arr[i] = left[j]
                j += 1
            else:
                arr[i] = right[k]
                k += 1
            i += 1
        while j < len(left):
            nums[i] = left[j]
            j += 1
            i += 1
        while k < len(right):
            nums[i] = right[k]
            k += 1
            i += 1

    def mergeSort(arr, l, r):
        if l == r:
            return arr
        m = (l + r) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)
        return arr

    return mergeSort(nums, 0, len(nums) - 1)

This solution uses the Merge Sort algorithm to sort the nums array efficiently.

The mergeSort function recursively divides the array into halves, sorts them, and then merges them back together using the merge function.

The time complexity of this solution is O(nlog(n)), which meets the problem’s requirements.

Time and Space Complexity

Time Complexity: O(nlog(n))

The Merge Sort algorithm has a time complexity of O(nlog(n)) because it divides the array into halves and recursively sorts and merges them.

The number of recursive levels is logarithmic in the size of the input array.

Space Complexity: O(n)

The space complexity is O(n) because we create temporary arrays to store the left and right halves of the array during the merge process.

The additional memory used for these temporary arrays contributes to the space complexity.

Reasoning Behind Our Approach

Merge Sort is a well-known sorting algorithm that fits the problem’s requirements.

It is efficient and has a stable time complexity of O(nlog(n)), making it a suitable choice for sorting large arrays.

The algorithm’s divide-and-conquer approach ensures that we can achieve the desired time complexity while adhering to the problem’s constraints.

The reason for choosing Merge Sort is that it is a reliable and well-understood algorithm that guarantees optimal time complexity.

It breaks the sorting problem into smaller subproblems, sorts them individually, and then combines them to obtain the final sorted array.

Related Interview Questions By Company:

• Surrounded Regions LeetCode
• Cheapest Flights Within K Stops LeetCode
• Construct Binary Tree From Preorder And Inorder Traversal LeetCode

Related Interview Questions By Difficulty:

• Majority Element LeetCode
• Sort Colors LeetCode
• Longest Common Prefix LeetCode

Related Interview Questions By Category:

• Reverse Bits LeetCode
• Kth Largest Element In A Stream LeetCode
• Validate Binary Search Tree LeetCode

Conclusion

In this tutorial, we tackled the Sort An Array problem from LeetCode.

We provided a Python solution that uses the Merge Sort algorithm to efficiently sort an array in ascending order.

The solution meets the problem’s requirements, including the time complexity of O(nlog(n)) and minimal space complexity.

We hope this guide was helpful in understanding the problem and its solution.

If you have any questions, suggestions, or comments, please feel free to share them.

Coding challenges are a great way to improve your problem-solving skills, and we encourage you to explore more coding problems and solutions.

Remember to like and engage if you found this content useful, and if you’re preparing for coding interviews, consider sticking around more and be more intentional about it.

Thank you for reading, and happy coding!