We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
//Similar to this Java :)
List sum = new ArrayList();
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
sum.add(arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2]);
}
}
System.out.println(Collections.max(sum));
}
Just check the constraints in the problem statement. The algorithm is meant to solve it for a 2D array of size 4x4. Easy to generalize, just get the array dimensions and use it for iteration thresholds.
They are storing all the sums for every hourglass in the array/list. What I don't like about this solution is that you need more memory (allocate another array/list) and finally you need the max function, which may add extra complexity depending on the implementation. I prefer the max variable + if solution better.
Except the contsrtaints include the size of the matrix, which defines the problem as not memory intensive. For an arbitrary sized matrix, you've got memory problems, but you've also got computational problems of order n^2. In the case where the matrix size is unbounded, you'll need to go do a different algorithm entirely (not brute force).
To save space, you can check for max sum with every calculation of the hourglass sum. So instead of having an array with all values and then comparing the max, we can get the result as we traverse :)
my approch has -1 calculation on each glass and no additional array sum. Look on it.
.
'''
def hourglassSum(arr):
len_arr = len(arr)
n=(len_arr-2)**2
s_max = None
for k in range(n):
i = k//(len_arr-2)
j = k%(len_arr-2)
if j==0: # new row glass sum
_ = sum((arr[i][0],arr[i][1],arr[i][2],
arr[i+1][1],
arr[i+2][0],arr[i+2][1],arr[i+2][2])
if(s_max is None):
s_max = _
else: # next glass in the same row sum calc
_ += (-arr[i][j-1]-arr[i+1][j]-arr[i+2][j-1] + \
arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j+2])
s_max = max(s_max,_)
return s_max
'''
This code uses list comprehension to build a list of hour glass sums. For the rows where 3 values are added, I used sum(arr[row][col:col+3]) then summed all values. The code starts at i, j = 0, 0 and I used the size of the array to limit the i and j terms. Think nested loop
def hourglassSum(arr):
addn=[]
for i in range(6):
for j in range(6):
top=arr[i][j]+arr[i][(j+1)%6]+arr[i][(j+2)%6]
middle=arr[(i+1)%6][(j+1)%6]
bottom=arr[(i+2)%6][j]+arr[(i+2)%6][(j+1)%6]+arr[(i+2)%6][(j+2)%6]
add=top+bottom+middle
addn.append(add)
return max(addn)
This is my attempt. but it doesnt pass all testcases for some reason. can anyone explain?
you can avoid writing the long sequence of additions the following way:
1) create a variable called total equal to arr[i+1][j+1]
2) create a third loop of k in range(3).
3) On each iteration of k, add arr[i][j+k] and arr[i+2][j+k] to total.
4) append total to k
Althought it's an elegant writing, it's really poor in terms of performance for the real world. That been said, it's probably the funiest solution for this simple exercice :D
2D Array - DS
You are viewing a single comment's thread. Return to all comments →
Python3 answer
Brilliant!
//Similar to this Java :) List sum = new ArrayList(); for(int i=0; i<4; i++){ for(int j=0; j<4; j++){ sum.add(arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2]); } } System.out.println(Collections.max(sum)); }
why we are iterating upto 4 ??
coz after 4 iteration will ends the matrix .if you count 6*6 matrix and if you need only 3*3 than it will be possible only uptu 4 iterartion
9 -9 -9 1 1 1 0 -9 0 4 3 2 -9 -9 -9 1 2 3 0 0 8 6 6 0 -->>4th line 0 0 0 -2 0 0 0 0 1 2 4 0
you can iterate til 4th line because next iteration give 2 lines only
Just check the constraints in the problem statement. The algorithm is meant to solve it for a 2D array of size 4x4. Easy to generalize, just get the array dimensions and use it for iteration thresholds.
you can use "(len(arr) - 3) + 1", instead of 4. Would work for any size of arr.
Could you please explain!
They are storing all the sums for every hourglass in the array/list. What I don't like about this solution is that you need more memory (allocate another array/list) and finally you need the max function, which may add extra complexity depending on the implementation. I prefer the max variable + if solution better.
Except the contsrtaints include the size of the matrix, which defines the problem as not memory intensive. For an arbitrary sized matrix, you've got memory problems, but you've also got computational problems of order n^2. In the case where the matrix size is unbounded, you'll need to go do a different algorithm entirely (not brute force).
One liner in Python 3:
As array indices also start from zero, it would be convenient to let range function start from 0 (which it does by default):
print(max([sum(arr[i][j:j+3] + [arr[i+1][j+1]] + arr[i+2][j:j+3]) for i in range(4) for j in range(4)]))
Why does the max function contain brackets that also wrap around everything inside?
it's a list comprehension https://python-course.eu/list_comprehension.php
Excellent Well done
print(max(sum(arr[i-1][j-1:j+2] + [arr[i][j]] + arr[i+1][j-1:j+2]) for j in range(1, 5) for i in range(1, 5))) no '[]' list generator,more faster!
My Attempt :)
awesome and cool:)
Python help me understand such questions easily
Even I thought of the same solution but it doesnt pass a lot of test cases
To save space, you can check for max sum with every calculation of the hourglass sum. So instead of having an array with all values and then comparing the max, we can get the result as we traverse :)
Nice simple solution! I feel stupid that I solved it with a 4D array now...
prefect pythonian solution
Why is range(len(arr)-2) ?
A similar NodeJS solution:
Oh, cool. I did something similar but forgot Math.max(). I had to do a sort then get the final element in the array. Thanks!
amazing !
my approch has -1 calculation on each glass and no additional array sum. Look on it. . '''
Here's a python3 one-liner.
This code uses list comprehension to build a list of hour glass sums. For the rows where 3 values are added, I used
sum(arr[row][col:col+3])then summed all values. The code starts at i, j = 0, 0 and I used the size of the array to limit the i and j terms. Think nested loopdef hourglassSum(arr): addn=[] for i in range(6): for j in range(6): top=arr[i][j]+arr[i][(j+1)%6]+arr[i][(j+2)%6] middle=arr[(i+1)%6][(j+1)%6] bottom=arr[(i+2)%6][j]+arr[(i+2)%6][(j+1)%6]+arr[(i+2)%6][(j+2)%6] add=top+bottom+middle addn.append(add)
This is my attempt. but it doesnt pass all testcases for some reason. can anyone explain?
you can avoid writing the long sequence of additions the following way:
1) create a variable called total equal to arr[i+1][j+1]
2) create a third loop of k in range(3). 3) On each iteration of k, add arr[i][j+k] and arr[i+2][j+k] to total. 4) append total to k
Althought it's an elegant writing, it's really poor in terms of performance for the real world. That been said, it's probably the funiest solution for this simple exercice :D
why is it len(arr)-2