How to represent a triangle of integers?

algorithm, int, integer, java, python

Solution

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.

Problem

This addresses "a specific programming problem" from On-Topic I am working on an interview question from Amazon Software Interview 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 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.

Original source