Sort an Array

LeetCode 948 | Difficulty: Medium

Medium

Problem Description

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(nlog(n)) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]
Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Explanation: Note that the values of nums are not necessarily unique.

Constraints:

- `1 <= nums.length <= 5 * 10^4`

- `-5 * 10^4 <= nums[i] <= 5 * 10^4`

Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort

---

Approach

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 268 ms)

Metric	Value
Runtime	268 ms
Memory	35.2 MB
Date	2019-12-10

Solution

public class Solution {
    public IList<int> SortArray(int[] nums) {
     Array.Sort(nums);
    return nums;
}


}

📜 3 more C# submission(s)

Submission (2019-12-10) — 288 ms, 35.4 MB

public class Solution {
    public IList<int> SortArray(int[] nums) {
     if (nums.Length <= 1) return nums;
    mergesort(nums);
    return nums;
}

public void mergesort(int[] nums)
{
    int[] ar = new int[nums.Length];
    mergesort(nums, ar, 0, nums.Length-1);
}

public void mergesort(int[] nums, int[] ar, int lo, int hi)
{
    if(lo>=hi) return;
    int mid = lo + (hi - lo) / 2;
    mergesort(nums, ar, lo, mid);
    mergesort(nums, ar, mid+1, hi);
    merge(nums, ar, lo, mid, hi);

}

public void merge(int[] nums, int[] ar, int lo, int mid, int hi)
{
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi)
    {
        if (nums[i] <= nums[j])
        {
            ar[k++] = nums[i++];

        }
        else
        {
            ar[k++] = nums[j++];
        }
    }
    while(i<=mid)
    {
        ar[k++] = nums[i++];
    }
    while(j<=hi)
    {
        ar[k++] = nums[j++];
    }
    for (int p = lo; p <= hi; p++)
    {
        nums[p] = ar[p];
    }
}
}

Submission (2019-12-10) — 300 ms, 35 MB

public class Solution {
    public IList<int> SortArray(int[] nums) {
       if(nums.Length<=1) return nums;
    quicksort(nums,0, nums.Length-1);
    return nums;
}

public void quicksort(int[] nums, int lo, int hi)
{
    if(lo<hi)
    {
        int p = partition(nums,lo,hi);
        quicksort(nums,lo,p-1);
        quicksort(nums,p+1,hi);     
    }
}

public int partition(int[] nums, int lo, int hi)
{
    int i = lo;
    int pivot = nums[hi];
    for (int j = lo; j < hi; j++)
    {
        if(nums[j]<=nums[hi])
        {
            swap(nums,i,j);
            i++;
        }
    }
    swap(nums,i,hi);
    return i;
}

public void swap(int[] nums, int p1, int p2)
{
    int temp = nums[p1];
    nums[p1] = nums[p2];
    nums[p2] = temp;
}
}

Submission (2020-01-02) — 308 ms, 36 MB

public class Solution {
    public IList<int> SortArray(int[] nums) {
     Array.Sort(nums);
    return nums;
}


}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.