Data Modelling & AI Data Structure & Algorithm

Minimum Sum Path In 3-D Array

23 June 2025

0

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 = 3
m = 3
n = 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:

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.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Minimum Sum Path In 3-D Array

C++

Java

Python3

C#

Javascript

Smarter Retrieval for RAG: Late Chunking with Jina Embeddings v2 and Milvus

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US