Skip to main content

Sort Matrix by Diagonals | Leetcode 3446 | How to Sort a Matrix by Diagonals

Sorting a square matrix based on its diagonals is an interesting problem that tests our understanding of array manipulation and sorting techniques.

Understanding the Problem in Simple Terms

We are given an n × n square matrix, and we need to sort its diagonals according to the following rules:

  1. Diagonals in the bottom-left triangle (including the middle diagonal) should be sorted in non-increasing order (descending).
  2. Diagonals in the top-right triangle should be sorted in non-decreasing order (ascending).

Example Walkthrough

Example 1

Input:

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

Output:

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

Example 2

Input:

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

Output:

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


Brute Force Approach – Sorting Each Diagonal Individually

Step-by-Step Approach

  1. Extract all diagonals from the matrix.
  2. Sort each diagonal according to the required order.
  3. Place the sorted diagonals back into the matrix.

Time Complexity:

  • Extracting diagonals: O(n²)
  • Sorting each diagonal: O(n log n)
  • Placing them back: O(n²)
  • Total Complexity: O(n² log n)

C++ Implementation

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Solution
{
public:
    vector<vector<int>> sortMatrix(vector<vector<int>> &grid)
    {
        int n = grid.size();

        // Sort all diagonals separately
        for (int d = -(n - 1); d <= (n - 1); d++)
        {
            vector<int> diag;

            // Collect diagonal elements
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i - j == d)
                    {
                        diag.push_back(grid[i][j]);
                    }
                }
            }

            // Sort the diagonal accordingly
            if (d >= 0)
                sort(diag.begin(), diag.end(), greater<int>()); // Descending order
            else
                sort(diag.begin(), diag.end()); // Ascending order

            // Put sorted elements back
            int index = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (i - j == d)
                    {
                        grid[i][j] = diag[index++];
                    }
                }
            }
        }
        return grid;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> grid = {{1, 7, 3}, {9, 8, 2}, {4, 5, 6}};

    vector<vector<int>> sortedGrid = sol.sortMatrix(grid);

    for (auto row : sortedGrid)
    {
        for (int num : row)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}


Drawbacks of the Brute Force Approach

  • We are iterating over all elements multiple times.
  • Sorting each diagonal separately increases the runtime.

Optimized Approach – Using Hash Map for Efficient Sorting

Instead of checking every element manually, we can use a hash map where:

  • Key = (i - j) (which uniquely identifies each diagonal)
  • Value = List of elements in that diagonal

Steps to Optimize

  1. Store all diagonal elements in a hash map.
  2. Sort each diagonal efficiently (descending for bottom-left, ascending for top-right).
  3. Reconstruct the matrix using sorted diagonals.

Optimized Code Implementation(C++)

#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution
{
public:
    vector<vector<int>> sortMatrix(vector<vector<int>> &grid)
    {
        int n = grid.size();
        unordered_map<int, vector<int>> diagMap;

        // Collect all diagonals
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                diagMap[i - j].push_back(grid[i][j]);
            }
        }

        // Sort diagonals based on their positions
        for (auto &[key, values] : diagMap)
        {
            if (key >= 0)
            {
                sort(values.begin(), values.end(), greater<int>()); // Descending for bottom-left
            }
            else
            {
                sort(values.begin(), values.end()); // Ascending for top-right
            }
        }

        // Fill sorted values back into the matrix
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                grid[i][j] = diagMap[i - j].back();
                diagMap[i - j].pop_back();
            }
        }

        return grid;
    }
};


Time Complexity of Optimized Solution

  • Collecting diagonals: O(n²)
  • Sorting diagonals: O(n log n)
  • Reconstructing matrix: O(n²)
  • Total Complexity: O(n² log n), but it reduces redundant computations.

  • We explored two solutions: a simple brute force approach and an optimized hash map approach.
  • The optimized method reduces unnecessary operations and sorts diagonals efficiently.
  • Understanding how to identify diagonals using (i - j) is the key to solving this problem effectively.


FAQs

1. Can we solve this problem in O(n²) time?
Not exactly, since sorting takes O(n log n). However, using bucket sort (if constraints allow) could make sorting nearly O(n).

2. Why did we use an unordered_map?
It helps in efficiently storing and retrieving diagonal elements using (i - j) as a unique key.

Popular posts from this blog

Top 10 Beginner-Friendly LeetCode Questions and Their Solutions

If you're new to solving coding problems on LeetCode, it can feel overwhelming. Where do you start? Which problems are suitable for beginners? Don’t worry! In this blog post, I’ll guide you through   10 beginner-friendly LeetCode questions   that are perfect for getting started on your coding journey. These problems will help you build confidence, improve your problem-solving skills, and lay a solid foundation in data structures and algorithms. Why Start with Beginner-Friendly Problems? Before diving into advanced topics like dynamic programming or graph theory, it’s essential to: Build a strong foundation in basic programming concepts. Understand how to approach a coding problem methodically. Gain familiarity with LeetCode’s platform and its problem structure. The following problems are simple yet impactful, designed to introduce you to common techniques like loops, arrays, strings, and basic math operations. 10 Beginner-Friendly LeetCode Problems 1.  Two Sum (Easy) Prob...
Read more

Maximum Difference Between Even and Odd Frequency | LeetCode

We are given a string consisting of lowercase English letters. Our task is to find the maximum difference between the frequency of two characters in the string such that: One of the characters has an even frequency . The other character has an odd frequency . The difference is calculated as:  odd_frequency - even_frequency We need to return the maximum possible difference between the odd and even frequencies. Example Walkthrough Let's take a couple of examples to better understand the problem: Example 1: Input:  s = "aaaaabbc" Frequencies: 'a' → 5 (odd) 'b' → 2 (even) 'c' → 1 (odd) Here, the maximum odd frequency is 5 (for 'a') and the maximum even frequency is 2 (for 'b'). Therefore, the result is: maxOdd - maxEven = 5 - 2 = 3 Example 2: Input:  s = "abcabcab" Frequencies: 'a' → 3 (odd) 'b' → 2 (even) 'c' → 2 (even) The maximum odd frequency is 3 (for 'a') and the maximum even fr...
Read more

Count Mentions Per User | Leetcode | Problem Explanation and Solution Approaches

Tracking mentions in messages is a common task in communication-based applications. This blog post breaks down a complex problem, "Count Mentions Per User," and walks through how to solve it efficiently with a clear understanding of all rules and constraints. Problem Statement You are given: An integer numberOfUsers representing the total number of users. An array events where each element is of size n x 3 and describes either a "MESSAGE" or an "OFFLINE" event. Each event can be one of the following types: MESSAGE Event : ["MESSAGE", "timestamp", "mentions_string"] Indicates that users are mentioned in a message at a specific timestamp. The mentions_string can contain: id<number> : Mentions a specific user (e.g., id0 , id1 ). ALL : Mentions all users (online or offline). HERE : Mentions only users who are online at the time. OFFLINE Event : ["OFFLINE", "timestamp", "id<number>"] In...
Read more