HackerRank ‘Array Manipulation’ (Hard) Solution
Solved live by M. Kirschner in Sept 2018 ACiDS Meeting at NU
Originally in Reponse to D. Leschev’s Interview with ‘——‘ (ask Denis, AI company in Toronto/Montreal)
Prompt
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in your array.
For example, the length of your array of zeros $n=10$. Your list of queries is as follows:
a b k
1 5 3
4 8 7
6 9 1
Add the values of $k$ between the indices $a$ and $b$ inclusive:
1 2 3 4 5 6 7 8 9 10 <---index
[0,0,0, 0, 0,0,0,0,0, 0]
[3,3,3, 3, 3,0,0,0,0, 0]
[3,3,3,10,10,7,7,7,0, 0]
[3,3,3,10,10,8,8,8,1, 0]
The largest value is 10 after all operations are performed.
Sample Input
5 3
1 2 100
2 5 100
3 4 100
Sample Output
200
Starting Wrapper
#!/bin/python3
import math
import os
import random
import re
import sys
def arrayManipulation(n, queries):
********CODE GOES HERE********
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nm = input().split()
n = int(nm[0])
m = int(nm[1])
queries = []
for _ in range(m):
queries.append(list(map(int, input().rstrip().split())))
result = arrayManipulation(n, queries)
fptr.write(str(result) + '\n')
fptr.close()
Good Solution
def arrayManipulation(n, queries):
arr = [0]*n
for i in queries:
for j in range(i[0], i[1] + 1):
arr[j - 1] += i[2]
return max(arr)
We loop over the rows in the query, and then sub-loop over the elements of the array than need summation. This approach works, but it will not pass (in an acceptable amount of time) the higher tests in when $n$ is very large e.g. the first line is 10000000 100000 ($n=10000000$ and # queries$=100000$).
Better Solution
def arrayManipulation(n, queries):
arr = [0]*n
for i in queries:
arr[i[0] - 1] += i[2]
arr[i[1]] -= i[2]
maxval = 0
itt = 0
print(arr)
for q in arr:
itt += q
if itt > maxval:
maxval = itt
return maxval
The insight here is that the sum only needs to be calculated for each step or fall in the array rather than every individual element. This is easier understand if you draw a picture, but ultimately it allows us to do a single loop for calculating the two steps in the array, and another for accounting for the maximum step height.
Best Solution
There still remains the edge-case where arr[i[1]] -= i[2] doesn’t work because if i[1] == len(arr), adding ‘fall’ to the ‘step’ is erroneous. So simply add in a conditional before arr[i[1]] -= i[2]
def arrayManipulation(n, queries):
arr = [0]*n
for i in queries:
arr[i[0] - 1] += i[2]
if i[1] != len(arr):
arr[i[1]] -= i[2]
maxval = 0
itt = 0
print(arr)
for q in arr:
itt += q
if itt > maxval:
maxval = itt
return maxval
I feel there’s a mistake in better solution code
arr[i[1] – 1] -= i[2] instead of arr[i[1]] -= i[2]
In case queries(b) has index = n as the array is 1-indexed array, then indexerror will come
what is the TLE problem in this code..please help!
long arr[]=new long[n];
int i,j,l,a,b,k;
long max=0;
for(i=0;i<m;i++)
{
j=0;
a=q[i][j];
b=q[i][j+1];
k=q[i][j+2];
for(l=(a-1);l<b;l++)
{
arr[l]=arr[l]+k;
}
}
for(i=0;i<n;i++)
{
if(max<arr[i])
max=arr[i];
}
return max;
even better option is to realize all the values greater than the half point, are not going to influence the result, thus if arr can be changed to arr = [0] * (n / 2), then in the condition if i[1] != len(arr):, just continue, eg in c++:
vector arr(n / 2, 0);for (auto i: data) {
arr[i[0] - 1] += i[2];
if (i[1] != arr.size()) {
continue;
}
}
long mx = INT_MIN;
long incr = 0;
for (auto val : arr) {
incr += val;
mx = max(mx, incr);
}
return mx;
please explain what “step” and “fall” mean. Your better solution still seems to iterate over the array so I’m a bit confused.
1 sample test case is not passed
Layanan sedot WC Semarang termurah didukung oleh tim profesional yang memiliki keahlian dan pengalaman dalam menangani berbagai masalah WC. Dengan pengetahuan dan keterampilan yang mumpuni, tim ini dapat menyelesaikan masalah dengan cepat dan tepat
Banyak pemain yang telah merasakan pengalaman bermain slot online di REALBET99 memberikan ulasan positif. Mereka memuji kualitas permainan, layanan pelanggan yang responsif, dan bonus yang melimpah
Untuk mendaftar, cukup kunjungi situs REALBET99 dan ikuti instruksi pendaftaran. Isi data yang diperlukan dan pastikan untuk memverifikasi akunmu
Setelah mendaftar, lakukan deposit dana ke akun kamu. REALBET99 menawarkan berbagai metode pembayaran yang aman dan cepat.
REALBET99 menawarkan berbagai pilihan pasaran togel dari berbagai negara, seperti Singapura, Hongkong, Sydney, dan banyak lagi. Dengan beragam pilihan ini, Anda bisa memilih pasaran yang sesuai dengan preferensi dan strategi Anda. Setiap pasaran memiliki karakteristik unik yang bisa Anda pelajari untuk meningkatkan peluang menang.
Dengan menganalisis data tersebut, kita dapat membuat prediksi yang lebih akurat tentang angka-angka yang mungkin muncul di REALBET99
Tidak kalah populer, togel Sydney memiliki daya tarik tersendiri bagi para pemain di REALBET99. Permainan ini memiliki jadwal undian yang berbeda dengan togel Singapore dan Hongkong, memberikan variasi waktu bermain yang lebih fleksibel
REALBET99 sering menawarkan berbagai bonus dan promosi yang bisa dimanfaatkan untuk meningkatkan modal bermain kita. Pastikan kita memanfaatkan setiap kesempatan untuk mendapatkan bonus tambahan.
REALBET99 menawarkan berbagai bonus dan promosi yang menggiurkan untuk menarik dan mempertahankan pemain
Selain itu, REALBET99 memiliki lisensi resmi dari otoritas perjudian terkemuka, menjadikannya platform yang terpercaya dan diakui.