Question: This addresses "a specific programming problem" from [On-Topic](https://stackoverflow.com/help/on-topic)

I am working on an interview question from [Amazon Software Interview](http://www.glassdoor.com/Interview/Given-a-triangle-of-integers-find-the-path-of-the-largest-sum-without-skipping-QTN_623875.htm)  

The question is " Given a triangle of integers, find the path of the largest sum without skipping. "

My question is how would you represent a triangle of integers?

I looked this up on [Triangle of Integers](https://stackoverflow.com/questions/25143410/how-to-print-a-triangle-of-integers-with-number-of-lines-specified-by-the-user)  and saw that a triangle of integers looked something like 

```
1
2      3
4      5      6
7      8      9      10
11     12     13     14     15

```

What is the best way(data structure) to represent something like this? My idea was having something like 

```
int[] r1 = {1};
int[] r2 = {2, 3};
int[] r3 = {4, 5, 6};
int[] r4 = {7, 8, 9, 10};
int[] r5 = {11, 12, 13, 14, 15};

```

Is this the best way to represent this triangle integer structure? I thought about using a 2 dimensional matrix structure but those have to have arrays of the same size.

Answer: 
You should put them in linear memory and access them as:

```
int triangular(int row){
 return row * (row + 1) / 2 + 1;
}

int[] r = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
for(int i=0; i<n_rows; i++){
 for(int j=0; j<=i; j++){
  System.out.print(r[triangular(i)+j]+" ");
 }System.out.println("");
}

row, column
if row>column:
 index=triangular(row)+column

```

Since it's a predictable structure there's an expression for the offset of the beginning of each row. This will be the most efficient way.
I'd use a 2D array with guard-bands. In the example below, the 0's represent invalid entries in the array. The top and bottom rows, as well as the leftmost and rightmost columns are the guard-bands. The advantage is that your pathfinding algorithm can wander around the array without having to constantly check for out-of-bounds array indices. 

```
int[][] array =
{
    { 0, 0, 0, 0, 0, 0, 0 },
    { 0, 1, 0, 0, 0, 0, 0 },
    { 0, 2, 3, 0, 0, 0, 0 },
    { 0, 4, 5, 6, 0, 0, 0 },
    { 0, 7, 8, 9,10, 0, 0 },
    { 0,11,12,13,14,15, 0 },
    { 0, 0, 0, 0, 0, 0, 0 }
}; 

```