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

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

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

Maximize Amount After Two Days of Conversions | Leetcode Question

When tackling the problem of maximizing the amount of currency after two days of conversions, we encounter an interesting graph-based problem that involves working with exchange rates between various currencies. In this article, we will explore this problem in detail, starting with the brute force approach and refining it to an optimized solution. Problem Explanation You are given a string initialCurrency (the starting currency), along with four arrays: pairs1 and rates1 : Represent exchange rates between currency pairs on Day 1. pairs2 and rates2 : Represent exchange rates between currency pairs on Day 2. The task is to maximize the amount of initialCurrency you can have after performing any number of conversions on both days. You can make conversions using Day 1 rates and then further conversions using Day 2 rates. Key Insights: Conversion rates are valid (no contradictions). Each currency can be converted back to its counterpart at a reciprocal rate (e.g., if USD -> EUR = 2....
Read more