2025-08-28 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's August LeetCoding Challenge with cpp.

August LeetCoding Challenge 28

Description

Sort Matrix by Diagonals

You are given an n x n square matrix of integers grid. Return the matrix such that:

  • The diagonals in the bottom-left triangle (including the middle diagonal) are sorted in non-increasing order.
  • The diagonals in the top-right triangle are sorted in non-decreasing order.

 

Example 1:

Input: grid = [[1,7,3],[9,8,2],[4,5,6]]

Output: [[8,2,3],[9,6,7],[4,5,1]]

Explanation:

The diagonals with a black arrow (bottom-left triangle) should be sorted in non-increasing order:

  • [1, 8, 6] becomes [8, 6, 1].
  • [9, 5] and [4] remain unchanged.

The diagonals with a blue arrow (top-right triangle) should be sorted in non-decreasing order:

  • [7, 2] becomes [2, 7].
  • [3] remains unchanged.

Example 2:

Input: grid = [[0,1],[1,2]]

Output: [[2,1],[1,0]]

Explanation:

The diagonals with a black arrow must be non-increasing, so [0, 2] is changed to [2, 0]. The other diagonals are already in the correct order.

Example 3:

Input: grid = [[1]]

Output: [[1]]

Explanation:

Diagonals with exactly one element are already in order, so no changes are needed.

 

Constraints:

  • grid.length == grid[i].length == n
  • 1 <= n <= 10
  • -105 <= grid[i][j] <= 105

Solution

class Solution {
public:
  vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
    vector<int> countainer;
    int n = grid.size();
    for(int i = 0; i < n - 1; ++i) {
      int row = 0;
      int col = n - 1 - i;
      for(int j = 0; col + j < n; ++j) {
        countainer.push_back(grid[row + j][col + j]);
      }
      sort(countainer.begin(), countainer.end());
      for(int j = 0; col + j < n; ++j) {
        grid[row + j][col + j] = countainer[j];
      }
      countainer.clear();
    }
    for(int i = 0; i < n; ++i) {
      int row = i;
      int col = 0;
      for(int j = 0; row + j < n; ++j) {
        countainer.push_back(grid[row + j][col + j]);
      }
      sort(countainer.begin(), countainer.end(), greater<int>());
      for(int j = 0; row + j < n; ++j) {
        grid[row + j][col + j] = countainer[j];
      }
      countainer.clear();
    }
    return grid;
  }
};

// Accepted
// 1306/1306 cases passed (8 ms)
// Your runtime beats 66.46 % of cpp submissions
// Your memory usage beats 93.21 % of cpp submissions (41.9 MB)
Algorithm