Posts published in “Algorithms”

花花酱 LeetCode 1093. Statistics from a Large Sample

By zxi on February 6, 2020

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

The middle element, if the elements of the sample were sorted and the number of elements is odd;
The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

Solution: TreeMap

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<double> sampleStats(vector<int>& count) {

int counts = 0;

int minVal = 255;

int maxVal = 0;

int mode = -1;

int modeCount = 0;

long sum = 0;

map<int, int> m;

for (int i = 0; i <= 255; ++i) {

if (!count[i]) continue;

sum += static_cast<long>(i) * count[i];

minVal = min(minVal, i);

maxVal = max(maxVal, i);

if (count[i] > modeCount) {

mode = i;

modeCount = count[i];

}

m[counts += count[i]] = i;

}

auto it1 = m.lower_bound(counts / 2);

double median = it1->second;

auto it2 = next(it1);

if (counts % 2 == 0 && it2 != m.end() && it1->first == counts / 2) {

median = (median + it2->second) / 2;

}

return {minVal, maxVal, static_cast<double>(sum) / counts, median, mode};

}

};

花花酱 LeetCode 912. Sort an Array

By zxi on February 1, 2020

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

Since n <= 50000, any O(n^2) won’t pass, we need O(nlogn) or better

Solution 1: QuickSort

Time complexity: O(nlogn) ~ O(n^2)
Space complexity: O(logn) ~ O(n)

C++

// Author: Huahua, 60 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

function<void(int, int)> quickSort = [&](int l, int r) {

if (l >= r) return;

int i = l;

int j = r;

int p = nums[l + rand() % (r - l + 1)];

while (i <= j) {

while (nums[i] < p) ++i;

while (nums[j] > p) --j;

if (i <= j)

swap(nums[i++], nums[j--]);

}

quickSort(l, j);

quickSort(i, r);

};

quickSort(0, nums.size() - 1);

return nums;

}

};

Solution 2: Counting Sort

Time complexity: O(n)
Space complexity: O(max(nums) – min(nums))

C++

// Author: Huahua, 54 ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto [min_it, max_it] = minmax_element(begin(nums), end(nums));

int l = *min_it, r = *max_it;

vector<int> count(r - l + 1);

for (int n : nums) ++count[n - l];

int index = 0;

for (int i = 0; i < count.size(); ++i)

while (count[i]--) nums[index++] = i + l;

return nums;

}

};

Solution 2: HeapSort

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua, 72ms

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

priority_queue<int> q(begin(nums), end(nums));

int i = nums.size();

while (!q.empty()) {

nums[--i] = q.top();

q.pop();

}

return nums;

}

};

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

auto heapify = [&](int i, int e) {

while (i <= e) {

int l = 2 * i + 1;

int r = 2 * i + 2;

int j = i;

if (l <= e && nums[l] > nums[j]) j = l;

if (r <= e && nums[r] > nums[j]) j = r;

if (j == i) break;

swap(nums[i], nums[j]);

swap(i, j);

}

};

const int n = nums.size();

// Init heap

for (int i = n / 2; i >= 0; i--)

heapify(i, n - 1);

// Get min.

for (int i = n - 1; i >= 1; i--) {

swap(nums[0], nums[i]);

heapify(0, i - 1);

}

return nums;

}

};

Solution 3: MergeSort

Time complexity: O(nlogn)
Space complexity: O(logn + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

vector<int> t(nums.size());

function<void(int, int)> mergeSort = [&](int l, int r) {

if (l + 1 >= r) return;

int m = l + (r - l) / 2;

mergeSort(l, m);

mergeSort(m, r);

int i1 = l;

int i2 = m;

int index = 0;

while (i1 < m || i2 < r)

if (i2 == r || (i1 < m && nums[i1] < nums[i2]))

t[index++] = nums[i1++];

else

t[index++] = nums[i2++];

std::copy(begin(t), begin(t) + index, begin(nums) + l);

};

mergeSort(0, nums.size());

return nums;

}

};

Solution 4: BST

Time complexity: (nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortArray(vector<int>& nums) {

multiset<int> s(begin(nums), end(nums));

return {begin(s), end(s)};

}

};

花花酱 LeetCode 162. Find Peak Element

By zxi on January 31, 2020

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

Solution: Binary Search

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findPeakElement(const vector<int> &num) {

int l = 0, r = num.size() - 1; // preventing OOB

while (l < r) {

int m = l + (r - l) / 2;

// Find the first m s.t. num[m] > num[m + 1]

if (num[m] > num[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 35. Search Insert Position

By zxi on January 31, 2020

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

Solution: Binary Search

Find the number or upper bound if doesn’t exist.

Time complexity: O(logn)
Space complexity: O1)

C++

// Author: Huahua

class Solution {

public:

int searchInsert(vector<int>& nums, int target) {

int l = 0, r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1299. Replace Elements with Greatest Element on Right Side

By zxi on December 28, 2019

Given an array arr, replace every element in that array with the greatest element among the elements to its right, and replace the last element with -1.

After doing so, return the array.

Example 1:

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Constraints:

1 <= arr.length <= 10^4
1 <= arr[i] <= 10^5

Solution: Scan from right to left

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> replaceElements(vector<int>& arr) {

int g = -1;

for (int i = arr.size() - 1; i >= 0; --i)

g = max(g, exchange(arr[i], g));

return arr;

}

};