HackerRank Diagonal Difference Java Solution Explained
Problem Overview
Original Problem: Diagonal Difference | HackerRank
Difficulty: Easy
Category: Arrays, Math
Description: Given a square matrix of integers, calculate the absolute difference between the sum of its primary diagonal (top-left to bottom-right) and secondary diagonal (top-right to bottom-left). Return the result as an integer.
This problem, part of HackerRank’s One Week Preparation Kit, is a great way for beginners to practice working with 2D arrays and basic math operations in Java, essential skills for coding interviews.
Understanding the Problem
The Diagonal Difference problem involves a square matrix (equal number of rows and columns) where you need to compute the sum of elements along two diagonals: the primary diagonal (from top-left to bottom-right) and the secondary diagonal (from top-right to bottom-left). The goal is to find the absolute difference between these sums. For example, in a 3x3 matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]], the primary diagonal sum is 1 + 5 + 9 = 15, the secondary diagonal sum is 3 + 5 + 7 = 15, and the absolute difference is |15 - 15| = 0.
Input and Output
Input:
First line: An integer n, the number of rows and columns in the square matrix.
Next n lines: Each contains n space-separated integers arr[i][j].
Output:
An integer representing the absolute difference between the sums of the primary and secondary diagonals.
Constraints:
1 ≤ n ≤ 100
-100 ≤ arr[i][j] ≤ 100
The matrix is square (n rows and n columns).
Initial Reasoning
To solve this, we need to:
Iterate through the matrix to compute the sum of the primary diagonal.
Compute the sum of the secondary diagonal.
Calculate the absolute difference between these sums using Math.abs.
Use a single loop to compute both sums simultaneously, as both diagonals can be accessed using the same row index.
This approach is efficient with O(n) time complexity and O(1) extra space, ideal for the problem’s constraints.
Thought Process
Here’s the step-by-step logic:
Understand Diagonal Indices:
Primary diagonal: Elements where row index equals column index (arr[i][i]). For a 3x3 matrix, these are arr[0][0], arr[1][1], arr[2][2].
Secondary diagonal: Elements where row index i and column index n-1-i sum to n-1 (arr[i][n-1-i]). For a 3x3 matrix, these are arr[0][2], arr[1][1], arr[2][0].
Single-Pass Calculation:
Use one loop from i = 0 to i < n to access both diagonal elements at each row.
Add arr[i][i] to the primary diagonal sum.
Add arr[i][n-1-i] to the secondary diagonal sum.
Compute Absolute Difference:
After the loop, calculate Math.abs(primarySum - secondarySum).
Since elements are in [-100, 100] and n ≤ 100, the sums fit within an int.
Edge Cases:
If n = 1, the matrix is [1x1], so both diagonals have the same element (arr[0][0]), and the difference is 0.
Negative numbers are allowed, so ensure sums handle negative values correctly.
The constraints guarantee a square matrix and valid inputs, so no additional validation is needed.
Pseudocode
// diagonalDifference method:
Initialize variables for primary and secondary diagonal sums
For each row in the matrix
Add the relevant value to the primary diagonal sum
Add the relevant value to the secondary diagonal sum
Calculate the absolute difference
Return the absolute difference
Solution Code
// Note: This is one of many possible solutions
// Note: Variable names have been updated from the original template for clarity and to follow Java naming conventions (e.g., 'arr' to 'matrix')
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static int diagonalDifference(List<List<Integer>> matrix) {
int primarySum = 0;
int secondarySum = 0;
int size = matrix.size();
// Calculate sums of primary and secondary diagonals in one loop
for (int i = 0; i < size; i++) {
primarySum += matrix.get(i).get(i);
secondarySum += matrix.get(i).get(size - 1 - i);
}
// Return absolute difference
return Math.abs(primarySum - secondarySum);
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int size = Integer.parseInt(bufferedReader.readLine().trim());
List<List<Integer>> matrix = new ArrayList<>();
IntStream.range(0, size).forEach(i -> {
try {
matrix.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList()));
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
int result = Result.diagonalDifference(matrix);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Step-by-Step Explanation
Let’s break down the Java solution for beginners:
Input Handling:
The main method reads:
size, the number of rows/columns, using Integer.parseInt(bufferedReader.readLine().trim()).
size lines of size space-separated integers, processed into a List<List<Integer>> using Stream.of and map(Integer::parseInt).
The matrix is stored as a List<List<Integer>>, where each inner list represents a row.
Initialize Variables:
In diagonalDifference, initialize primarySum and secondarySum to 0 to store the diagonal sums.
Store matrix.size() in size for clarity and to avoid repeated calls.
Calculate Diagonal Sums:
Use a single loop from i = 0 to i < size.
For the primary diagonal, add matrix.get(i).get(i).
For the secondary diagonal, add matrix.get(i).get(size - 1 - i).
Since elements are in [-100, 100] and n ≤ 100, int is sufficient for sums (max sum = 100 × 100 = 10,000).
Compute Absolute Difference:
Calculate Math.abs(primarySum - secondarySum) to ensure a non-negative result.
Return this value as an int.
Output Handling:
Write the result to the output file using bufferedWriter.write(String.valueOf(result)).
Add a newline with bufferedWriter.newLine().
Close bufferedReader and bufferedWriter to prevent resource leaks.
Common Mistakes to Avoid
Here are common pitfalls for beginners:
Incorrect Diagonal Indices: Using wrong indices for the secondary diagonal (e.g., matrix[i][i] instead of matrix[i][size-1-i]) can lead to incorrect sums. Always verify the column index for the secondary diagonal.
Using Nested Loops: Iterating over all elements with nested loops (O(n²)) is unnecessary, as only diagonal elements are needed (O(n)).
Forgetting Absolute Value: Returning primarySum - secondarySum without Math.abs can produce a negative result, failing the requirement for an absolute difference.
Real-World Application
The Diagonal Difference problem is relevant in fields like image processing and data analysis, where matrix operations are common. For example, in computer vision, diagonal sums of a matrix might represent features like edge intensity in an image. In graph theory, matrices represent connections, and diagonal properties can indicate structural patterns. This problem teaches 2D array traversal and indexing, skills used in scientific computing and machine learning.
FAQs
Q: Why use a single loop instead of nested loops?
A: A single loop accesses only the diagonal elements (O(n)), while nested loops iterate over all elements (O(n²)), which is inefficient for this problem.
Q: Can I convert the List to a 2D array?
A: Yes, but the List<List<Integer>> format is provided by the template and is sufficient. Converting to a 2D array adds complexity without benefit for this problem.
Q: Why use Math.abs for the result?
A: The problem requires the absolute difference, so Math.abs ensures the result is non-negative, regardless of which diagonal sum is larger.