Another Casual Coder

Famous algorithms like QuickSort and MergeSort are well-known for their nLogn time performance and indeed for general purposes they are the best. However, sorting can be done faster than nLogn if certain conditions apply. For example, the key to this problem is the fact that the numbers in the matrix are in between [0..1000]. This allows you to use CountingSort to perform a linear sort. Doing this you can actually solve this problem in NxM time. Code is below, cheers, ACC.

Sum in a Matrix - LeetCode

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.

Input: nums = [[1]]
Output: 1
Explanation: We remove 1 and add it to the answer. We return 1.

public int MatrixSum(int[][] nums)
{
 //Sort in nxm using countingSort
 for (int r = 0; r < nums.Length; r++)
 {
 int[] bucket = new int[1005];
 for (int c = 0; c < nums[r].Length; c++)
 bucket[nums[r][c]]++;
 int indexCol = 0;
 for (int i = bucket.Length - 1; i >= 0; i--)
 {
 while (bucket[i] > 0)
 {
 nums[r][indexCol] = i;
 indexCol++;
 bucket[i]--;
 }
 }
 }
 //Process max in nxm
 int retVal = 0;
 for (int c = 0; c < nums[0].Length; c++)
 {
 int max = -1;
 for (int r = 0; r < nums.Length; r++)
 max = Math.Max(max, nums[r][c]);
 retVal += max;
 }
 return retVal;
}