Press "Enter" to skip to content

Posts tagged as “Merge Sort”

LeetCode 977. Squares of a Sorted Array

By stone on April 20, 2021

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

Solution 1: (Quick Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(nums, left, right) {
    let index;
    if (nums.length > 1) {
        // index returned from partition
        index = partition(nums, left, right);
        // more elements on the left side of the pivot
        if (left < index - 1)
            quickSort(nums, left, index - 1);
        // more elements on the right side of the pivot
        if (index < right)
            quickSort(nums, index, right);
    }
    // you can return or not return, 
    // since we change nums, no need to return
    // return nums;
}

function partition(nums, start, end) {
    let l = start, r = end;
    let mid = Math.floor((start + end) / 2);
    let pivot = nums[mid];
    // Important: l <= r not l < r
    while (l <= r) {
        while(nums[l] < pivot)
            l++;
        while(nums[r] > pivot)
            r--;
        if (l <= r) {
            // swap
            [nums[l], nums[r]] = [nums[r], nums[l]];
            l++;
            r--;
        }
    }
    return l;
}

Solution 2: (Merge Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    let mid =  Math.floor((start + end) / 2);
    mergeSort(nums, start, mid, temp);
    mergeSort(nums, mid + 1, end, temp);
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid =  Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
             temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = 0; i <= end; i++)
        nums[i] = temp[i];
}

LeetCode 912. Sort an Array (javascript)

By stone on April 14, 2021

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

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

Idea:

Use Merge Sort Template

Solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums === null || nums.length === 0) return;
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    // deal with first half
    mergeSort(nums, start, Math.floor((start + end) / 2), temp);
    // deal with second half
    mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
    // merge
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid = Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
            temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = start; i <= end; i++) {
        nums[i] = temp[i];
    }
}