Implement LU decomposition (without pivoting) to factor a square matrix A into a lower triangular matrix L and an upper triangular matrix U, such that A = L*U.
Algorithm (Doolittle):
1. U's first row = A's first row
2. L's first column = A's first column / U[0][0]
3. Iterate: compute U row by row, L column by column
Example:
Input: A = [[2, 1], [4, 3]]
Output: L = [[1, 0], [2, 1]], U = [[2, 1], [0, 1]]
**Explanation:** L*U = [[2+0, 1+0], [4+0, 2+1]] = [[2,1],[4,3]] = A ✓
Constraints:
Test Cases
Test Case 1
Input:
[[2, 1], [4, 3]]Expected:
A = L * U verifiedTest Case 2
Input:
[[1, 0], [0, 1]]Expected:
A = L * U verifiedTest Case 3
Input:
[[2, 1, 1], [4, 3, 3], [8, 7, 9]]Expected:
A = L * U verified+ 2 hidden test cases