Posts tagged as “median”

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

By zxi on October 21, 2021

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= x, grid[i][j] <= 10⁴

Solution: Median

To achieve minimum operations, the uni-value must be the median of the array.

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

// Author; Huahua

class Solution {

public:

int minOperations(vector<vector<int>>& grid, int x) {

const int mn = grid.size() * grid[0].size();

vector<int> nums;

nums.reserve(mn);

for (const auto& row : grid)

nums.insert(end(nums), begin(row), end(row));

nth_element(begin(nums), begin(nums) + mn / 2, end(nums));

const int median = nums[mn / 2];

int ans = 0;

for (int v : nums) {

if (abs(v - median) % x) return -1;

ans += abs(v - median) / x;

}

return ans;

}

};

花花酱 LeetCode 1478. Allocate Mailboxes

By zxi on June 14, 2020

Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Example 3:

Input: houses = [7,4,6,1], k = 1
Output: 8

Example 4:

Input: houses = [3,6,14,10], k = 4
Output: 0

Constraints:

n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
Array houses contain unique integers.

Solution: DP

First, we need to sort the houses by their location.

This is a partitioning problem, e.g. optimal solution to partition first N houses into K groups. (allocating K mailboxes for the first N houses).

The key of this problem is to solve a base case, optimally allocating one mailbox for houses[i~j], The intuition is to put the mailbox in the middle location, this only works if there are only tow houses, or all the houses are evenly distributed. The correct location is the “median position” of a set of houses. For example, if the sorted locations are [1,2,3,100], the average will be 26 which costs 146 while the median is 2, and the cost becomes 100.

dp[i][k] := min cost to allocate k mailboxes houses[0~i].

base cases:

dp[i][1] = cost(0, i), min cost to allocate one mailbox.
dp[i][k] = 0 if k > i, more mailboxes than houses. // this is actually a pruning.

transition:

dp[i][k] = min(dp[p][k-1] + cost(p + 1, i)) 0 <= p < i,

allocate k-1 mailboxes for houses[0~p], and allocate one for houses[p+1~i]

ans:

dp[n-1][k]

Time complexity: O(n^3)
Space complexity: O(n^2) -> O(n)

C++

// Author: Huahua

class Solution {

public:

int minDistance(vector<int>& houses, int k) {

constexpr int kInf = 1e9;

const int n = houses.size();

sort(begin(houses), end(houses));

vector<vector<int>> dp(n + 1, vector<int>(n + 1, kInf));

vector<vector<int>> costs(n + 1, vector<int>(n + 1, kInf));

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

int& ans = costs[i][j];

if (ans != kInf) return ans;

const int m = i + (j - i) / 2;

int box = 0;

if ((j - i + 1) & 1) // odd number of houses.

box = houses[m];

else // even number of houses.

box = (houses[m] + houses[m + 1]) / 2;

ans = 0;

for (int h = i; h <= j; ++h)

ans += abs(houses[h] - box);

return ans;

};

// min cost to allocate k mailboxes for houses[0~i].

function<int(int, int)> solve = [&](int i, int k) {

if (k > i) return 0; // more mailboxs than houses.

if (k == 1) return cost(0, i);

int& ans = dp[i][k];

if (ans != kInf) return ans;

for (int p = 0; p < i; ++p)

ans = min(ans, solve(p, k - 1) + cost(p + 1, i));

return ans;

};

return solve(n - 1, k);

}

};

O(1) time to compute cost. O(n) Time and space for pre-processing.

C++

// Author: Huahua

vector<int> sums(n + 1);

for (int i = 1; i <= n; ++i)

sums[i] = sums[i - 1] + houses[i - 1];

// min cost to allocate one mailbox for houses[i~j].

auto cost = [&](int i, int j) {

const int m1 = (i + j) / 2;

const int m2 = (i + j + 1) / 2;

const int center = (houses[m1] + houses[m2]) / 2;

return (m1 - i + 1) * center - (sums[m1 + 1] - sums[i])

+ (sums[j + 1] - sums[m2]) - (j - m2 + 1) * center;

};

花花酱 LeetCode 1471. The k Strongest Values in an Array

By zxi on June 6, 2020

Given an array of integers arr and an integer k.

Return a list of the strongest k values in the array. return the answer in any arbitrary order.

Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n - 1) / 2) in the sorted list (0-indexed).

For arr = [6, -3, 7, 2, 11], n = 5 and the median is obtained by sorting the array arr = [-3, 2, 6, 7, 11] and the median is arr[m] where m = ((5 - 1) / 2) = 2. The median is 6.
For arr = [-7, 22, 17, 3], n = 4 and the median is obtained by sorting the array arr = [-7, 3, 17, 22] and the median is arr[m] where m = ((4 - 1) / 2) = 1. The median is 3.

Example 1:

Input: arr = [1,2,3,4,5], k = 2
Output: [5,1]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,1,4,2,3]. The strongest 2 elements are [5, 1]. [1, 5] is also accepted answer.
Please note that although |5 - 3| == |1 - 3| but 5 is stronger than 1 because 5 > 1.

Example 2:

