LeetCode 1424: Diagonal Traverse II
Problem Description
Explanation
To traverse the array diagonally, we need to move in a zigzag pattern. We can achieve this by keeping track of the diagonal index sum (i+j) and storing elements in a map based on this sum. Then we can iterate through the map to get the elements in the desired order.
- Create a map to store elements based on the diagonal index sum (i+j).
- Traverse the 2D array and store elements in the map.
- Iterate through the map and add elements to the result list.
Time Complexity: O(N*M) where N is the number of rows and M is the number of columns in the input array.
Space Complexity: O(N*M) for storing elements in the map.
Solutions
import java.util.*;
class Solution {
public int[] findDiagonalOrder(List<List<Integer>> nums) {
Map<Integer, List<Integer>> map = new HashMap<>();
int rows = nums.size();
int resultSize = 0;
for (int i = 0; i < rows; i++) {
List<Integer> row = nums.get(i);
int cols = row.size();
for (int j = 0; j < cols; j++) {
int diagonalSum = i + j;
map.putIfAbsent(diagonalSum, new ArrayList<>());
map.get(diagonalSum).add(row.get(j));
resultSize++;
}
}
int[] result = new int[resultSize];
int idx = 0;
for (int key : map.keySet()) {
List<Integer> diagonalElements = map.get(key);
for (int i = diagonalElements.size() - 1; i >= 0; i--) {
result[idx++] = diagonalElements.get(i);
}
}
return result;
}
}Loading editor...