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.
You don't need to represent it at all! The starting number of row `r` (starting at 0) is given by the expression:

```
r * (r + 1) / 2 + 1

```