Input: arr = [1,1,3,5,5], k = 2
Output: [5,5]
Explanation: Median is 3, the elements of the array sorted by the strongest are [5,5,1,1,3]. The strongest 2 elements are [5, 5].

Example 3:

Input: arr = [6,7,11,7,6,8], k = 5
Output: [11,8,6,6,7]
Explanation: Median is 7, the elements of the array sorted by the strongest are [11,8,6,6,7,7].
Any permutation of [11,8,6,6,7] is accepted.

Example 4:

Input: arr = [6,-3,7,2,11], k = 3
Output: [-3,11,2]

Example 5:

Input: arr = [-7,22,17,3], k = 2
Output: [22,17]

Constraints:

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

Solution 1: quick selection + sort

Step 1: find the median element m
Step 2: Sort the array according to m
Step 3: output the first k elements of the sorted array.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getStrongest(vector<int>& arr, int k) {

const int n = arr.size();

const int i = (n - 1) / 2;

// sort(begin(arr), end(arr));

nth_element(begin(arr), begin(arr) + i, end(arr));

const int m = arr[i];

sort(begin(arr), end(arr), [&](const int x, const int y) {

return abs(x - m) != abs(y - m) ? abs(x - m) > abs(y - m) : x > y;

});

return {begin(arr), begin(arr) + k};

}

};

花花酱 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 480. Sliding Window Median

By zxi on January 28, 2018

题目大意：让你求移动窗口的中位数。

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Median

--------------- -----

[1 3 -1] -3 5 3 6 7 1

1 [3 -1 -3] 5 3 6 7 -1

1 3 [-1 -3 5] 3 6 7 -1

1 3 -1 [-3 5 3] 6 7 3

1 3 -1 -3 [5 3 6] 7 5

1 3 -1 -3 5 [3 6 7] 6

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk + (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

// Author: Huahua

// Running time: 99 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

std::sort(window.begin(), window.end());

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::find(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

C++ / vector + binary_search for deletion.

// Author: Huahua

// Running time: 84 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

vector<int> window(nums.begin(), nums.begin() + k - 1);

std::sort(window.begin(), window.end());

for (int i = k - 1; i < nums.size(); ++i) {

window.push_back(nums[i]);

auto it = prev(window.end(), 1);

auto const insertion_point =

std::upper_bound(window.begin(), it, *it);

std::rotate(insertion_point, it, it + 1);

ans.push_back((static_cast<double>(window[k / 2]) + window[(k - 1) / 2]) / 2);

window.erase(std::lower_bound(window.begin(), window.end(), nums[i - k + 1]));

}

return ans;

}

};

Java

// Author: Huahua

// Running time: 60 ms

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = 0;

while (i < window.length - 1 && val > window[i]) ++i;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = 0;

while (i < window.length && val != window[i]) ++i;

while (i < window.length - 1) window[i] = window[++i];

}

Java / Binary Search

// Author: Huahua

// Running time: 47 ms (<98.96%)

class Solution {

public double[] medianSlidingWindow(int[] nums, int k) {

if (k == 0) return new double[0];

double[] ans = new double[nums.length - k + 1];

int[] window = new int[k];

for (int i = 0; i < k; ++i)

window[i] = nums[i];

Arrays.sort(window);

for (int i = k; i <= nums.length; ++i) {

ans[i - k] = ((double)window[k / 2] + window[(k - 1)/2]) / 2;

if (i == nums.length) break;

remove(window, nums[i - k]);

insert(window, nums[i]);

}

return ans;

}

// Insert val into window, window[k - 1] is empty before inseration

private void insert(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

if (i < 0) i = - i - 1;

int j = window.length - 1;

while (j > i) window[j] = window[--j];

window[j] = val;

}

// Remove val from window and shrink it.

private void remove(int[] window, int val) {

int i = Arrays.binarySearch(window, val);

while (i < window.length - 1) window[i] = window[++i];

}

Python

"""

Author: Huahua

Running time: 161 ms (< 93.75%)

"""

class Solution:

def medianSlidingWindow(self, nums, k):

if k == 0: return []

ans = []

window = sorted(nums[0:k])

for i in range(k, len(nums) + 1):

ans.append((window[k // 2] + window[(k - 1) // 2]) / 2.0)

if i == len(nums): break

index = bisect.bisect_left(window, nums[i - k])

window.pop(index)

bisect.insort_left(window, nums[i])

return ans

Solution 2: BST

// Author: Huahua

// Running time: 68 ms

class Solution {

public:

vector<double> medianSlidingWindow(vector<int>& nums, int k) {

vector<double> ans;

if (k == 0) return ans;

multiset<int> window(nums.begin(), nums.begin() + k);

auto mid = next(window.begin(), (k - 1) / 2);

for (int i = k; i <= nums.size(); ++i) {

ans.push_back((static_cast<double>(*mid) +

*next(mid, (k + 1) % 2)) / 2.0);

if (i == nums.size()) break;

window.insert(nums[i]);

if (nums[i] < *mid) --mid;

if (nums[i - k] <= *mid) ++mid;

window.erase(window.lower_bound(nums[i - k]));

}

return ans;

}

};

Related Problems: