Using sort by descending order and ascending order and Priority Queue based on max heap and min heap to solve '2679. Sum in a Matrix'.
Example
2679. Sum in a Matrix
You are given a 0-indexed 2D integer array nums. Initially, your score is 0. Perform the following operations until the matrix becomes empty:
From each row in the matrix, select the largest number and remove it. In the case of a tie, it does not matter which number is chosen.
Identify the highest number amongst all those removed in step 1. Add that number to your score.
Return the final score.
Example 1:
Input: nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
Output: 15
Explanation: In the first operation, we remove 7, 6, 6, and 3. We then add 7 to our score. Next, we remove 2, 4, 5, and 2. We add 5 to our score. Lastly, we remove 1, 2, 3, and 1. We add 3 to our score. Thus, our final score is 7 + 5 + 3 = 15.
Answer
Priority Queue · Min heap
Both max heap and min heap are acceptable for heap sort algorithm.
var matrixSum = function(nums) {
const m = nums.length, n = nums[0].length, pqs = Array.from({length: m}, _ => new MyPriorityQueue())
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
pqs[i].push(nums[i][j])
}
}
let ans = 0
for (let j = 0; j < n; j++) {
let max = Number.MIN_SAFE_INTEGER
for (let i = 0; i < m; i++) {
max = Math.max(max, pqs[i].pop())
}
ans += max
}
return ans
};
class MyPriorityQueue {
constructor (ar = [], compare = (a, b) => a - b) {
this.heap = []
this.size = 0
this.compare = compare
while (ar.length) this.push(ar.pop())
}
swap(a, b) {
const t = this.heap[a]
this.heap[a] = this.heap[b]
this.heap[b] = t
}
getLeftIndex(index) {
return (index << 1) + 1
}
getRightIndex(index) {
return (index << 1) + 2
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
this.swap(index, leftIndex)
this.shiftDown(leftIndex)
}
if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
this.swap(index, rightIndex)
this.shiftDown(rightIndex)
}
}
getParentIndex(index) {
return index - 1 >> 1
}
shiftUp(index) {
const paretIndex = this.getParentIndex(index)
if (paretIndex >= 0 && this.compare(this.heap[paretIndex], this.heap[index]) > 0) {
this.swap(paretIndex, index)
this.shiftUp(paretIndex)
}
}
push(value) {
this.heap.push(value)
this.shiftUp(this.size++)
}
top() {
return this.heap[0]
}
pop() {
if (this.size === 0) return null
if (--this.size === 0) return this.heap.pop()
const top = this.top()
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
empty() {
return this.size === 0
}
}type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func matrixSum(nums [][]int) int {
m, n := len(nums), len(nums[0])
pqs := make([]IntHeap, m)
for i := 0; i < m; i++ {
pqs[i] = IntHeap{}
heap.Init(&pqs[i])
for j := 0; j < n; j++ {
heap.Push(&pqs[i], nums[i][j])
}
}
ans := 0
for j := 0; j < n; j++ {
maxVal := 0
for i := 0; i < m; i++ {
maxVal = max(maxVal, heap.Pop(&pqs[i]).(int))
}
ans += maxVal
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
function matrixSum($nums) {
$m = count($nums);
$n = count($nums[0]);
$pqs = array_fill(0, $m, null);
for ($i = 0; $i < $m; $i++) {
$pqs[$i] = new PriorityQueue();
for ($j = 0; $j < $n; $j++) {
$pqs[$i]->insert($nums[$i][$j], $nums[$i][$j]);
}
}
$ans = 0;
for ($j = 0; $j < $n; $j++) {
$maxVal = PHP_INT_MIN;
for ($i = 0; $i < $m; $i++) {
$maxVal = max($maxVal, $pqs[$i]->extract());
}
$ans += $maxVal;
}
return $ans;
}
}
class PriorityQueue extends SplPriorityQueue {
public function compare ($a, $b) {
return $b - $a;
}
}class Solution {
public int matrixSum(int[][] nums) {
int m = nums.length, n = nums[0].length;
PriorityQueue<Integer>[] pqs = new PriorityQueue[m];
for (int i = 0; i < m; i++) {
pqs[i] = new PriorityQueue<Integer>((a, b) -> a - b);
for (int j = 0; j < n; j++) {
pqs[i].offer(nums[i][j]);
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = 0;
for (int i = 0; i < m; i++) {
maxVal = Math.max(maxVal, pqs[i].poll());
}
ans += maxVal;
}
return ans;
}
}public class Solution {
public int MatrixSum(int[][] nums) {
int m = nums.Length, n = nums[0].Length;
PriorityQueue<int, int>[] pqs = new PriorityQueue<int, int>[m];
for (int i = 0; i < m; i++) {
pqs[i] = new PriorityQueue<int, int>();
for (int j = 0; j < n; j++) {
pqs[i].Enqueue(nums[i][j], nums[i][j]);
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = int.MinValue;
for (int i = 0; i < m; i++) {
maxVal = Math.Max(maxVal, pqs[i].Dequeue());
}
ans += maxVal;
}
return ans;
}
}class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
int m = nums.size(), n = nums[0].size();
vector<priority_queue<int>> pqs(m);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
pqs[i].emplace(nums[i][j]);
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < m; i++) {
maxVal = max(maxVal, pqs[i].top());
pqs[i].pop();
}
ans += maxVal;
}
return ans;
}
};class Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n, ans = len(nums), len(nums[0]), 0
pqs = [[] for _ in range(m)]
for i in range(0, m):
for j in range(0, n):
heappush(pqs[i], nums[i][j])
for j in range(0, n):
maxVal = -sys.maxsize
for i in range(0, m): maxVal = max(maxVal, heappop(pqs[i]))
ans += maxVal
return ansPriority Queue · Max heap
var matrixSum = function(nums) {
const m = nums.length, n = nums[0].length, pqs = Array.from({length: m}, _ => new MyPriorityQueue(void 0, (a, b) => b - a))
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
pqs[i].push(nums[i][j])
}
}
let ans = 0
for (let j = 0; j < n; j++) {
let max = Number.MIN_SAFE_INTEGER
for (let i = 0; i < m; i++) {
max = Math.max(max, pqs[i].pop())
}
ans += max
}
return ans
};
class MyPriorityQueue {
constructor (ar = [], compare = (a, b) => a - b) {
this.heap = []
this.size = 0
this.compare = compare
while (ar.length) this.push(ar.pop())
}
swap(a, b) {
const t = this.heap[a]
this.heap[a] = this.heap[b]
this.heap[b] = t
}
getLeftIndex(index) {
return (index << 1) + 1
}
getRightIndex(index) {
return (index << 1) + 2
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
if (leftIndex < this.size && this.compare(this.heap[index], this.heap[leftIndex]) > 0) {
this.swap(index, leftIndex)
this.shiftDown(leftIndex)
}
if (rightIndex < this.size && this.compare(this.heap[index], this.heap[rightIndex]) > 0) {
this.swap(index, rightIndex)
this.shiftDown(rightIndex)
}
}
getParentIndex(index) {
return index - 1 >> 1
}
shiftUp(index) {
const paretIndex = this.getParentIndex(index)
if (paretIndex >= 0 && this.compare(this.heap[paretIndex], this.heap[index]) > 0) {
this.swap(paretIndex, index)
this.shiftUp(paretIndex)
}
}
push(value) {
this.heap.push(value)
this.shiftUp(this.size++)
}
top() {
return this.heap[0]
}
pop() {
if (this.size === 0) return null
if (--this.size === 0) return this.heap.pop()
const top = this.top()
this.heap[0] = this.heap.pop()
this.shiftDown(0)
return top
}
empty() {
return this.size === 0
}
}type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func matrixSum(nums [][]int) int {
m, n := len(nums), len(nums[0])
pqs := make([]IntHeap, m)
for i := 0; i < m; i++ {
pqs[i] = IntHeap{}
heap.Init(&pqs[i])
for j := 0; j < n; j++ {
heap.Push(&pqs[i], nums[i][j])
}
}
ans := 0
for j := 0; j < n; j++ {
maxVal := 0
for i := 0; i < m; i++ {
maxVal = max(maxVal, heap.Pop(&pqs[i]).(int))
}
fmt.Println(maxVal);
ans += maxVal
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
function matrixSum($nums) {
$m = count($nums);
$n = count($nums[0]);
$pqs = array_fill(0, $m, null);
for ($i = 0; $i < $m; $i++) {
$pqs[$i] = new PriorityQueue();
for ($j = 0; $j < $n; $j++) {
$pqs[$i]->insert($nums[$i][$j], $nums[$i][$j]);
}
}
$ans = 0;
for ($j = 0; $j < $n; $j++) {
$maxVal = PHP_INT_MIN;
for ($i = 0; $i < $m; $i++) {
$maxVal = max($maxVal, $pqs[$i]->extract());
}
$ans += $maxVal;
}
return $ans;
}
}
class PriorityQueue extends SplPriorityQueue {
public function compare ($a, $b) {
return $a - $b;
}
}class Solution {
public int matrixSum(int[][] nums) {
int m = nums.length, n = nums[0].length;
PriorityQueue<Integer>[] pqs = new PriorityQueue[m];
for (int i = 0; i < m; i++) {
pqs[i] = new PriorityQueue<Integer>((a, b) -> b - a);
for (int j = 0; j < n; j++) {
pqs[i].offer(nums[i][j]);
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = 0;
for (int i = 0; i < m; i++) {
maxVal = Math.max(maxVal, pqs[i].poll());
}
ans += maxVal;
}
return ans;
}
}class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
int m = nums.size(), n = nums[0].size();
vector<priority_queue<int>> pqs(m);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
pqs[i].emplace(nums[i][j]);
}
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < m; i++) {
maxVal = max(maxVal, pqs[i].top());
pqs[i].pop();
}
ans += maxVal;
}
return ans;
}
};class Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n, ans = len(nums), len(nums[0]), 0
pqs = [[] for _ in range(m)]
for i in range(0, m):
for j in range(0, n):
heappush(pqs[i], -nums[i][j])
for j in range(0, n):
maxVal = -sys.maxsize
for i in range(0, m): maxVal = max(maxVal, -heappop(pqs[i]))
ans += maxVal
return ansSort · Descending order
Ssorting the array in descending order is not necessary, and it can also be sorted in ascending order.
var matrixSum = function(nums) {
const m = nums.length, n = nums[0].length
for (let i = 0; i < m; i++) {
nums[i].sort((a, b) => b - a)
}
let ans = 0
for (let j = 0; j < n; j++) {
let r = Number.MIN_SAFE_INTEGER
for (let i = 0; i < m; i++) {
r = Math.max(r, nums[i][j])
}
ans += r
}
return ans
};class Solution {
public int matrixSum(int[][] nums) {
int m = nums.length, n = nums[0].length;
for (int i = 0; i < m; i++) {
Arrays.sort(nums[i]);
reverse(nums[i], n);
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = 0;
for (int i = 0; i < m; i++) {
maxVal = Math.max(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}
public void reverse(int[] nums, int n) {
for (int i = 0; i < n >> 1; i++) {
int t = nums[i];
nums[i] = nums[n - i - 1];
nums[n - i - 1] = t;
}
}
}class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
int m = nums.size(), n = nums[0].size();
for (int i = 0; i < m; i++) {
sort(nums[i].begin(), nums[i].end(), greater<int>());
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < m; i++) {
maxVal = max(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}
};#define MAX(a, b) (a > b ? a : b)
static inline int compare(const void *pa, const void *pb) {
return *(int*)pb -*(int*)pa;
}
int matrixSum(int** nums, int numsSize, int* numsColSize){
for (int i = 0; i < numsSize; i++) {
qsort(nums[i], *numsColSize, sizeof(int), compare);
}
int ans = 0;
for (int j = 0; j < *numsColSize; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < numsSize; i++) {
maxVal = MAX(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}class Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n, ans = len(nums), len(nums[0]), 0
for i in range(0, m): nums[i].sort(reverse = True)
for j in range(0, n):
maxVal = -sys.maxsize
for i in range(0, m): maxVal = max(maxVal, nums[i][j])
ans += maxVal
return ansclass Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n, ans = len(nums), len(nums[0]), 0
for i in range(0, m): nums[i].sort(key = lambda x: -x)
for j in range(0, n):
maxVal = -sys.maxsize
for i in range(0, m): maxVal = max(maxVal, nums[i][j])
ans += maxVal
return ansSort · Ascending order
func matrixSum(nums [][]int) int {
m, n := len(nums), len(nums[0])
for i := 0; i < m; i++ {
sort.Ints(nums[i])
}
ans := 0
for j := 0; j < n; j++ {
maxVal := 0
for i := 0; i < m; i++ {
maxVal = max(maxVal, nums[i][j])
}
ans += maxVal
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}class Solution {
function matrixSum($nums) {
$m = count($nums);
$n = count($nums[0]);
for ($i = 0; $i < $m; $i++) {
rsort($nums[$i], SORT_NUMERIC);
}
$ans = 0;
for ($j = 0; $j < $n; $j++) {
$maxVal = PHP_INT_MIN;
for ($i = 0; $i < $m; $i++) {
$maxVal = max($maxVal, $nums[$i][$j]);
}
$ans += $maxVal;
}
return $ans;
}
}public class Solution {
public int MatrixSum(int[][] nums) {
int m = nums.Length, n = nums[0].Length;
for (int i = 0; i < m; i++) {
Array.Sort(nums[i]);
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = int.MinValue;
for (int i = 0; i < m; i++) {
maxVal = Math.Max(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}
}class Solution {
public:
int matrixSum(vector<vector<int>>& nums) {
int m = nums.size(), n = nums[0].size();
for (int i = 0; i < m; i++) {
sort(nums[i].begin(), nums[i].end());
}
int ans = 0;
for (int j = 0; j < n; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < m; i++) {
maxVal = max(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}
};#define MAX(a, b) (a > b ? a : b)
static inline int compare(const void *pa, const void *pb) {
return *(int*)pa -*(int*)pb;
}
int matrixSum(int** nums, int numsSize, int* numsColSize){
for (int i = 0; i < numsSize; i++) {
qsort(nums[i], *numsColSize, sizeof(int), compare);
}
int ans = 0;
for (int j = 0; j < *numsColSize; j++) {
int maxVal = INT_MIN;
for (int i = 0; i < numsSize; i++) {
maxVal = MAX(maxVal, nums[i][j]);
}
ans += maxVal;
}
return ans;
}class Solution:
def matrixSum(self, nums: List[List[int]]) -> int:
m, n, ans = len(nums), len(nums[0]), 0
for i in range(0, m): nums[i].sort()
for j in range(0, n):
maxVal = -sys.maxsize
for i in range(0, m): maxVal = max(maxVal, nums[i][j])
ans += maxVal
return ans
