Given a 3-D array arr[l][m][n], the task is to find the minimum path sum from the first cell of the array to the last cell of the array. We can only traverse to adjacent element, i.e., from a given cell (i, j, k), cells (i+1, j, k), (i, j+1, k) and (i, j, k+1) can be traversed, diagonal traversing is not allowed, We may assume that all costs are positive integers.
Examples:
Input : arr[][][]= { {{1, 2}, {3, 4}},
{{4, 8}, {5, 2}} };
Output : 9
Explanation : arr[0][0][0] + arr[0][0][1] +
arr[0][1][1] + arr[1][1][1]
Input : { { {1, 2}, {4, 3}},
{ {3, 4}, {2, 1}} };
Output : 7
Explanation : arr[0][0][0] + arr[0][0][1] +
arr[0][1][1] + arr[1][1][1]
Let us consider a 3-D array arr[2][2][2] represented by a cuboid having values as:
arr[][][] = {{{1, 2}, {3, 4}},
{ {4, 8}, {5, 2}}};
Result = 9 is calculated as:
This problem is similar to Min cost path. and can be solved using Dynamic Programming.
// Array for storing result
int tSum[l][m][n];
tSum[0][0][0] = arr[0][0][0];
/* Initialize first row of tSum array */
for (i = 1; i < l; i++)
tSum[i][0][0] = tSum[i-1][0][0] + arr[i][0][0];
/* Initialize first column of tSum array */
for (j = 1; j < m; j++)
tSum[0][j][0] = tSum[0][j-1][0] + arr[0][j][0];
/* Initialize first width of tSum array */
for (k = 1; k < n; k++)
tSum[0][0][k] = tSum[0][0][k-1] + arr[0][0][k];
/* Initialize first row- First column of tSum
array */
for (i = 1; i < l; i++)
for (j = 1; j < m; j++)
tSum[i][j][0] = min(tSum[i-1][j][0],
tSum[i][j-1][0],
INT_MAX)
+ arr[i][j][0];
/* Initialize first row- First width of tSum
array */
for (i = 1; i < l; i++)
for (k = 1; k < n; k++)
tSum[i][0][k] = min(tSum[i-1][0][k],
tSum[i][0][k-1],
INT_MAX)
+ arr[i][0][k];
/* Initialize first width- First column of
tSum array */
for (k = 1; k < n; k++)
for (j = 1; j < m; j++)
tSum[0][j][k] = min(tSum[0][j][k-1],
tSum[0][j-1][k],
INT_MAX)
+ arr[0][j][k];
/* Construct rest of the tSum array */
for (i = 1; i < l; i++)
for (j = 1; j < m; j++)
for (k = 1; k < n; k++)
tSum[i][j][k] = min(tSum[i-1][j][k],
tSum[i][j-1][k],
tSum[i][j][k-1])
+ arr[i][j][k];
return tSum[l-1][m-1][n-1];
C++
// C++ program for Min path sum of 3D-array #include<bits/stdc++.h> using namespace std; #define l 3 #define m 3 #define n 3 // A utility function that returns minimum // of 3 integers int min(int x, int y, int z) { return (x < y)? ((x < z)? x : z) : ((y < z)? y : z); } // function to calculate MIN path sum of 3D array int minPathSum(int arr[][m][n]) { int i, j, k; int tSum[l][m][n]; tSum[0][0][0] = arr[0][0][0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i-1][0][0] + arr[i][0][0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j-1][0] + arr[0][j][0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k-1] + arr[0][0][k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i-1][j][0], tSum[i][j-1][0], INT_MAX) + arr[i][j][0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i-1][0][k], tSum[i][0][k-1], INT_MAX) + arr[i][0][k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k-1], tSum[0][j-1][k], INT_MAX) + arr[0][j][k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i-1][j][k], tSum[i][j-1][k], tSum[i][j][k-1]) + arr[i][j][k]; return tSum[l-1][m-1][n-1]; } // Driver program int main() { int arr[l][m][n] = { { {1, 2, 4}, {3, 4, 5}, {5, 2, 1}}, { {4, 8, 3}, {5, 2, 1}, {3, 4, 2}}, { {2, 4, 1}, {3, 1, 4}, {6, 3, 8}} }; cout << minPathSum(arr); return 0; } |
Java
// Java program for Min path sum of 3D-array import java.io.*; class GFG { static int l =3; static int m =3; static int n =3; // A utility function that returns minimum // of 3 integers static int min(int x, int y, int z) { return (x < y)? ((x < z)? x : z) : ((y < z)? y : z); } // function to calculate MIN path sum of 3D array static int minPathSum(int arr[][][]) { int i, j, k; int tSum[][][] =new int[l][m][n]; tSum[0][0][0] = arr[0][0][0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i-1][0][0] + arr[i][0][0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j-1][0] + arr[0][j][0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k-1] + arr[0][0][k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i-1][j][0], tSum[i][j-1][0], Integer.MAX_VALUE) + arr[i][j][0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i-1][0][k], tSum[i][0][k-1], Integer.MAX_VALUE) + arr[i][0][k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k-1], tSum[0][j-1][k], Integer.MAX_VALUE) + arr[0][j][k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i-1][j][k], tSum[i][j-1][k], tSum[i][j][k-1]) + arr[i][j][k]; return tSum[l-1][m-1][n-1]; } // Driver program public static void main (String[] args) { int arr[][][] = { { {1, 2, 4}, {3, 4, 5}, {5, 2, 1}}, { {4, 8, 3}, {5, 2, 1}, {3, 4, 2}}, { {2, 4, 1}, {3, 1, 4}, {6, 3, 8}} }; System.out.println ( minPathSum(arr)); } } // This code is contributed by vt_m |
Python3
# Python3 program for Min # path sum of 3D-array l = 3m = 3n = 3 # A utility function # that returns minimum # of 3 integers def Min(x, y, z): return min(min(x,y),z) # function to calculate MIN # path sum of 3D array def minPathSum(arr): tSum = [[[0 for k in range(n)]for j in range(m)] for i in range(l)] tSum[0][0][0] = arr[0][0][0] # Initialize first # row of tSum array for i in range(1,l): tSum[i][0][0] = tSum[i - 1][0][0] + arr[i][0][0] # Initialize first column # of tSum array for j in range(1,m): tSum[0][j][0] = tSum[0][j - 1][0] + arr[0][j][0] # Initialize first # width of tSum array for k in range(1,n): tSum[0][0][k] = tSum[0][0][k - 1] + arr[0][0][k] # Initialize first # row- First column of # tSum array for i in range(1,l): for j in range(1,m): tSum[i][j][0] = Min(tSum[i - 1][j][0],tSum[i][j - 1][0],1000000000) + arr[i][j][0]; # Initialize first # row- First width of # tSum array for i in range(1,l): for k in range(1,n): tSum[i][0][k] = Min(tSum[i - 1][0][k],tSum[i][0][k - 1],1000000000) + arr[i][0][k] # Initialize first # width- First column of # tSum array for k in range(1,n): for j in range(1,m): tSum[0][j][k] = Min(tSum[0][j][k - 1],tSum[0][j - 1][k],1000000000) + arr[0][j][k] # Construct rest of # the tSum array for i in range(1,l): for j in range(1,m): for k in range(1,n): tSum[i][j][k] = Min(tSum[i - 1][j][k],tSum[i][j - 1][k],tSum[i][j][k - 1]) + arr[i][j][k] return tSum[l-1][m-1][n-1] # Driver Code arr = [[[1, 2, 4], [3, 4, 5], [5, 2, 1]], [[4, 8, 3], [5, 2, 1], [3, 4, 2]], [[2, 4, 1], [3, 1, 4], [6, 3, 8]]] print(minPathSum(arr)) # This code is contributed by shinjanpatra |
C#
// C# program for Min // path sum of 3D-array using System; class GFG { static int l = 3; static int m = 3; static int n = 3; // A utility function // that returns minimum // of 3 integers static int min(int x, int y, int z) { return (x < y) ? ((x < z) ? x : z) : ((y < z) ? y : z); } // function to calculate MIN // path sum of 3D array static int minPathSum(int [,,]arr) { int i, j, k; int [ , , ]tSum = new int[l, m, n]; tSum[0, 0, 0] = arr[0, 0, 0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i, 0, 0] = tSum[i - 1, 0, 0] + arr[i, 0, 0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0, j, 0] = tSum[0, j - 1, 0] + arr[0, j, 0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0, 0, k] = tSum[0, 0, k - 1] + arr[0, 0, k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i, j, 0] = min(tSum[i - 1, j, 0], tSum[i, j - 1, 0], int.MaxValue) + arr[i, j, 0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i, 0, k] = min(tSum[i - 1, 0, k], tSum[i, 0, k - 1], int.MaxValue) + arr[i, 0, k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0, j, k] = min(tSum[0, j, k - 1], tSum[0, j - 1, k], int.MaxValue) + arr[0, j, k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i, j, k] = min(tSum[i - 1, j, k], tSum[i, j - 1, k], tSum[i, j, k - 1]) + arr[i, j, k]; return tSum[l-1,m-1,n-1]; } // Driver Code static public void Main () { int [, , ]arr= {{{1, 2, 4}, {3, 4, 5}, {5, 2, 1}}, {{4, 8, 3}, {5, 2, 1}, {3, 4, 2}}, {{2, 4, 1}, {3, 1, 4}, {6, 3, 8}}}; Console.WriteLine(minPathSum(arr)); } } // This code is contributed by ajit |
Javascript
<script> // Javascript program for Min // path sum of 3D-array var l = 3; var m = 3; var n = 3; // A utility function // that returns minimum // of 3 integers function min(x, y, z) { return (x < y) ? ((x < z) ? x : z) : ((y < z) ? y : z); } // function to calculate MIN // path sum of 3D array function minPathSum(arr) { var i, j, k; var tSum = Array(l); for(var i = 0; i<l;i++) { tSum[i] = Array.from(Array(m), ()=>Array(n)); } tSum[0][0][0] = arr[0][0][0]; /* Initialize first row of tSum array */ for (i = 1; i < l; i++) tSum[i][0][0] = tSum[i - 1][0][0] + arr[i][0][0]; /* Initialize first column of tSum array */ for (j = 1; j < m; j++) tSum[0][j][0] = tSum[0][j - 1][0] + arr[0][j][0]; /* Initialize first width of tSum array */ for (k = 1; k < n; k++) tSum[0][0][k] = tSum[0][0][k - 1] + arr[0][0][k]; /* Initialize first row- First column of tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) tSum[i][j][0] = min(tSum[i - 1][j][0], tSum[i][j - 1][0], 1000000000) + arr[i][j][0]; /* Initialize first row- First width of tSum array */ for (i = 1; i < l; i++) for (k = 1; k < n; k++) tSum[i][0][k] = min(tSum[i - 1][0][k], tSum[i][0][k - 1], 1000000000) + arr[i][0][k]; /* Initialize first width- First column of tSum array */ for (k = 1; k < n; k++) for (j = 1; j < m; j++) tSum[0][j][k] = min(tSum[0][j][k - 1], tSum[0][j - 1][k], 1000000000) + arr[0][j][k]; /* Construct rest of the tSum array */ for (i = 1; i < l; i++) for (j = 1; j < m; j++) for (k = 1; k < n; k++) tSum[i][j][k] = min(tSum[i - 1][j][k], tSum[i][j - 1][k], tSum[i][j][k - 1]) + arr[i][j][k]; return tSum[l-1][m-1][n-1]; } // Driver Code var arr= [[[1, 2, 4], [3, 4, 5], [5, 2, 1]], [[4, 8, 3], [5, 2, 1], [3, 4, 2]], [[2, 4, 1], [3, 1, 4], [6, 3, 8]]]; document.write(minPathSum(arr)); </script> |
Output:
20
Time Complexity : O(l*m*n)
Auxiliary Space : O(l*m*n)
This article is contributed by Shivam Pradhan. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
