Last updated on February 12th, 2025 at 02:13 am
Here, we see a Diagonal Traverse LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Array, Matrix, Simulation
Companies
Level of Question
Medium
Diagonal Traverse LeetCode Solution
Table of Contents
1. Problem Statement
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
Example 1:
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Example 2:
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
<!-- wp:html -->
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-7231089257748111"
crossorigin="anonymous"></script>
<!-- horizontal ads -->
<ins class="adsbygoogle"
style="display:block"
data-ad-client="ca-pub-7231089257748111"
data-ad-slot="5889742421"
data-ad-format="auto"
data-full-width-responsive="true"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>
<!-- /wp:html -->
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Diagonal Traversal of a Matrix. The problem involves traversing the matrix diagonally and collecting elements in a specific order, which is a common matrix manipulation problem.
3. Code Implementation in Different Languages
3.1 Diagonal Traverse C++
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
vector<int> res;
map<int, vector<int>> mp;
for(int i = 0 ; i < mat.size() ; i++)
for(int j = 0 ; j < mat[0].size() ; j++)
mp[i + j].push_back(mat[i][j]);
for(auto i : mp) {
if((i.first)%2 == 0)
reverse(i.second.begin(), i.second.end());
for(auto k : i.second) res.push_back(k);
}
return res;
}
};
3.2 Diagonal Traverse Java
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
if (mat == null) {
throw new IllegalArgumentException("Input matrix is null");
}
if (mat.length == 0 || mat[0].length == 0) {
return new int[0];
}
int rows = mat.length;
int cols = mat[0].length;
int[] result = new int[rows * cols];
int r = 0;
int c = 0;
for (int i = 0; i < result.length; i++) {
result[i] = mat[r][c];
if ((r + c) % 2 == 0) {
if (c == cols - 1) {
r++;
} else if (r == 0) {
c++;
} else {
r--;
c++;
}
} else {
if (r == rows - 1) {
c++;
} else if (c == 0) {
r++;
} else {
r++;
c--;
}
}
}
return result;
}
}
3.3 Diagonal Traverse JavaScript
var findDiagonalOrder = function(mat) {
let rows = mat.length;
let cols = mat[0].length;
let result = new Array(rows + cols - 1).fill(null).map(() => []);
for(let row = 0; row < rows; row++) {
for(let col = 0; col < cols; col++) {
if((row + col) % 2 === 0) result[row + col].unshift(mat[row][col]);
else result[row + col].push(mat[row][col]);
}
}
return result.flat();
};
3.4 Diagonal Traverse Python
class Solution(object):
def findDiagonalOrder(self, mat):
d={}
for i in range(len(mat)):
for j in range(len(mat[i])):
if i + j not in d:
d[i+j] = [mat[i][j]]
else:
d[i+j].append(mat[i][j])
ans= []
for entry in d.items():
if entry[0] % 2 == 0:
[ans.append(x) for x in entry[1][::-1]]
else:
[ans.append(x) for x in entry[1]]
return ans
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(m * n) | O(m * n) |
| Java | O(m * n) | O(1) |
| JavaScript | O(m * n) | O(m + n) |
| Python | O(m * n) | O(m * n) |
- The problem involves Diagonal Traversal of a Matrix.
- The time complexity is O(m * n) for all implementations, as every element in the matrix is visited once.
- The space complexity varies depending on the language and the data structures used.